n1e2m3's blog

how to solve this kind of problem?
By n1e2m3, history, 5 years ago, In English

can anyone suggest approach to solve this problem?
https://mirror.codeforces.com/gym/102157/problem/3

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

»
5 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

I think for this problem you're DP state is going to be DP[current index on first row][what elements are matched on bottom row]

We can use a bitmask to represent what elements are matched on the bottom row (with respect to our current index on the first row). Because e <= 4, the we only need to consider "windows" of length 9, so our bit mask goes to 2^9 which is 512. Transitions then become trivial.

I believe the overall complexity is O(N * 2^(2E+1) + N*K).

→ Reply