Approach for the question Cards

general
#1

I always get stuck at this point where dp states depend on both forward and some backward state.In this question : http://codeforces.com/problemset/problem/626/B

I came up with this recurrence relation:

dp[r][g][b] denotes if its is possible to reach this state containing r ‘R’,g ‘G’,b ‘B’.

and relation is dp[r][g][b]=dp[r][g][b] or dp[r+1][g][b] or dp[r][g+1][b] or dp[r][g][b+1] or dp[r-1][g+1][b+1] or dp[r+1][g-1][b+1] or dp[r+1][g+1][b-1].

I want to solve this iteratively without recursion,however i dont know how to iterate,and what to calculate first.

Plz any help is appreciated.

1 Like
#2

As you surely know, the objective is to make sure all the states which a state s depends on are calculated before s. In this particular problem you can see that after every state the number of cards decreases by one. So f(r, g, b) will depend on some states f(r', b', g') as you mentioned above, but observe that r + g + b = r' + g' + b' - 1. And that’s it… just fill up the states in decreasing order of r + g + b.

for(sum=start_value; sum>0; sum--)
    for(int r=0; r<=sum; r++)
        for(int g=0; g<=sum-r; g++) {
            int b = sum-r-g;
            // calculate dp[r][g][b]
        }
1 Like
#3

Thanx a ton!!

Could u plz tell from where should i practice dp. I am currently doing dp problems from codeforces.

Thanks

1 Like