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

→ Обратите внимание

До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
34:34:14
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
7	SecondThread	150
9	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя aman_naughty

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

Автор aman_naughty, история, 5 лет назад, По-английски

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 лет назад
10

Комментарии (10)

Написать комментарий?

Snake___Eater

5 лет назад, # |

← 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])$$$.

→ Ответить

aman_naughty

5 лет назад, # ^ |

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

→ Ответить

Snake___Eater

5 лет назад, # ^ |

yeah, i was wrong, i did some changes.

→ Ответить

aman_naughty

5 лет назад, # ^ |

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

→ Ответить

Snake___Eater

5 лет назад, # ^ |

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.

→ Ответить

aman_naughty

5 лет назад, # ^ |

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

→ Ответить

Snake___Eater

5 лет назад, # ^ |

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

→ Ответить

aman_naughty

5 лет назад, # ^ |

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

code

→ Ответить

Snake___Eater

5 лет назад, # ^ |

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;
}

→ Ответить

ghoshsai5000

5 лет назад, # ^ |

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

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 20.04.2024 07:00:47 (l2).

Десктопная версия, переключиться на мобильную.

При поддержке