Round #633 div2 C (yesterday round):
While Practicing ,I got AC in it ,but i am still not convinced that my solution is correct.
I looked for editorial they said to approach d/f approach as 1 +2 +4 +.... to reach a number . But ,i just simply found the minimum power of 2 which is greater than or equal to our maximum difference. And output that power.
Also to note that in question it was said 2^(x-1) is added to x cost only , but i didn't consider that , i added x for 2^x but still passed TC.
Please Someone tell me ,why i am correct Or give some test case where my solution fails.
It's correct. As you said you're finding the maximum difference, but you're also updating the array values with a[i] = a[i-1], so you calculated 'd' value correctly, and then you basically take the highest set bit of 'd'.
what about , for a power P , its cost should be P+1, but i took P??
Please, work out a small example on paper, it's not hard. You'll see where you are mistaken.