forget_it's blog

By forget_it, history, 5 years ago, In English

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.

76475571

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

    what about , for a power P , its cost should be P+1, but i took P??

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

      Please, work out a small example on paper, it's not hard. You'll see where you are mistaken.