toTalmeSS's blog

TLE
By toTalmeSS, history, 7 years ago, In English

Hello guys... Here's my code for the first problem of the Canada Cup. Unfortunately, I got TLE on test case 4. I was really excited after preparing the solution as I've never been able to solve a single problem within the contest time. Is there anyway to optimize my code? Or do I have to change the approach altogether? Thanks in advance and happy coding to all! Problem link My code

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your solution runs in O(n2). Usually, you can perform about 109 operations per second. On maxtest your solution will do approximately 1010 operations, which does not fit restictions. If you want to optimize your code you can calculate in each position the nearest position of < to the right, and the nearest position of '>' to the left. Using these values you can reduce inner loop asymptotic from O(n) to O(1).

Simpler method is described here.

→ Reply