parveen1981's blog

Need Help: Proof of 1361B- Johny and Grandmaster?
By parveen1981, history, 3 years ago, In English

Hi guys, hope you are doing well. I came across this problem 2 days ago and solved it with intuition. The same algorithm is also given in the editorial.
The problem is that I couldn't find a proper proof for that algorithm. I found this comment which seems to give some proof but I couldn't convince myself that it is a proper proof. Now, I am not able to move forward i.e. skip and solve another problems. I tried to find a proper proof for 2 days but it seems impossible. It would be great help if someone can give a proper proof. Thanks in advance.

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

»
3 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

You can think in terms of base p number system, Suppose, when processing exponents in decreasing order, the first number is p^5, then it is 100000 (You place it in first bag, also lets call S1 -> sum of numbers in first bag and S2 -> the same for second bag) , then if next number will be like 10000, S2 will be 10000, third number can be 10000 then S2 becomes 20000, fourth no->1000, S2->21000. It is clear that S2 will keep increasing but will never become greater than S1 (100000), at most somewhere it will become equal to S1, This is because S2 at any stage will be like XXY00 (X may be zero/non zero, Y is a non zero digit) and then suppose when I add some number to S2, S2 becomes greater than S1, but the maximum number that I can add at this stage is 100, and the max sum that can be obtained is when XXY00 would be ( p-1 p-1 p-1 0 0 ) , so adding 100 to this, we'll get 100000. This is some sort of informal proof that S2 can never become greater S1 without first becoming S1, and when S2 becomes equal to S1, we simply put the next number to S1.

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

    Yes, I can see that S2 can never be greater than S1. But I wanted to ask why this algorithm gives us optimal answer.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 6   Vote: I like it +3 Vote: I do not like it

      This can be proven by induction. Suppose that you have S1 and S2 at any stage (when you process i-1 exponents) (WLOG I assume S1>=S2) and also S1-S2 is minimum, Then there are 2 cases — >

      1) S1-S2 >= p^i , then it is optimal to give p^i to S2, because it will reduce the difference further. also the final difference becomes S1-S2-p^i, which becomes lesser as S1-S2 becomes lesser, since S1-S2 is already minimum by hypothesis, this is indeed optimal. So after processing ith exponent, S1-S2 is again minimum.

      2) S1-S2 < p^i, then it might look optimal to give p^i to S2, however in this case final difference is p^i-S1+S2, this is not optimal when S1-S2 is minimum, in fact here, S1-S2 should be as large as possible. So here the algorithm fails, BUT this case can never occur, as I have already proved that as long as S1-S2 >0, S1-S2-p^i will also be positive or equal to 0, it can never be negative.

      This shows that as long as S1-S2 >0 give the current number to S2. Since it comes under case 1 and is optimal. It is due to the "special property" case 2 never arises.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thank you very much. Your explanation is amazing. Now I get it.

        → Reply