Roland — the Railroad Rat — looks like typical DP but duplicates spoil everything

Revision en1, by RodionGork, 2023-09-26 20:06:20

Hi Friends! Here is the problem created by one of the user's at my site. I don't ask for solution (at least yet, ha-ha, going to try thinking a bit more) — but invite you to check your skills, presumably, at DP.

It has somewhat lengthy description, but boils down to counting number of differing subsequences in 01-string with required balance of zeroes and ones. I quickly started scratching typical DP-like double loop, but soon found it doesn't account for possible duplicates: i.e. in the sequence 1010 we can pick 10 subsequence in two ways but they are not considered different. Results seemingly can grow somewhere to 10^18 so naively keeping all sequences in hashtable doesn't look like a viable approach. Sorry for my naive thoughts, I'm obviously lame at this and perhaps there is a known solution. However if you, like me, don't know it, you can spend some time on it...

Tags dp, subseq, subsequence problem, string

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English RodionGork 2023-09-26 20:06:20 1046 Initial revision (published)