VIKRAM91's blog

Why is my O((2^P)*P) time solution giving TLE in testcase 2?
By VIKRAM91, history, 6 years ago, In English

Recently I did a Gym competition as a virtual contest. I was not able to do Problem D. Largest Group. After completion of the contest, I tried to implement the editorial solution of this given problem. The editorialist is saying that a solution of time complexity O((2^P)*P) will pass. But my solution is giving TLE in test case 2.

Why is my code giving TLE? Is there any other good solution for this problem?

This is my code which I implemented as said in editoiral.

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

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

Change pow(2,p) to (1<<p) and it will get AC. pow(2, p) is too slow and it executes on each iteration in your code.

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

    Why not just assign (1<<p) to a variable? That will eliminate even the bit shifting.

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

      well, 2^p binary shifts will not change the complexity as it is just simple operation, so assigning it to variable will not help at all. function pow got some exponentiation with doubles, so it is very heavy compared to simple binary shifting.

      → Reply