Kuber's blog

Timeout in 546 D
By Kuber, history, 3 years ago, In English

Hi everyone, Please review my submission: https://mirror.codeforces.com/problemset/submission/546/213448834

The logic is exactly the same as that of the person who got the first position in the contest. I'm unable to understand how to change the solution to get AC.

Edit: Changed cout to printf and cin to scanf.

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

here testcase == 1e6 and for each test case your solve function runs at least 5e6 time(considering only the outer for loop), so in total your time complexity will be at least 1e6 * 5e6 == 5e12 which gives TLE. U can not calculate the sieve array every time. Rather pre-calculate the sieve only once before taking any input.

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

    Read the code again. Notice that solve is called exactly once (and thus, sieve runs once). The test cases are solved inside solve in the last for-loop with $$$n$$$ being number of test cases.

    Also, OP already solved the problem by changing cin/cout to scanf/printf: 213448834

    → Reply