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

Problem Overview

• Consider the permutation 1 to $n$ called $P$.
• The parameters $l,r,s$ that satisfies $1\le l\le r\le n$ and $1\le s\le \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\ast (2\ast x+(m-1)\ast -1)}{2}$
$max(x,m)=\frac{m(2x-m+1)}{2}$

Any number $s$ that satisfies $min(k)\le s\le 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\ge 0$ and $s-i\ge 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.

Source Code