elmagico1's blog

any approach for this problem
By elmagico1, history, 10 years ago, In English

http://acmp.ru/index.asp?main=task&id_task=223

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
10 years ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it

Here is my solution (got AC) :

Suppose we call the input string A and the output string B. Let's solve it by dynamic programming with the following state:

F[L1][L2][k] = the amount of ways to solve the problem if we had the substring [L1; L1 + k - 1] of A for the input string and the substring [L2; L2 + k - 1] of B for the output string.

Obviously our solution is in F[1][1][n]. Now let's actually find a way to calculate the states.

Let's for some state F[L1][L2][k] concentrate on the last letter that was popped from the stack. That letter is obviously BL2 + k - 1. Now find all p such that Ap = BL2 + k - 1. Since that is the last letter popped from the stack, then when it was added the stack was empty. That means that all letters AL1, AL1 + 1, ..., Ap - 1 were added to the stack and popped before Ap was added, creating the first few letters in the output string. Similarly, all letters Ap + 1, Ap + 2, ..., AL1 + k - 1 were added and popped from the stack before Ap was popped, creating the next few letters in the output string. This actually divides our problem in two subproblems and gives us a formula:

Obviously for states that have no valid p at all the values is 0.

This yields an O(N4) time complexity algorithm with O(N3) space complexity. The only annoying thing is that an input of two strings of n equal characters has an answer of the n-th Catalan number, which for n = 50 has about 28 digits — forcing you to use 128-bit numbers in all DP state computations.

→ Reply