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
Are you sure that the time-complexity of the recursive function
minCostToConvertToPalindromeis $$$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)$$$.I used caching so it should take ...I am expecting O(N^2)...to be total time complexity
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.
hmmm...i see but isn't the work done at each state constant time ? I given that I dont have any for loops ?
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.
The following update to your code does not get TLE, but it produces wrong answers for some test cases.
Check the following accepted update to the function with provable $$$O(N^2)$$$ time-complexity.