How is the first term of permutation is determined in this question?

problem link-
https://codeforces.com/contest/1141/problem/C

q_i = p_{i+1} - p_i
\sum_{i=1}^{j} q_i = p_{j+1} - p_1
\sum_{j=1}^{n-1} \sum_{i=1}^{j} q_i = \sum_{j=1}^{n-1} p_{j+1} - (n-1)p_1 = \frac{n(n+1)}{2} - np_1
\dfrac{\dfrac{n(n+1)}{2} - \displaystyle\sum_{j=1}^{n-1} \displaystyle\sum_{i=1}^{j} q_i}{n} = p_1
2 Likes

thanks, by the way in editorial they say that p[0]=1-min_val where min_val==min value in prefix sum of q[i].
so i don’t understand this part…if you can please elaborate this a little.

If p[1] = 1-p'[r] such that p'[r] is not the minimum and let p'[x] be the minimum prefix sum. From the editorial, p[i] = p[1] + p'[i]. Substitute in the values,
p[x] = 1 - p'[r] + p'[x] which will be less than 1.

But since the minimum value needs to be 1, this cannot be possible. Thus, p'[r] = p'[x], the minimum value of the prefix sum.

1 Like

okay…still i don’t understand how can we say this…?-> If p[1] = 1-p’[r]
i know this should not be less than 1…and greater than n.