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.