Hustle_Loyalty_Respect's blog

ABC Rotate and Palindrome — TLE even with caching states
By Hustle_Loyalty_Respect, history, 21 month(s) ago, In English

So I have been trying to solve Task C https://atcoder.jp/contests/abc286/tasks/abc286_c in Java. Here is what I came up with :-

     static long minCostToConvertToPalindrome(int a, int b, char[] word, int f, int s) {

        if (f >= s) {
            return 0;
        }

        String cacheKey = f + "-" + s;
        if (cache.containsKey(cacheKey))
            return cache.get(cacheKey);

        // Rotate the word
        int amountSpentInRotation = a + (word[f] == word[f + 1] ? 0 : b);

        // Change the word
        int amountSpentInChanging = word[f] == word[s] ? 0 : b;

        long minAmountSpent = Math.min(
                amountSpentInRotation + minCostToConvertToPalindrome(a, b, word, f + 2, s),
                amountSpentInChanging + minCostToConvertToPalindrome(a, b, word, f + 1, s - 1)
        );

        cache.put(cacheKey, minAmountSpent);
        return minAmountSpent;

    }

Note that I call the function like this -> minCostToConvertToPalindrome(a, b, word, 0, word.length - 1) in my main function.

Now, its clear that there are only N^2 possible combinations of parameters f and s. So the time complexity of my solution is also O(N^2) I think. The editorial also suggests a O(N^2) solution so why does mine not make it?

Please help me Thank you for reading

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

»
21 month(s) ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Are you sure that the time-complexity of the recursive function minCostToConvertToPalindrome is $$$O(N^2)$$$? It seems that the recursive definition for the time-complexity should be something like $$$T(N) = f(N) + 2 \times T(N-2)$$$.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used caching so it should take ...I am expecting O(N^2)...to be total time complexity

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I see. Then, the most probable reason for TLE is that the work done at each of the $$$O(N^2)$$$ states is not constant-time $$$O(1)$$$, i.e. the time-complexity is $$$O(f(N)\times N^2)$$$, where $$$f(N)$$$ is the average time-complexity of the work done at each state.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        hmmm...i see but isn't the work done at each state constant time ? I given that I dont have any for loops ?

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Not exactly. Your code is calling cache.containsKey(cacheKey) in each state, and this is not a conventional array item lookup operation, but a map lookup operation whose time-complexity should be $$$O(\log N)$$$.

          Try to replace that cache map with a conventional 2D array, and check if this will resolve the TLE issue.

          → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          The following update to your code does not get TLE, but it produces wrong answers for some test cases.

          WA
          → Reply
»
21 month(s) ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

Check the following accepted update to the function with provable $$$O(N^2)$$$ time-complexity.

Updated function
→ Reply