Hi!
First of all, I would like to thank SecondThread, really appreciate your videos and effort. I think it really helps beginners, like me — to learn, improve, and understand the thought process of high rated coders.
Problem link : https://codeforces.com/contest/1392/problem/F Solution video link : https://www.youtube.com/watch?v=oHucq2J-3T8&t=12545s
He uses quite an ingenious trick to change the constraint of having adjacent difference >=2 to >=1, by subtracting i from each index initially, and then solving the problem (converts into something much simpler) and again adding the i back to the final array, and thus the solution. Can someone please explain why it works (as in the intuition behind it) (or different way of looking at solution perhaps)? My peanut brain is just not able to grasp it at all.
And if someone has solved it differently and can share the thought process, would really appreciate it.
It's actually a well-known trick that I've seen before at this blog that I sadly didn't realize during the contest.
After the landslide has stopped, for all $$$j,\, h_{j + 1} \leq h_j + 1$$$, which means for all $$$i,\, j$$$ where $$$i < j,\, h_j \leq h_i + (j - i) \rightarrow h_j - j \leq h_i - i$$$. Therefore by subtracting every element by its index, the problem becomes finding the first non-ascending sequence while shuffling everything to the left, which is $$$\lceil\frac{sum}{n}\rceil,\, \dots,\, \lceil\frac{sum}{n}\rceil,\, \lfloor\frac{sum}{n}\rfloor,\, \dots,\, \lfloor\frac{sum}{n}\rfloor$$$, with the first $$$sum\operatorname{mod}n$$$ elements being $$$\lceil\frac{sum}{n}\rceil$$$ and the rest being $$$\lfloor\frac{sum}{n}\rfloor$$$. To find the answer to the problem, simply add the indices back.