### Hustle_Loyalty_Respect's blog

By Hustle_Loyalty_Respect, history, 9 months ago, 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?  Comments (7)
 » 9 months ago, # | ← Rev. 3 →   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)$.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   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.
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   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.
•  » » » » » 9 months ago, # ^ | ← Rev. 4 →   The following update to your code does not get TLE, but it produces wrong answers for some test cases. WAimport java.util.*; public class Main { private static Scanner cin = new Scanner(System.in); private static int N = cin.nextInt(); private static long A = cin.nextLong(); private static long B = cin.nextLong(); private static String S = cin.next(); private static long dp[][] = new long[N][N]; private static long solve(int f, int s) { if (f >= s) return 0L; if (dp[f][s] != -1L) return dp[f][s]; int g = f+1, h = g+1, t = s-1; long r_cost = A+(S.charAt(f) == S.charAt(g) ? 0L : B); long c_cost = S.charAt(f) == S.charAt(s) ? 0L : B; long min_cost = Math.min( r_cost + solve(h,s), c_cost + solve(g,t)); dp[f][s] = min_cost; return min_cost; } public static void main(String args[]) { for (int f = 0; f < N; ++f) for (int s = f+1; s < N; ++s) dp[f][s] = -1L; System.out.println(solve(0,N-1)); } } 
 » 9 months ago, # | ← Rev. 7 →   Check the following accepted update to the function with provable $O(N^2)$ time-complexity. Updated functionimport java.util.*; public class Main { private static Scanner cin = new Scanner(System.in); private static int N = cin.nextInt(); private static long A = cin.nextLong(); private static long B = cin.nextLong(); private static String S = cin.next(); private static char s_char(int i) { return S.charAt(i%N); } private static long minCostToConvertToPalindrome(int op1, long min_cost) { if (op1 == N) return min_cost; int op2 = 0; for (int l = 0, r = N-1; l < r; ++l, --r) if (s_char(l+op1) != s_char(r+op1)) ++op2; return minCostToConvertToPalindrome(op1+1,Math.min(min_cost,A*op1+B*op2)); } public static void main(String args[]) { System.out.println(minCostToConvertToPalindrome(0,Long.MAX_VALUE)); } }