Help in a DP problem

Revision en3, by harsh-apcr, 2024-03-02 22:08:10

Problem Link : https://codeforces.me/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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English harsh-apcr 2024-03-02 22:08:10 64
en2 English harsh-apcr 2024-03-02 22:07:15 21
en1 English harsh-apcr 2024-03-02 22:06:27 570 Initial revision (published)