PROBLEM LINK:
Author: Ankush Khanna
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Graph techniques like DFS, BFS and DSU, Basic Combinatorics, Modular Arithmetic and Modular Inverse.
PROBLEM:
Given a grid A of size N \times M (N rows and M columns ) and an integer K (K \leq N.M), find the smallest connected region with size S \geq K and compute \binom{S}{K} \bmod (10^{9} + 7). If no such region exists, print -1.
Note: If we imagine this grid as an undirected graph where each cell represents a vertex. There is an edge between two vertices if they have the same value (A_{i, j} = A_{p, q}) and they are neighbors (each cell has at most 8 neighbors, well mentioned in the problem statement) to each other. A connected region is a connected component in this graph.
EXPLANATION:
First of all we should figure out the size of the region which will minimize the number of choices. Using basic combinatorics, we can figure that out very easily. We know,
\binom{n}{r} = \frac{n!}{r! (n - r)!} = \frac{\prod\limits_{i = 1}^{r}{(n - r + i)}}{r!}
In our problem, K (r in the above formula) is fixed for every choice. So, in order to minimize the number of choices, we need to minimize the numerator in the above formula. So, we need to choose the size S (S \geq K) (n in the above formula) as small as possible which will minimize the numerator in the above formula and hence minimize the number of choices.
Now we can think about the strategy to solve this problem programmatically. We need to find the connected component in this graph with the smallest size \geq K. This can be done easily using standard graph traversal techniques like DFS or BFS or by using data structures like DSU. Representing this grid as a graph is also a trivial task as the concepts of neighbors and connected regions are well defined in the problem statement itself.
Factorials and their respective modular multiplicative inverses under modulo 10^{9} + 7 (which is a prime number) can be pre-computed easily using basic concepts of Modular Arithmetic.
(For calculating modular multiplicative inverses, we can use Fermat’s little theorem which works in logarithmic time due to Modular Exponentiation for a single inverse. In the solution mentioned below, modular inverse has been calculated in constant time for a single inverse, which is faster but not necessarily needed.)
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const long MOD = (long) 1e9 + 7L;
constexpr int dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int dy[8] = {1, 0, -1, 0, 1, -1, 1, -1};
int n, m, cur;
vector<vector<bool>> vis;
vector<vector<int>> g;
vector<long> fact, inv;
inline bool valid(int x, int y, int id) {
return x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && g[x][y] == id;
}
void dfs(int x, int y) {
vis[x][y] = true;
cur++;
for (int i = 0; i < 8; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (valid(xx, yy, g[x][y])) {
dfs(xx, yy);
}
}
}
inline long add(long a, long b) {
if ((a += b) >= MOD) {
a -= MOD;
}
return a;
}
inline long mul(long a, long b) {
return a * b % MOD;
}
inline void pre_processing() {
constexpr long MAXN = 1'00'001L;
inv.resize(MAXN);
fact.resize(MAXN);
vector<long> x(MAXN);
x[1L] = inv[0L] = inv[1L] = fact[0L] = fact[1L] = 1L;
for (long i = 2L; i < MAXN; i++) {
fact[i] = mul(i, fact[i - 1L]);
x[i] = add(MOD, -mul(MOD / i, x[MOD % i]));
inv[i] = mul(inv[i - 1L], x[i]);
}
}
inline long choose(int n, int r) {
return mul(mul(fact[n], inv[r]), inv[n - r]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
pre_processing();
int tt;
cin >> tt;
while (tt--) {
int k;
cin >> n >> m >> k;
g.assign(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j];
}
}
vis.assign(n, vector<bool>(m));
int min_size = static_cast<int>(MOD);
bool flag = true;
for (int i = 0; flag && i < n; i++) {
for (int j = 0; j < m; j++) {
if (!vis[i][j]) {
cur = 0;
dfs(i, j);
if (cur == k) {
min_size = k;
flag = false;
break;
} else if (cur > k && cur < min_size) {
min_size = cur;
}
}
}
}
if (min_size == static_cast<int>(MOD)) {
cout << "-1\n";
continue;
}
cout << choose(min_size, k) << '\n';
}
return 0;
}
COMPLEXITY:
Time complexity: O(N \times M) per test.
Space Complexity: O(N \times M) auxiliary space per test.
[ Pre-processing takes O(C) time with O(C) auxiliary space where C \leq 10^{5} ]
Feel free to share your approach. If you have any queries, they are always welcome.