I was trying to solve Codeforces round 633 Div1A problem(Powered Addition). Here is my solution
I am not able to understand why this solution is wrong. Shouldn’t I be taking ceiling value because if variable ‘dif’ is in power of 2, I will get an integer answer but if its not the case then I should be taking the ceiling value of the number I will get.
Please help where am i going wrong in this?
It’s not enough to just consider the maximum element. For example, try this:
1
3
999999999 1 1000000000
My output is 31. Is it correct? Also, What do you mean by “It’s not enough to just consider the maximum element.”?
Did you change the link? I think the (new) version correctly handles what I’m talking about.
The correct answer is 30, which is equal to \lceil \log_2{999999999} \rceil. I think you should take ceil(log2(dif + 1)) instead of ceil(log2(dif)) + 1. This represents the range [4, 7] as 3, the range [8, 15] as 4, etc. which is correct.
No, The link was same.
Now, I changed it to ceil( log2 (dif+1)) and it got accepted 
. I understood my mistake. Thanks a lot 
Why calculating highest difference and taking its log works?
1
6
1 7 6 5 8 7
Can you tell what would be change at each second?
The idea of the solution is to create a monotonically increasing array, and of course the only operations you have is to increase. So the final array for your test case would be 1 7 7 7 8 8. Each element at position i has to be at least as large as the maximum of the elements on 0 \dots i - 1 for the array to be monotonic, and there’s certainly no reason to make it higher, so the necessary increase for each element is \max(0, (\max_{0 \leq j \leq i - 1}{a_j}) - a_i), and let d be the maximum change over all elements.
\lceil \log_2{(d + 1)} \rceil happens to capture perfectly the maximum required number of days for any d. Play around with some ranges to see why this works, for example, a d on [4, 7] will yield an answer of 3 days, which you can show to be correct (it’s not 2 because 1 + 2 < 4, and it can be 3 because 7 \leq 1 + 2 + 4).
For the actual changes (0-indexed):
Day 1: increment positions 2 and 5 by 1
Day 2: increments position 3 by 2
Do we have to increase the value at all indices from 2 to 5 by 1?
No, just the values at indices 2 and 5.
Does selection of indices not need to be continuous? I have doubt in this
No (it doesn’t), do you see that somewhere in the statement?
Oh I got it. I misunderstood it. Thanks