Given an array A of size N. You have to perform K operations. Each operation is:
Create a new element equal to the current number of elements.
Decrease other elements by 1.
Any element that is decreased to 0 will be removed.
After that, sort the new array.
Example:
Unable to parse markup [type=CF_TEX]
You need to find what the array will be after K operations.
Contraints:
Unable to parse markup [type=CF_TEX]
-
Unable to parse markup [type=CF_TEX]
K ≤ 109.
I feel like this's gonna be a cycle detection problem. I've tested a few cases and I see that the cycle length is quite short. But I have no idea what the upperbound will be.
It'd be great if someone can help me prove an upperbound for this, or give me a testcase where the cycle length is large.
Thanks in advance !
