Блог пользователя ronak037

How many loops in 1 sec ?
Автор ronak037, история, 5 лет назад, По-английски

Basically I want to know how many loops we can iterate in 1 sec because according to me this number is approx 10^6 but in ques A of given link: https://mirror.codeforces.com/contest/1341/problem/A, I submitted a solution with brute force by thinking that it takes a maximum of 10^6 loops so I will not tle in system cases but that doesn't happen my solution got tle later and I relook into that solution and also not getting the reason why this solution get tle as it takes a maximum of 10^6 loops. Solution link: https://mirror.codeforces.com/contest/1341/submission/77777541. So please anyone explain to me the reason for this. Thank you

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
  1. Put assertions in your code to check your assumption on the number of loop iterations.
  2. Benchmark your code to check which part is using the most amount of time.
→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

There are additional T more loops. So your complexity is O(T*10^6). 10^6 is enough for 1sec but your code runs in 10^6 * 10^3 = 10^9, which is about 10sec.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

In 1 sec we can run a loop doing 1e8 operations. The problem with your code is that as we have t test cases and can have max value of 1000. Suppose you have 1000 test cases so your code can run 1000*( 1000000 ) operations in some cases as 1e9 > 1e8. It will give you TLE.

→ Ответить