Ankit_12's blog

Yesterday Div3 round(Make a Power of Two)
By Ankit_12, history, 3 years ago, In English

Make a Power of Two In this problem, I wrote the code and it gives me TLE on test case-3 without any reason because my code runs in worst-case (269*11) = 2959 and the time limit for this problem is "one second" but still it gives me TLE why? I don't have any Idea anyone help me

My code
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

make_power_of_2() should be preprocessed. You're calling it per testcase without clearing it (looking at Your submission). 40 push_backs per case making its size 40 * 10 ^ 4.

Call it once, or clear the vs vector after each testcase.

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

use 2**62 or larger

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

    No reason for using it as it is cleary mentioned in the question that the value of n<=10⁹ , so even if we add a digit to the right of n it cannot exceed 2^36

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

      u would get a wa generating all powers till 36. you have to generate atleast till 56 because 2^56 > 1e18

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

        And why is it , that we've to generate till 1e18 , the upper limit in the question is 1e9 and the max number of moves to get a power of 2 is (number of digits+1) , that gives us 1e10 in worst scenario

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

          From the editorial of this round:

          Suppose n consists of more than 9 digits. Then n=10^9 because n≤10^9 according to the input format. The answer for the number doesn't exceed 9 — we can get this answer if we erase all 0 from the number to turn it into 1. Suppose there's a number x such that ans(n,x)≤8. This number can consist of no more than 18 digits (10 digits of n plus 8 digits), hence x<10^18.

          Therefore, it's enough to consider all powers of two that are less than 10^18

          → Reply