giantweekbold's blog

TLE on latest Educational Round (D. Journey)
By giantweekbold, 4 years ago, In English

I cannot for the life of me find the reason for which this submission below is getting TLE, could anyone help?

https://codeforces.net/contest/1476/submission/105936603

Any sort of information would be very useful, I have resubmitted since the contest ended, but to no avail.

Initial thoughts such as infinite recursion (whether it's calling itself again, or indexing above n etc.) seem infeasible because of the constraints imposed. Basically, if I am exploring to the right, I will only keep moving right, so it should not call itself again.

I have tested it extensively with different values of n, and always terminates instantly. The fact that Codeforces shows the output from the program makes me suspicious that it is something else. does anyone know the issue?

Thank you kindly.

(p.s. ignore some typos in the brainstorm at the top).

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

»
4 years ago, # |
  Vote: I like it +30 Vote: I do not like it

You are resetting the whole dp array each test case, you should only reset what changed during each test.

→ Reply
»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Here is your AC code.

Can you explain your approach in some more detail?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Of course. Firstly, what are we keeping track of?

    Some people have used a 2-dimensional dp table, but I used a 3-dimensional one. The first dimension stores the index we are at. The second stores whether we are currently moving left or right, The last stores whether we have moved an even or odd number of times.

    Therefore dp[i][dir][parity] will store the number of cities on the (direction) of city (i) if we reach city (i) with (parity) moves.

    The answer for each city is then the number on the left on an even number of visits + the number on the right on an even number of visits (dp[i][0][0] + dp[i][1][0]).

    Transitions are explained in the comments, where parity == 0 is a normal string (to go left s[i — 1] must be 'L') and parity == 1 inverts our string, so if we want to move left s[i — 1] needs to be 'R' for example.

    Hope that helps, thanks for the AC solution.

    → Reply