ABC Rotate and Palindrome — TLE even with caching states

Правка en1, от Hustle_Loyalty_Respect, 2023-03-11 10:19:15

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?