themaskedhero's blog

By themaskedhero, history, 3 years ago, In English,

I've seen this technique before where if you have some recurrence dp(state) = val, you can swap the state and value functions to better the complexity, and instead get dp(val) = state.

I'm looking for examples of these problems, one example is http://usaco.org/index.php?page=viewproblem2&cpid=648 .

Thanks

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

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

A well-known problem is finding Longest Common Subsequence (LCS) of 2 strings , let's say string A and string B. If |A| ≤ 5000, |B| ≤ 10^6 then we cannot use the simple DP approach since its complexity is O( |A|.|B| ).

One observation is that, the length of LCS is indeed ≤ min( |A|,|B| ). Then instead of let dp[i][j]=k be the longest LCS when we consider first i characters of A and first j characters of B, we will let dp[i][k]=j meaning j is the smallest position in B so that it can form a LCS length k with first i characters of A.

This required a pre-processed array next[i][j] meaning the first position of character j in [i..|B|]. However, the complexity for DP now is O(|A|^2).

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

Given an array of n ≤ 106 positive integers, output the number of non-empty subsequences whose sum is divisible by a given 2 ≤ m ≤ 300, modulo 1000003. You may try it here.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

The nlogn optimization for longest increasing subsequence swaps the state and value, optimizing for the smallest last value that has a certain length.

This is described here: https://en.wikipedia.org/wiki/Longest_increasing_subsequence