asawa_harsh's blog

Getting TLE on Atcoder ABC219D Problem
By asawa_harsh, history, 2 years ago, In English

I wrote a recursive solution with O(n^3) time complexity imo.

But I am getting TLE Verdict on submission .

Problem Link

  • Vote: I like it
  • -15
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The main issue is that the parameter valX and valY is the solve funciton may be negative, and lead to many useless states. Since we only care about whether we have enough x and y, so change LINE22 into return dp[i][valX][valY] = min(1 + solve(i + 1, max(0, valX - v[i].ff), max(0, valY - v[i].ss)), solve(i + 1, valX, valY)); would just be fine.

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

    Thank u so much!

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

      Still got a TLE. Submission

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

        I got the following update.

        Accepted

        → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        The default dp value should also be changed. Change 1e9 in LINE21 and LINE43 into -1.

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

          Why taking -1 gets an AC whereas taking 1e9 as dp value gets a TLE.

          AC submission

          TLE Submission

          Difference in the runtime is also huge. TLE submission takes 2.2s still no output whereas AC submission takes 0.3s with just this small change. Can you clarify?

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

            In the TLE Submission, the default dp value is 1e9. This means that when you call the solve function and the current dp[i][valX][valY] is 1e9, it keeps doing recursion.

            Assume current state is valX=10, valY=10, and the suffix of the input data is like [..., {1,1}, {1,1}, {1,1}, {1,1}]. We cannot subtract valX and valY to 0 even if we use all the suffix, so the dp[i][valX][valY] is 1e9. When you visit this state again, LINE21 check that the dp value is 1e9 and still need to be searched. The runtime would be exponential to n in the worst case.

            Generally speaking, it's a bad idea to mix the UNVISITED status and the INVALID status when we do dfs with memorization.

            → Reply