PROBLEM LINK:
Author: Temirlan Baibolov
Tester & Editorialist: Radoslav Dimitrov
DIFFICULTY:
PREREQUISITES:
Probability, Euler’s Formula
PROBLEM:
Given a M \times N matrix of random integers between 1 and K, find the expected number of strongly connected components if we have a directed edges between every two adjacent cells iff the value in the first cell is greater than or equal to the value in the second cell.
Quick Explanation
We notice that every strongly connected component will have all of its vertices/cells equal to the same value.
Then we can just solve the problem of finding the number of connected components if the graph was undirected and we had edges iff two adjacent cells had the same value. This has a simple solution because we can use Euler’s formula for planar graphs.
Explanation
We’ll first show why our problem is equivalent to counting the number of connected components in the undirected graph formed by edges between cells with the same value. Let’s prove this by contradiction:
Assume there are two adjacent cells (x_1, y_1) and (x_2, y_2) that are in the same strongly connected component and A_{x_1, y_1} < A_{x_2, y_2}. Then by the definition of strong connectivity, there should exist a path from (x_1, y_1) to (x_2, y_2). However, all edges “decrease” the value (i.e. they go from a larger value to a lower one). This means that all cells reachable from (x_1, y_1) will have a value of at most A_{x_1, y_1}. Therefore, (x_2, y_2) is not reachable from (x_1, y_1), because A_{x_1, y_1} < A_{x_2, y_2}. This contradicts with our assumption of the cells being in the same strongly connected component$.
From the above proof, it follows that two cells can be in the same strongly connected component iff their values are the same (then we have a bidirectional edge). This by itself is equivalent to counting the number of connected components in an undirected graph.
To solve this new problem (the undirected version), we first notice that the graph is planar by construction. This is useful, because of one of the most popular theorems for planar graphs - Euler’s formula. It states that v - e + f = 2, where v is the number of vertices in the graph, e is the number of edges and f is the number of faces. This formula works for any connected planar graph, but it can be easily generalised for graphs with more than one connected component (which is our case). Let k be the number of connected components. Then the generalisation states that v - e + f = 1 + k.
Let’s get back to our problem. We are interested in \mathop{\mathbb{E}}[k] = \mathop{\mathbb{E}}[v - e + f - 1]. Using linearity of expectation we get \mathop{\mathbb{E}}[k] = \mathop{\mathbb{E}}[v] - \mathop{\mathbb{E}}[e] + \mathop{\mathbb{E}}[f] - \mathop{\mathbb{E}}[1]. Now we’re only left with calculating the different terms of the previous equation:
-
\mathop{\mathbb{E}}[v] is the expected number of vertices. This is clearly always constants, so \mathop{\mathbb{E}}[v] = N * M.
-
\mathop{\mathbb{E}}[e] is the expected number of edges. We’ll use the contribution idea (with linearity of expectation) to calculate it. Consider an edge between two different cells. It’ll exist iff the values in the two cells are the same. Therefore, the probability of it existing is \frac{1}{K}, as we can think of this as if we’ve fixed the first value and then finding the probability of the second one being the same. Now we can simply use linearity of expectation to get that \mathop{\mathbb{E}}[e] = \frac{N * (M - 1) + (N - 1) * M}{K}, because we have N * (M - 1) + (N - 1) * M edges and the contribution of each one is equal to \frac{1}{K}.
-
\mathop{\mathbb{E}}[f] is the expected number of faces. The main observation here is that we can only have a face that looks like a 2 \times 2 square with the same value. Also we shouldn’t forget that we always have 1 additional face on the “outside”. Clearly, that M = 1, we have \mathop{\mathbb{E}}[f] = 1, because the only face is the “outside” one. Now let’s consider the M = 2 case. Then we can again use linearity of expectation. The number of 2 \times 2 squares is N - 1 and the probability of each of them forming a face is \frac{1}{K^3} (using the same idea of fixing one of the values). Then \mathop{\mathbb{E}}[f] = \frac{N - 1}{K^3} + 1.
-
\mathop{\mathbb{E}}[1] = 1. This one is quite obvious.
Now we are pretty much done. We just calculate the 4 above-mentioned values in constant* time and then fine the required expectation for the number of connected components.
*(we have to find the inverse of K, so the complexity actually logarithmic).
Additional comments
The given constraints might look a bit weird, because they allow linear solutions. This is because initially the author’s solution was using FFT to calculate the number of configurations with 1, 2, ... , N * M connected components. This didn’t look very natural, so the problem was converted to finding the expectation for the number of connected components (where the intended solution was again FFT). Then while testing the problem, I solved it with the Euler’s formula, but we decided to still let the FFT/some other linear solutions pass and so we didn’t increase the constraints to 10^9.
Also, there is a way to solve the M = 3 case (which wasn’t included in the problem) again using the Euler’s formula solution, as then we only need to additionally count the 3 \times L faces which always look like a border with a “hole” inside. An open question would be whether it’s possible to count the number of components for larger M's. If you have some ideas, I’m open to discuss!
Tester's solution
#include <bits/stdc++.h>
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int mod = 998244353;
int pw(int x, int p) {
int r = 1;
while(p) {
if(p & 1) r = r * 1ll * x % mod;
x = x * 1ll * x % mod;
p >>= 1;
}
return r;
}
int n, m, k;
void read() {
cin >> m >> n >> k;
}
void solve_1() {
int ik_c = (1 - pw(k, mod - 2) + mod) % mod;
int ans = (1ll + ik_c * 1ll * (n - 1)) % mod;
cout << ans << endl;
}
void fix(int &x) {
if(x >= mod) x -= mod;
if(x < 0) x += mod;
}
void solve_2() {
int ik = pw(k, mod - 2);
// We'll use Euler's theorem:
// v - e + f = 1 + k
// E[k] = 2 * n - 1 - E[e] + E[f]
//
// E[e] = ik * (3 * n - 1)
int answer = 2 * n - 1;
answer -= ik * 1ll * (3ll * n - 2) % mod; fix(answer);
int Ef = ik * 1ll * ik % mod;
Ef = Ef * 1ll * ik % mod;
Ef = Ef * 1ll * (n - 1) % mod;
Ef += 1; // main face
answer += Ef; fix(answer);
cout << answer << endl;
}
void solve() {
if(m == 1) solve_1();
else solve_2();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
read();
solve();
return 0;
}