Ssaranshh13's blog

WHY TLE?
By Ssaranshh13, history, 3 years ago, In English

I have written the code to solve 1609C - Сложный анализ рынка problem, but it gives TLE. I think the complexity of my soln. is O(n*log(log(n) because of Seive rest of the work i have done in linear time. My approach is as follows:

Suppose arr[i] is prime I have calculated the number of chains of 1 on left of arr[i] and similarly on right of arr[i]. Then i have used sum+=onesLeft[i]+onesRight[i]+onesLeft[i]*onesRight[i]; to get the answer.

Here is my submission ----> https://mirror.codeforces.com/contest/1609/submission/160055418. Please tell where I am wrong in calculating the time complexity? Thanks in advance.

Tags dp
  • Vote: I like it
  • -10
  • Vote: I do not like it

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

You are doing sieve for each test case, which is wasteful.

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

To expand the previous comment: you can execute isPrime(1e6) line in a main() function before the for loop, because the parameters will never change. Hence, you will you will have no need to execute it every time in a solve() function and your code will be succesfully AC.

→ Reply