Alex7's blog

By Alex7, history, 2 years ago, In English,

Given 2 binary strings A and B of each with length at most 175, we want to combine them to produce a new string C the following way: As long as either one of strings A, B choose one of them (as long as it's non empty) add the first character in the chosen string to the end of C and then delete from that string. The task is for each distinct possible resulting C sum the square of the number of ways you can arrive at it with that procedure modulo some prime.

This problem was presented in a local IOI selection in 2012, we suspect it was ripped from some USACO related contest (since all other problems that year were also stolen from there), so I don't really have a link for it but I know it's possible to solve it. Any ideas? Thanks in advance.

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

»
2 years ago, # |
  Vote: I like it +29 Vote: I do not like it

The answer is the number of ways we can choose 2 equal strings from the list of all strings generated by this procedure. Consider 4-dimensional dp: dp[pos1A][pos1B][pos2A][pos2B] = the number of ways we can generate 2 equal strings such that the first one has used pos1A characters from the string A and pos1B characters from B, and the second one has used pos2A characters from A and pos2B from B. The answer is dp[|A|][|B|][|A|][|B|]. We can compress this dp to O(n3) states by using only states where the first and the second string have the same length.

»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yesss, I remember the organizes switched AB with HG to trick copyrights lol