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

Getting TLE on Atcoder ABC219D Problem
Автор asawa_harsh, история, 3 года назад, По-английски

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

But I am getting TLE Verdict on submission .

Problem Link

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

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

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.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank u so much!

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Still got a TLE. Submission

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I got the following update.

        Accepted

        → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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?

          → Ответить
          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            → Ответить