Color a 3XN grid using atmost 4 colors DP Problem help needed

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
17:54:50
Register now »

*has extra registration

→ Streams

Leetcode BiWeekly Contest 144 — Solution Discussion

By Shayan

Before stream 19:24:49

Codeforces CodeTON Round 9 (Div 1 + Div 2) — Solution Discussion

By Shayan

Before stream 20:54:49

View all →

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

aman_naughty's blog

Color a 3XN grid using atmost 4 colors DP Problem help needed

By aman_naughty, history, 5 years ago, In English

Problem : link

Code : code

My approach is : For any {i,j} I maintain 4 colors dp[i][j][0],dp[i][j][1],dp[i][j][2] and dp[i][j][3];

dp[i][j][k] denotes the number of ways to fill the board[0..i][0..j] using the color k at position i,j.

To fill dp[i][j][k] we need only summation of (dp[i-1][j][l]+dp[i][j-1][l]) where l varies from 0 to 3 and l is not equal to k.

In simple words to fill i,j with color k number of ways would be we can fill i-1,j with color other than k and i,j-1 with color other than k.

In the end my answer would be summation of dp[3][n][k] where 0<=k && k<=3;

Why is this approach wrong as I am getting wrong answer for n=2 test case?

Any help is appreciated.

#interview, #2d-dp, codenation, help

aman_naughty
5 years ago
10

Comments (10)

Write comment?

Snake___Eater

5 years ago, # |

← Rev. 3 →

There is at most $$$4^3$$$ configurations for a column, so you can model the problem as a $$$dp[i][j][k][l]$$$, that means the number of configurations ending at column $$$i$$$ with colors $$$j$$$ $$$k$$$ $$$l$$$ for this column.

$$$dp[i][j][k][l] = 0;$$$ if $$$j = k$$$ or $$$k = l$$$.

$$$dp[i][j][k][l]$$$ = $$$SUM(dp[i - 1][t][f][g])$$$ where $$$t \neq f$$$ and $$$f \neq g$$$ and $$$t \neq j$$$ and $$$k \neq f$$$ and $$$l \neq g$$$.

This is $$$O(N*4^6)$$$, dont use $$$mod$$$(%) operator, just substract the number if he becomes greater than $$$10^9 + 7$$$, i think this is enough to fit in the time.

EDIT: The answer is $$$SUM(dp[n][i][j][k])$$$.

→ Reply

aman_naughty

5 years ago, # ^ |

I believe your approach is wrong as ABA in a column is still a vaild coloring.

→ Reply

Snake___Eater

5 years ago, # ^ |

yeah, i was wrong, i did some changes.

→ Reply

aman_naughty

5 years ago, # ^ |

Your approach seems good but can you tell what is the flaw in my approach

→ Reply

Snake___Eater

5 years ago, # ^ |

I dont know if i will can explain, but you are not counting all combinations, because if you sum $$$dp[i][j - 1][l]$$$ + $$$dp[i - 1][j][l]$$$, is all combinations for fixed values for column $$$j$$$ in positions 1..i-1 plus all combinations for fixed values for line $$$i$$$ in positions 1..j-1.

→ Reply

aman_naughty

5 years ago, # ^ |

your approach will not fit in time limit as n can be 1e5

→ Reply

Snake___Eater

5 years ago, # ^ |

I think if you do a interative dp and dont use mod operador, it fit in time cause are 409600000 operations in the worst case, i think it is less than 1s

→ Reply

aman_naughty

5 years ago, # ^ |

Thanks for the reply. I implemented what you suggested but it is giving wrong answer for n=2 case.

code

→ Reply

Snake___Eater

5 years ago, # ^ |

The lines 18-20 isnt right, check my ac solution.

code

int dp[100001][4][4][4];

int Solution::solve(int A) {
    const int mod = int(1e9) + 7;
    const int D = 4;
    
    memset(dp, 0, sizeof dp);
    
    for(int j = 0 ; j < D ; j++){
        for(int k = 0 ; k < D ; k++){
            if(k == j){
                continue;
            }
            
            for(int l = 0 ; l < D ; l++){
                if(l == k){
                    continue;
                }
                
                dp[0][j][k][l] = 1;
            }
        }
    }
    
    for(int i = 1 ; i < A ; i++){
        for(int k = 0 ; k < D ; k++){
            for(int l = 0 ; l < D ; l++){
                if(l == k) continue;
                
                for(int d = 0 ; d < D ; d++){
                    if(l == d) continue;
                    
                    for(int e = 0 ; e < D ; e++){
                        if(e == k) continue;
                        
                        for(int f = 0 ; f < D ; f++){
                            if(f == e || f == l) continue;
                            
                            for(int g = 0 ; g < D ; g++){
                                if(g == f || g == d) continue;
                                
                                dp[i][k][l][d] += dp[i - 1][e][f][g];
                                
                                if(dp[i][k][l][d] >= mod){
                                    dp[i][k][l][d] -= mod;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    int sum = 0;
    
    for(int j = 0 ; j < D ; j++){
        for(int k = 0 ; k < D ; k++){
            if(k == j){
                continue;
            }
            
            for(int l = 0 ; l < D ; l++){
                if(l == k){
                    continue;
                }
                
                sum += dp[A - 1][j][k][l];
                
                if(sum >= mod){
                    sum -= mod;
                }
            }
        }
    }
    
    return sum;
}

→ Reply

ghoshsai5000

5 years ago, # ^ |

Thanks a lot for sharing your solution ! I've been looking for the solution to this problem for quite a few months now !

→ Reply