alpenglow's blog

By alpenglow, history, 2 weeks ago, In English

Given numbers $$$1$$$ to $$$n$$$, we have to make all those number equal to zero by choosing some subset and subtracting same value from all of them, we have to use minimum number of operations.

My idea was to always split it into two parts and get two {$$$1,2..n/2-1,n/2$$$} sets from {$$$1,2,..n$$$} set and continue like this recursively. This approach is correct and leads to $$$ceil(log_2(n))$$$ solution. What is the proof this being optimal?

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint: prove that, for one operation, if the number of different values in the set was $$$k$$$ before the operation, it will be at least $$$\lceil k / 2 \rceil$$$ after the operation.

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

    I think the middle is optimal because if didn't do middle we would have one smaller and one larger set and the answer will only depend on the larger set, because we do things in parallel.

    Is this the correct proof?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      More or less.

      The important part is this: when we have $$$k$$$ distinct elements, and pick $$$p$$$ elements to decrease, there are $$$k - p$$$ old elements which will still be distinct, and there are $$$p$$$ new elements which will still be distinct since we decreased them all by the same value. So, the number of distinct elements after the operation will be at least $$$\max (k - p, p)$$$. This number is at least $$$\lceil k / 2 \rceil$$$.

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

In each step choose a set containing numbers that in its binary representation have a $$$1$$$ in the $$$i$$$-th position and subtract $$$2^{i}$$$ from them. After $$$\left \lceil{\log_{2} n}\right \rceil$$$ steps we are done.