PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Ildar Gainullin
Tester: Felipe Mota
Editorialist: Taranpreet Singh
DIFFICULTY:
Hard
PREREQUISITES:
Graph-Matchings, Maths, Observations and Hard work!
PROBLEM:
Given an initial graph G with N nodes and M edges and an integer K. A line graph L(G) is defined as a graph representing each edge in G as a node in L(G) and any pair of nodes in L(G) are connected if and only if the corresponding edges in G share an endpoint.
Let L^k(G) define the operation “replace G by L(G)” k-times. Find the size of largest independent set in L^K(G) modulo 998244353
EXPLANATION
I’d suggest reading each section one by one, think and probably write. Each section heavily depend on previous one.
Observation 1
The size of largest independent set in L(G) is same as the size of maximum matching in G
A Tip
If graph G is disconnected, the independent set chosen in one component doesn’t affect the choice of independent set in other components. So we solve for each component separately.
This is important, as all subsequent observations assume connected graph G.
Observation 2
The size of largest maximum matching in a line graph L(G) is \lfloor \frac{|V(L(G))|}{2} \rfloor where V(H) denotes the number of vertices in H
And, the number of vertices in L(G) is also the same as the number of edges in G
What does that imply?
For K = 2, the number of edges in each component of G divided by 2 shall be size of maximum matching in L(G) which is size of largest independent set in L^2(G)
Now, we need to find the number of edges in L^{K-2}(G) for 3 \leq K \leq 7. The time is for some casework.
K = 3
We need number of edges in each component of L^{3-2}(G) = L(G)
Let’s denote degree of i-th vertex in G by d_i. Since all pairs of edges incident to this vertex share an endpoint, each pair shall form an edge. And there are d_i*(d_i-1)/2 such pair of edges.
Let f(N) = (N*(N-1)/2)
So, we can take sum of s(d_i) over all edges and divide the sum by 2 (Each edge in L(G) is included twice, one for each endpoint). This gives the number of edges in L(G).
K = 4
For K = 3, we just managed to count the number of edges in L(G) by degree sequence of G. If we could somehow get degree sequence of L(G), we can get number of edges in L^2(G)
Each edge (u, v) in G correspond to a node in L(G), so we need to find the degree that vertex shall have. For endpoint u, there are d_u-1 other edges which have u as an endpoint, therefore, shall be adjacent to vertex corresponding to edge (u, v) in L(G).
Applying same login on other endpoint, we get degree of node corresponding to edge (u, v) as (d_u-1)+(d_v-1) = d_u+d_v-2 and take sum over f(d_u+d_v-2)
K = 5
We need number of edges in L^{K-2}(G) = L^3(G)
Consider three nodes in G as 1 2 and 3 and two edges (1, 2) and (2, 3) and assuming degrees as d_1,d_2 and d_3 respectively.
Since the two edges share an endpoint, they’ll contribute to an edge in L(G) with degree (d_1+d_2-2) + (d_2+d_3-2) -2 = 2*d_2+(d_1+d_3)-6 in L(G) which contribute to a vertex in L^2(G) with degree 2*d_2+(d_1+d_3)-6. This contributes to f(2*d_2+(d_1+d_3)-6) to final answer.
Generalizing, for each pair of edges (u, v) and (u, w), it contributes f(2*d_u+(d_v+d_w)-6) to number of edges in L^3(G)
Taking sum over all pairs of edges having u as common vertex, the total number of edges generated due to edges sharing endpoint v is given as \displaystyle 2*S = d_u*(d_u-1)*(2*d_u^2-13*d_u+21) + (d_u-1)*(4*d_u-13)* \sum_{v} d_v + (d_u-2)* \sum_{v} d_v^2 + \big( \sum_v d_v \big)^2
Proof (Not for light-hearted folks
We need to sum over all pairs v, w which are neighbours of u and v \neq w and add f(2*d_u + d_v+d_w - 6). Let’s call final sum S (Considering both (v, w) and (w, v) for ease, multiplying S by 2)
\displaystyle 2*S = \sum_{v} \sum_{w} (2*d_u + d_v+d_w -6) * (2*d_u + d_v+d_w -7) /2
\displaystyle 4*S = \sum_{v} \sum_{w} (4*d_u^2 + 8*d_u*(d_v+d_w) + (d_v+d_w)^2 - 13*(2*d_u+d_v+d_w) + 42
\displaystyle 4*S = \sum_{v} \sum_{w} ((4*d_u^2-26*d_u+42) + (d_v+d_w)*(4*d_u-13) + (d_v+d_w)^2
The way i grouped terms, each group either doesn’t depend on (d_v+d_w), depend on (d_v+d_w) or (d_v+d_w)^2. Taking closed form and dividing y 2 both sides.
\displaystyle 2*S = d_u*(d_u-1)*(2*d_u^2-13*d_u+21) + (d_u-1)*(4*d_u-13)* \sum_{v} d_v + \sum_{v} \sum_{w} (d_v+d_w)^2/2
Expanding the term \displaystyle \sum_{v} \sum_{w} (d_v+d_w)^2, we get \displaystyle \sum_v \sum_w d_v^2 + d_w^2 + 2*d_v*d_w which is same as
\displaystyle 2*(d_u-1)*\sum_v d_v^2 + \sum_v \sum_w 2*d_v*d_w
The last term is basically the sum of product of values x_i taken two at a time, and have a nice simple form, given as (\sum x_i)^2 - \sum x_i^2 as explained in detail here.
So plugging back, we get
\displaystyle 2*S = d_u*(d_u-1)*(2*d_u^2-13*d_u+21) + (d_u-1)*(4*d_u-13)* \sum_{v} d_v + (d_u-1)* \sum_{v} d_v^2 + \big( \sum_v d_v \big)^2 - \sum_{v} d_v^2
which gives
\displaystyle 2*S = d_u*(d_u-1)*(2*d_u^2-13*d_u+21) + (d_u-1)*(4*d_u-13)* \sum_{v} d_v + (d_u-2)* \sum_{v} d_v^2 + \big( \sum_v d_v \big)^2
So, for each vertex in current component, we can compute \sum_v d_v and \sum_v d_v^2 and compute the final answer.
K = 6
If you noticed, for K = 5, we just used degree of vertices. What if we extend it to figure out degrees of edges in L(G) and apply K = 5 idea on that?
Can we?
Yes, we can. All we need is the sum of degrees of edges which share an endpoint. We get degree of to be vertex (u, v) as (d_u+d_v-2) sum of degrees of nodes adjacent to node u plus sum of degree of nodes adjacent to v subtracting the degree of this edge.
Similarly, we can compute sum of squares of degrees in same fashion.
K = 7
Ah, the final case many of you were waiting for. The most complex part of this problem.
Let's see
Since M \leq 2000, we can actually create L(G) with M nodes for given graph G.
TIME COMPLEXITY
The time taken to make Line Graph is O(M^2). Edmond’s seem to take asymptotic complexity O(N^2*M) but seem to work way faster.
SOLUTIONS:
Setter's Solution
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
struct Dsu{
vector<int> p;
void init(int n){
p.resize(n);
iota(p.begin(), p.end(), 0);
}
Dsu(int n){
init(n);
}
Dsu(){}
int find_set(int i){ // iterative path compression
int j=i;
int ret=i;
while(ret!=p[ret]){
ret=p[ret];
}
i=p[j];
while(i!=j){
p[j]=ret;
j=i;
i=p[i];
}
return ret;
}
void unite_set(int a, int b){
p[find_set(a)] = find_set(b);
}
};
struct Matcher{
vector<vector<int> > graph; // adjacency list
vector<int> mate, origin, pred; //vertex vectors
deque<int> augmenting_path; // vertex list
vector<pair<int, int> > bridge; // vertex pair vector
vector<int> vertex_state; // state vectors 0=unreached, 1=odd, 2=even
vector<int> ancestor_v, ancestor_w; // vertex vectors
vector<pair<int, int> > even_edges; // edge vector
Dsu dsu;
Matcher(int N){
graph.resize(N);
mate.resize(N, -1);
origin.resize(N);
pred.resize(N);
bridge.resize(N);
vertex_state.resize(N);
ancestor_v.resize(N);
ancestor_w.resize(N);
}
void add_edge(int a, int b){
assert(a>=0 && a < (int)graph.size());
assert(b>=0 && b < (int)graph.size());
graph[a].emplace_back(b);
graph[b].emplace_back(a);
}
void clearMatching(){
fill(mate.begin(), mate.end(), -1);
}
///parent in DFS tree
int parent(int vertex){
if(vertex_state[vertex]==2 && mate[vertex]!=-1)
return mate[vertex];
else if(vertex_state[vertex]==1)
return origin[dsu.find_set(pred[vertex])];
else
return vertex;
}
void link_set_bridges(int vertex, int LCA, pair<int, int> bridge_edge){ // shrink Blossom to LCA
for(int v=vertex; v!=LCA;v=parent(v)){
dsu.unite_set(v, LCA);
origin[dsu.find_set(LCA)] = LCA;
if(vertex_state[v] == 1){
bridge[v] = bridge_edge;
for(auto const &e:graph[v]){ // repush edges, as this is now a single blossom-vertex
if(e!=v){
even_edges.emplace_back(v, e);
}
}
}
}
}
void retrieve_augmenting_path(int v, int w, bool is_reversed){
if(v==w){
augmenting_path.push_back(v);
}
else if(!is_reversed){
if(vertex_state[v]==2){ //straight up the blossom
augmenting_path.push_back(v);
augmenting_path.push_back(mate[v]);
retrieve_augmenting_path(pred[mate[v]], w, false);
} else { // down the blossom and up on the other side
augmenting_path.push_back(v);
retrieve_augmenting_path(bridge[v].first, mate[v], true);
retrieve_augmenting_path(bridge[v].second, w, false);
}
} else {
if(vertex_state[v]==2){ //straight up the blossom
retrieve_augmenting_path(pred[mate[v]], w, true);
augmenting_path.push_back(mate[v]);
augmenting_path.push_back(v);
} else { // down the blossom and up on the other side
retrieve_augmenting_path(bridge[v].second, w, true);
retrieve_augmenting_path(bridge[v].first, mate[v], false);
augmenting_path.push_back(v);
}
}
}
/// Searches a single augmenting path
bool augment(){
/// INIT
int timestamp = 0;
even_edges.clear();
int N = graph.size();
dsu.init(N);
for(int i=0;i<N;++i){
origin[i]=i;
pred[i]=i;
ancestor_v[i] = ancestor_w[i] = 0;
if(mate[i]==-1){
vertex_state[i]=2;//Even
for(auto const &e:graph[i]){
even_edges.emplace_back(i, e);
}
} else {
vertex_state[i]=0; //unreached
}
}
/// END OF INIT
/// AUGMENTING PATH DFS
int v, w, w_ancestor = -1, v_ancestor = -1;
bool found_altenating_path=0;
while(!even_edges.empty() && !found_altenating_path){
pair<int, int> curEdge = even_edges.back();
even_edges.pop_back();
tie(v, w)=curEdge;
int v2=origin[dsu.find_set(v)];
int w2=origin[dsu.find_set(w)];
if(vertex_state[v2]!=2){
cerr << "swap, should not happen...";
swap(v, w);
swap(v2, w2);
}
if(vertex_state[w2] == 0){ // Add matched pair to Tree ( v----w2===w2_mate )
vertex_state[w2]=1;
int w2_mate = mate[w2];
vertex_state[w2_mate] = 2;
for(auto const &e:graph[w2_mate]){
if(e!=w2_mate){
even_edges.emplace_back(w2_mate, e);
}
}
pred[w2] = v;
} else if(vertex_state[w2] == 2 && w2!=v2){ // if w2==v2 this was a inter-blossom edge
int vUp = v2, wUp = w2; // used to climb up the DFS tree
int lowest_common_ancestor = -1;
w_ancestor = -1, v_ancestor=-1;
// here we either found a blossom, or an augmenting path
++timestamp;
while(lowest_common_ancestor==-1 &&(v_ancestor==-1 || w_ancestor==-1)){
ancestor_v[vUp] = ancestor_w[wUp] = timestamp;
if(w_ancestor == -1)
wUp = parent(wUp);
if(v_ancestor == -1)
vUp = parent(vUp);
if(mate[vUp] == -1)
v_ancestor = vUp;
if(mate[wUp] == -1)
w_ancestor = wUp;
if(ancestor_w[vUp] == timestamp)
lowest_common_ancestor = vUp;
else if(ancestor_v[wUp] == timestamp)
lowest_common_ancestor = wUp;
else if(v_ancestor==w_ancestor && v_ancestor != -1)
lowest_common_ancestor = vUp;
}
if (lowest_common_ancestor==-1){ // different DFS tree roots
found_altenating_path = 1;
} else {
// found blossom
link_set_bridges(w2, lowest_common_ancestor, make_pair(w, v));
link_set_bridges(v2, lowest_common_ancestor, make_pair(v, w));
}
}
}
if(!found_altenating_path)
return false;
/// END OF AUGMENTING PATH DFS
/// AUGMENTATION
//retrieve augmenting path and use it
retrieve_augmenting_path(v, v_ancestor, true);
retrieve_augmenting_path(w, w_ancestor, false);
//cerr << "augment: "<< v_ancestor << "-" << w_ancestor << " : ";
while(!augmenting_path.empty()){
v=augmenting_path.front();augmenting_path.pop_front();
w=augmenting_path.front();augmenting_path.pop_front();
mate[v]=w;
mate[w]=v;
//cerr << "->" << v << "->" << w;
}
//cerr << "\n";
/// END OF AUGMENTATION
return true;
}
void get_matching(){
bool done=false;
while(!done){
done = !augment();
}
}
int get_maching_size(){
get_matching();
int ret=0;
for(int i=0;i<(int)graph.size();++i){
if(mate[i]!=-1 && mate[i]<i)++ret;
}
return ret;
}
};
const int N = 2002;
const ll M = 998244353 * 4ll;
const int need_M = 998244353;
void add(ll &a, ll b) {
a += b;
if (a < 0) a += M;
if (a >= M) a -= M;
}
ll mul(ll a, ll b) {
return (a * b) % M;
}
vector <int> g[N];
bool u[N];
vector <int> verts;
vector <pair <int, int> > e;
void dfs(int v) {
verts.push_back(v);
u[v] = true;
for (int to : g[v]) {
if (!u[to]) {
dfs(to);
}
if (v < to) {
e.push_back({v, to});
}
}
}
vector <vector <int> > chill(vector <vector <int> > g) {
int n = (int) g.size();
vector <pair <int, int> > e;
for (int i = 0; i < n; i++) {
for (int j : g[i]) {
if (i < j) {
e.push_back({i, j});
}
}
}
vector <vector <int >> gr(e.size());
int m = (int) e.size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
if (i == j) continue;
if (e[i].first == e[j].first || e[i].first == e[j].second || e[i].second == e[j].first || e[i].second == e[j].second) {
gr[i].push_back(j);
}
}
}
return gr;
}
ll solve_connected_stup(int n, vector <pair <int, int >> e, int k) {
vector <vector <int> > gr(n);
for (auto c : e) {
gr[c.first].push_back(c.second);
gr[c.second].push_back(c.first);
}
if (k == 1) {
Matcher solve(n);
for (auto c : e) {
solve.add_edge(c.first, c.second);
}
return 2 * solve.get_maching_size();
} else {
k--;
for (int i = 0; i < k - 1; i++) {
gr = chill(gr);
}
int sum = 0;
for (int i = 0; i < (int) gr.size(); i++) sum += gr[i].size();
return sum / 2;
//return gr.size();
}
}
ll solve_connected(int n, vector <pair <int, int> > e, int k) {
if (k == 1) {
Matcher solve(n);
for (auto c : e) {
solve.add_edge(c.first, c.second);
}
return 2 * solve.get_maching_size();
} else {
k -= 2;
vector <vector <int> > gr(e.size());
for (int i = 0; i < (int) e.size(); i++) {
for (int j = 0; j < (int) e.size(); j++) {
if (i == j) continue;
if (e[i].first == e[j].first || e[i].first == e[j].second || e[i].second == e[j].first || e[i].second == e[j].second) {
gr[i].push_back(j);
}
}
}
if (k == 0) {
return gr.size();
} else {
vector <ll> d(gr.size());
for (int i = 0; i < (int) gr.size(); i++) {
d[i] = gr[i].size();
}
auto f = [&] (ll d, ll d2, ll sq_d2) {
ll cost = mul(2, mul(d, d));
add(cost, -mul(13, d));
add(cost, 21);
add(cost, 4 * d2);
cost = mul(cost, d);
cost = mul(cost, d - 1);
add(cost, -mul(13, mul(d - 1, d2)));
add(cost, mul(d - 2, sq_d2));
add(cost, mul(d2, d2));
return cost;
};
if (k == 1) {
ll sum = 0;
for (int i = 0; i < (int) gr.size(); i++) {
sum += d[i];
}
return sum / 2;
} else if (k == 2) {
ll sum = 0;
for (int i = 0; i < (int) gr.size(); i++) {
int x = d[i];
int deg = x * (x - 1) / 2;
add(sum, deg);
}
return sum;
} else if (k == 3) {
ll sum = 0;
for (int i = 0; i < (int) gr.size(); i++) {
for (int j : gr[i]) {
if (i < j) {
int val = d[i] + d[j] - 2;
int ok = val * (val - 1) / 2;
add(sum, ok);
}
}
}
return sum;
} else if (k == 4) {
vector <ll> d2(gr.size());
vector <ll> sq_d2(gr.size());
for (int i = 0; i < (int) gr.size(); i++) {
for (int j : gr[i]) {
add(d2[i], d[j]);
add(sq_d2[i], d[j] * d[j]);
}
}
ll sum = 0;
for (int i = 0; i < (int) gr.size(); i++) {
add(sum, f(d[i], d2[i], sq_d2[i]));
}
return sum / 2;
} else if (k == 5) {
vector <ll> prec(gr.size());
vector <ll> prec_sq(gr.size());
for (int i = 0; i < (int) gr.size(); i++) {
for (int j : gr[i]) {
add(prec[i], d[i] + d[j] - 2);
add(prec_sq[i], mul((d[i] + d[j] - 2), (d[i] + d[j] - 2)));
}
}
ll sum = 0;
for (int i = 0; i < (int) gr.size(); i++) {
for (int j : gr[i]) {
if (i < j) {
ll edge_d = d[i] + d[j] - 2;
ll edge_d2 = prec[i];
add(edge_d2, prec[j]);
add(edge_d2, -mul(edge_d, 2));
ll edge_sq_d2 = prec_sq[i];
add(edge_sq_d2, prec_sq[j]);
add(edge_sq_d2, -mul(mul(edge_d, edge_d), 2));
add(sum, f(edge_d, edge_d2, edge_sq_d2));
}
}
}
return sum / 2;
} else {
//oh no...
return -1;
}
}
}
}
int main() {
#ifdef iq
freopen("a.in", "r", stdin);
#endif
/*
int k = 7;
int tc = 0;
while (true) {
int n = rnd() % 6 + 1;
int m = rnd() % (n * (n - 1) / 2 + 1);
if (m > 11) m = 11;
vector <pair <int , int> > ed;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
ed.push_back({i, j});
}
shuffle(ed.begin(), ed.end(), rnd);
ed.resize(m);
assert(solve_connected(n, ed, k) == solve_connected_stup(n, ed, k));
cout << solve_connected(n, ed, k) << ' ' << solve_connected_stup(n, ed, k) << endl;
cout << "OK" << tc++ << endl;
}
*/
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--, b--;
g[a].push_back(b);
g[b].push_back(a);
}
ll ans = 0;
for (int i = 0; i < n; i++) {
if (!u[i]) {
verts.clear();
e.clear();
dfs(i);
sort(verts.begin(), verts.end());
verts.resize(unique(verts.begin(), verts.end()) - verts.begin());
for (auto &c : e) {
c.first = lower_bound(verts.begin(), verts.end(), c.first) - verts.begin();
c.second = lower_bound(verts.begin(), verts.end(), c.second) - verts.begin();
}
ll edges = solve_connected((int) verts.size(), e, k);
edges /= 2;
add(ans, edges);
}
}
cout << ans % need_M << endl;
}
Editorialist's Solution
Will add soon.
Feel free to share your approach. Suggestions are welcomed as always. 