# REDGREEN - Editorial

Author: Utkarsh Gupta
Tester: Tejas Pandey
Editorialist: Nishank Suresh

2319

Combinatorics

# PROBLEM:

You have an N\times M grid, each cell of which can be colored either red or green. The score of a colored grid is the number of right-down paths from (1, 1) to (N, M) such that the number of red cells equals the number of green cells on this path.

Find the sum of scores across possible colorings of the grid.

# EXPLANATION:

This task can be solved with a trick that’s rather common in counting problems, sometimes called the contribution trick.

Whenever you need to fix a configuration and count the number of objects in it that satisfy some property, you can often instead fix an object that satisfies that property and count how many configurations it appears in — the sum of both values is the same.

Let’s do the same thing here. We want to

• Fix a coloring of the grid
• Look at a right-down path from (1, 1) to (N, M)
• Count it if it has an equal number of red and green cells

• Fix a right-down path from (1, 1) to (N, M)
• Color it in such a way that the number of red and green cells is equal
• Then, count the number of grids that contain this path

Summing this across all paths is the the final answer.

Now, let’s see how to compute this.

• First, we need to fix a path. There are \binom{N+M-2}{M-1} paths from (1, 1) to (N, M) — this is a well-known result.
• An easy proof is that you make exactly N+M-2 steps in total with M-1 of them being right and N-1 being down, so fixing the positions of the right steps fixes the path.
• Next, we need to color the path correctly.
• Let the length of the path be \$L. Note that L = N + M - 1.
• If L is odd, there is no way to color the path correctly
• Otherwise, we simply fix the positions of the green cells in \binom{L}{L/2} ways, which then also fixes the red cells
• Finally, we want to know how many grids this path appears in. We’ve fixed the colors of cells on the path, but everything else is completely free and has two choices each (red or green).
• This gives us 2^{N\cdot M - L} grids that contain this path.

So, the final answer is simply

\binom{N+M-2}{M-1} \binom{L}{L/2} 2^{N\cdot M - L}

where L = N + M - 1. Note that the answer is 0 when L is odd.

The binomial coefficients can be precomputed in a 2000\times 2000 table using Pascal’s identity since we only need something like \binom{2000}{1000} at worst. Similarly, the powers of 2 upto 10^6 can be precomputed.

This allows each query to be answered in \mathcal{O}(1) time.

There are of course other ways to compute binomial coefficients (for example, the standard factorial + inverse factorial method) and powers of 2 (via binary exponentiation), if you want to do something else.

# TIME COMPLEXITY

\mathcal{O}(1) or \mathcal{O}(\log {MOD}) per test case, depending on implementation.

# CODE:

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define maxn 10007
#define mod 998244353

long long int fact[maxn], ifact[maxn];

long long int mpow(long long int a, long long int b) {
long long int res = 1;
while(b) {
if(b&1) res *= a, res %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return res;
}

void pre() {
fact[0] = fact[1] = ifact[0] = ifact[1] = 1;
for(int i = 2; i < maxn; i++) fact[i] = fact[i - 1]*i, fact[i] %= mod;
for(int i = 2; i < maxn; i++) ifact[i] = ifact[i - 1]*mpow(i, mod - 2), ifact[i] %= mod;
}

long long int comb(long long int a, long long int b) {
if(b == 0) return 1LL;
long long int ans = fact[a];
ans *= ifact[b];
ans %= mod;
ans *= ifact[a - b];
ans %= mod;
return ans;
}

int main() {
pre();
int t;
cin >> t;
while(t--) {
int n, m;
cin >> n >> m;
if((n + m - 1)&1) cout << "0\n";
else {
long long int paths = comb(n + m - 2, m - 1);
paths *= ((fact[n + m - 1]*((ifact[(n + m - 1)/2]*ifact[(n + m - 1)/2])%mod))%mod);
paths %= mod;
paths *= mpow(2, n*m - (n + m - 1));
paths %= mod;
cout << paths << "\n";
}
}
return 0;
}

Editorialist's code (Python)
mod = 998244353
N = 2005
C = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
C[i][0] = 1
for i in range(1, N):
for j in range(1, i+1):
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod

for _ in range(int(input())):
n, m = map(int, input().split())
len = n + m - 1
ans = C[n+m-2][m-1] * C[len][len//2] * pow(2, n*m - len, mod)
if len%2 == 1:
ans = 0
print(ans%mod)

2 Likes

Tried using dfs but could not optimize my solution
Can someone help ??
This gave AC for few test cases but TLE for others…

#include <bits/stdc++.h>
#define int long long int

int mod = 998244353, n = 0, m = 0;

int expo(int a, int b, int mod)  {
int res = 1;
while (b > 0) {
if (b & 1)
res = (res * a) % mod;
a = (a * a) % mod;
b = b >> 1;
}
return res;
}

int dfs(int i, int j, int c1, int c2){
if(i > n || j > m)
return 0;
if(i == n && j == m){
if(c1 == c2){
return expo(2, n*m-c1-c2, mod);
}
return 0;
}
int ans = 0;
ans = (ans + dfs(i+1, j, c1+1, c2))%mod;
ans = (ans + dfs(i+1, j, c1, c2+1))%mod;
ans = (ans + dfs(i, j+1, c1+1, c2))%mod;
ans = (ans + dfs(i, j+1, c1, c2+1))%mod;
return ans%mod;
}

void solve(){
n, m;
std::cin >> n >> m;
int ans = dfs(1, 1, 1, 0) + dfs(1, 1, 0, 1);
std::cout << ans << "\n";
}

signed main() {

std::ios::sync_with_stdio(false);
std::cin.tie(0);

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE

int t = 1;
std::cin >> t;
while(t--){
solve();
}
}


can we do it like we can see that only the path with even length can have equal R’s and G’s so
now we need to find how many possibilities we can get equal 0’s and 1’s for length n. if we found that now our answer is simply the product of that number and all possible paths.

for a length n path if even the number of equal R’s and G’s would be 2*(3)^(n/2 - 1) ?
i was not able to code it? any help i was stuck at finding numbers of paths.

Loved this explanation finally able to solve my first modulo combinations problem.
lerned many concepts

2 Likes

can u please tell intution behind dfs ?

Can someone share a DP solution to this problem?

1 Like

for(int i = 2; i < maxn; i++) ifact[i] = ifact[i - 1]*mpow(i, mod - 2), ifact[i] %= mod;

Can anyone explain this line given in editorial