RodionGork's blog

By RodionGork, history, 10 months ago, In English

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...

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

10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Here is almost the same task, the only difference is that subsequence must be a right brace sequence.

  • »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! That sounds like a generous hint — about the relation to brace sequence problems (though to my weak brain it is yet to figure out if this is the same, given that 0-1 sequence doesn't actually need to be as "right" as brace sequence)