harsh-apcr's blog

By harsh-apcr, history, 8 months ago, In English

Problem Link : https://mirror.codeforces.com/problemset/problem/1912/K

My approach : Reduce all the numbers mod 2 and then work with the following,

$$$dp[i][xy] = $$$ # subsequences in $$$a_1 \ldots a_i$$$ with consecutive sum of 3 is divisible by 2 which ends with $$$x, y$$$.

$$$dp[i][xy] = $$$ if $$$y = a_i$$$ then $$$ dp[i-1][xy] $$$ (not choose $$$a_i$$$) + $$$dp[i-1][zx]$$$ (choose $$$a_i$$$) ($$$z$$$ here is $$$(x+y) \textrm{mod} 2)$$$ ; else $$$ dp[i-1][xy] $$$

Base case $$$dp[2][a_1 a_2] = 1$$$ (others are initialised to 0)

But I'm not really getting correct answer with this approach, I can't really see why this is wrong. Any help is appreciated

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome problem. Look at this solution: 236990750 I think it explains the best.