2029C - New Rating

• Implemented the dynamic programming solution I read yesterday.

Submission: 292352411

Another straightforward question that I was not able to solve.

We do not need to care about the placement of the elements at the start(and therefore also at the end) of the array, since they can only be influenced by the elements in front and behind them respectively. Instead we can just swap $$$a_1$$$ and $$$a_{n - 1}$$$ elements instead. Therefore we can keep $$$a_0$$$ and $$$a_n$$$ as is.

For an index $$$i$$$ we can compare the disturbance before and after operating on it wrt to the $$$(i - 1)^{th}$$$ and $$$(n - i)^{th}$$$ elements respectively.

But What about the $$$(i + 1)^{th}$$$ and $$$(n - i - 1)^{th}$$$ elements?

Submission: 292357132

A pretty straightforward question.

If we make a graph with edges from $$$i$$$ to $$$p_i$$$, the resulting graph will be a functional graph. A functional graph built on permutations will always consist of disconnected cycles. Therefore for each cycle the number of black integers reachable from any vertex $$$v$$$ will be equal to the number of black vertices $$$\theta$$$ in that cycle.

We can perform a simple dfs and solve this question.

This is a question, I have tried multiple times before but to no avail. The editorial for this is just not something that I am able to come up with.

Basically the entire solution to this problem hinges on the fact that for the smallest square number $$$h \ge k$$$ then $$$h \le 2 * k$$$ or $$$h - k \le k$$$. Therefore for all $$$i \in [h - k,k]$$$ we can put $$$h - i$$$ as our answer and then recursively fill for all vertices from $$$h - k - 1$$$ and below.

This ensures that each $$$i + p_i$$$ adds up to its respective square number, and since value is dependent on the index $$$i$$$ these numbers will be unique.