abcdef6199's blog

By abcdef6199, history, 8 years ago, In English

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 !

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +46 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Some hints, please :( I tried to prove it but I can't :( Thanks.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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...

»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

According to this paper the length of every cycle is