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:
8311 - > 742 - > 6331 - > 5422.
You need to find what the array will be after K operations.
Contraints:
1 ≤ Ai
sum(Ai) ≤ 100
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 !
The sum is constant through the process so every array is a [partition](https://en.wikipedia.org/wiki/Partition_(number_theory)) of sum. The number of partitions for 100 is about 2·108. Real bound is smaller because not all the partitions can occur: for example, it is easy to prove that after 100th iteration all the numbers are smaller than 20 and the length of array is smaller than 20.
Could you tell me some hint about how to prove that "After 100 iterations, the length and the maximum value are less than 20"? I tried to prove it but.... Thanks in advance.
Some hints, please :( I tried to prove it but I can't :( Thanks.
I guess I saw this as a theoretical problem in the past...But I really can't remember what was the exact statement and what was the solution...
So I think it should be a better bound on this problem...
According to this paper the length of every cycle is