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.