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

Автор hardikkapoor, история, 4 года назад, По-английски

Recently i was giving a competition, specifically Codeforces round #647 div 2 and in the problem B (1362B - Johnny and His Hobbies), I thought the brute force approach would give TLE, as the complexity was O((n^2)logn) and combined with number of test cases it would give operations of nearly 10^10, which wont fit 1 second time. But at last i submitted the bruteforce and it passes the pretests. So, i just want to know if the number of test cases has any effect on the overall time complexity of the program. Thank you.

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

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Notice: "It is guaranteed that the sum of n over all test cases will not exceed 1024". Therefore we can essentially assume one huge test case, so the brute force only does n^2 * log(n) operations, which is at most 1.05e7.