Codeforces Round 965 Discussion stream (with hints)

Chose $A_1 = (K \cdot X_C, K \cdot Y_C)$.

The remaining points such that sum of x coordinates and y coordinates is 0.

Sum of all elements will be equal in both permutations. So no of such $(i,j)$ is atleast 1. Can you find a permutation $Q$ such that this count remains 1?

Set $Q_i = 1$ if $P_i = N$, Set $Q_i = 1 + P_i$ if $P_i < N$, otherwise

Set $Q_i = P_{(i+1) \mod N}$

Lets forget about $A_i$ and focus on $C_i$ first. If we have and array of $N-1$ elements $A_i$ and binary array of $N-1$ elements $B_i$. What is the maximum median we can get using atmax $K$ operations?

We can binary search for median. We can directly count how many elements are more than mid, and how many elements we can make more than median. Using segment tree, walk on segment tree and blah blah blah…

Notice that at any point all the elements are sum of continous subarray.

Define a function solve(L,R) which returns true, if we can convert element with weight $\sum A_L+A_{L+1}+\ldots+A_{R}$ into an element with weight $\sum A$

Use greedy, for fixed index $L$ and $R$, find a minimum $nxtL$ such that $\sum A_{nxtL} + A_{nxtL+1} + \ldots + A_{L-1} \le A_L+A_{L+1}+\ldots+A_{R}$, make a direct jump to $nxtL,R$ segment.

Do similar for $nxtR$, and memorise all the answer of solve function.

For each element $j$ there is a range $(L_j,R_j)$ in which it can be present as last elemt.

Modify the Solve function to now return what is the minimum index $L_j$, instead of boolean earlier. Basically find minimum $L_j$ such that element $j$ can become $\sum A_1+A_2+\ldots A_{Lj}$

Also for each index $i$ precalcute how much right it can go. Use this to calculate $R_j$ based on $L_j$.

Otherway around you can also return this range in your solve function.