# Codeforces #713(Div.3) E: Permutation by Sum

## Problem Overview

- Consider the permutation 1 to \(n\) called \(P\).
- The parameters \(l, r, s\) that satisfies \(1 \leq l \leq r \leq n\) and \(1 \leq s \leq \frac{n(n + 1)}{2}\) are given.
- Find the permutation which satisfies \(P_{l} + P_{l + 1} + … + P_{r} = s\).
- Print any permutation of length \(n\) that fits the condition above if such a permutation exists; otherwise, -1.

## Problem Explanation

First, consider the minimum and the maximum value we can generate with the length \(r - l + 1\).

Hereafter, we define \(k = r - l + 1\).

**Minimum Value**

As an arithmetic sequence with first term 1, term number \(m\), and tolerance 1, we can derive the minimum value.

\(min(m) = \frac{m(m + 1)}{2}\)

**Maximum Value**

As an arithmetic sequence with first term \(x\), term number \(m\), and tolerance -1, we can derive the maximum value.

\(max(x, m) = \frac{m * (2 * x + (m - 1) * -1)}{2}\)

\(max(x, m) = \frac{m(2x - m + 1)}{2}\)

Any number \(s\) that satisfies \(min(k) \leq s \leq max(n, k)\) meet the condition.

**Coding**

First, we prepare the vector \(res\) with size \(n\) to push the results.

Consider in descending order.

Start the for loop from \(n\),

if \(i\) meets the condition \(max(i, k) - s \geq 0\) and \(s - i \geq min(k - 1)\), put \(i\) to the \(res[l + k]\) and replace \(k = k - 1, s = s - i\).

Iterate this until \(k\) becomes 0, and then if \(s = 0\) is achieved, we find the permuation; otherwise, prints -1.

The remaining part of the implementation is to insert the unused numbers into the empty parts of the vector.