PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Srikkanth R
Tester: Manan Grover
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Medium
PREREQUISITES:
Eulerian Circuit, Graph Traversal
PROBLEM:
Let us clear out some terms used in the problem:
- Vertex-Induced Subgraph - It is obtained by removing some (possibly none) vertices from a simple graph G. When a vertex is removed, all edges incident to it must also be removed.
- Vertex-Induced Cycle - A vertex-induced subgraph that is also a cycle. Equivalently, a cycle C is vertex induced, if, for every edge e in the graph G that does not belong to C, at most one of its ends lies on C.
- Move on a Vertex-Induced Cycle - In one move on a selected vertex-induced cycle, you flip the values of the label on all the edges of the cycle (i.e., change 0 to 1 and 1 to 0).
- Cost of a move - Cost of a move is equal to the size(i.e. number of edges) of the cycle. The total cost of a sequence of moves is the sum of costs of each individual move.
Given a simple undirected graph G with N vertices and M edges. Each edge has a label that is 0 or 1.
Let the total number of edges in G with label 1 equal to k.
Find a sequence of moves with total cost no more than 3 \cdot k, such that, after these moves, all the edges have label 0. If this sequence does not exist, print -1.
It’s guaranteed that if an answer exists, there exists a sequence of moves with a total cost not exceeding 3 \cdot k.
QUICK EXPLANATION:
- We define a “chord” of a cycle C in a graph G as an edge in G between two non adjacent vertices of C. Note that similar to the chord for a circle in geometry, a chord in a cycle C splits it into two smaller cycles.
- Let G_s denote the subgraph with edges having labels equal to 1. If G_s is not an even subgraph, the answer is -1.
- Construct an Eulerian Circuit and decompose it into cycles.
- While there exists a cycle with a chord, remove the cycle and replace it with the two smaller cycles that contain the chord.
- Output the set of cycles obtained as the answer.
EXPLANATION:
Let us understand what a vertex-induced cycle (C) actually means. We are given that it is a vertex-induced subgraph that is also a cycle. Let’s call an edge between two non-adjacent vertices of a cycle, a “chord” of the cycle. Intuitively the chord is similar to its definition for circles in geometry. A vertex induced cycle is one that does not have any chords.
When is the answer -1?
After every move, the number of flipped edges incident on any vertex is always even. This is because the degree of every vertex in every cycle is 2, so if one edge incident on it is flipped then another has to flipped as well. Thus if any vertex has odd number of edges labelled 1 incident on it, then the answer is surely -1. If this is not the case, then we can find a sequence of moves (as we show in the next section).
Part 1: An easier version and relevance of Euler Circuit
Let’s consider an easier version of the problem where we are allowed to choose any cycle (not just vertex induced ones).
The problem is very similar to that of finding an Euler Circuit.
For this easier version, we will ignore all edges with label 0, we will not need them. Let the graph obtained after removing edges with label 0 be G_s. Every vertex in G_s has an even degree and k edges and O(k) vertices (after removing vertices with degree 0).
The graph G_s must definitely contain a cycle, because all nonempty acyclic graphs contains at least one leaf (which has degree 1) . We can find the cycle in O(k) time (using any cycle detection algorithm) and remove the edges of the cycle from G_s. After removing the cycle, the degrees of all vertices remains even (vertices of cycle have their degrees reduced by 2) and as long as at least one edge remains we can keep finding cycles and remove them from the graph. Eventually the graph becomes empty.
It is clear that in O(k^2) time we can decompose the edges labelled 1 into edge disjoint cycles (as described above) and we can apply the move for each cycle independently. The total cost of these moves is exactly k.
We can implement this part of the problem in O(k) as well, but we will not discuss them here.
Order of moves to do matter
If we have any sequence of moves, the flipped edges after all moves are performed does not change if the order in which the operations are performed is changed.
This is because an edge is flipped only if it is a part of an odd number of cycles across all moves.
Part 2: Finding a sequence of moves
In the previous part, we obtained a set of moves where each move flipped edges of some cycle (not necessarily vertex induced cycles). Here we describe how to modify these moves so that every cycle is vertex induced. We cannot ignore edges with label 0 now, since they may be required (for example consider a cycle with a single chord).
Consider a cycle C in the set of moves that is not vertex induced. By definition, C must contain a chord (i.e. an edge of the graph joining two non-adjacent vertices of C). This chord splits the cycle into two smaller cycles C_1, C_2. The two cycles do not share any edge apart from the chord. If we flip all edges of C_1 followed by all edges of C_2, then equivalently all edges of C will have been flipped and all other edges remain unchanged (i.e. chord is flipped twice and others untouched). Therefore if we remove C from the set of moves and replace it with two moves C_1, C_2 the output remains same.
We can keep repeating the above procedure and we have shown that as long as there are cycles that are not vertex induced, we can reduce the size of some cycle. No cycle can have less than 3 vertices, therefore after some (finite) number of iterations we will end up with a set of cycles each of which is vertex induced as desired. The pseudocode is summarized below,
// S = set of cycles which flip all edges labelled 1
while (there exists a cycle C in S that is not vertex induced) {
e = any chord of C that splits it into C_1, C_2
remove C from S
add C_1 and C_2 to S
}
Implementation and Calculating Cost
The first part is finding an euler circuit, which can be done in O(k^2) time.
The second part can also be done in O(k^2) time with proper implementation, which we will discuss in some detail here. We also show that the total cost is no more than 3k for the above solution.
As n \leq 1000, we can afford O(n^2) space and we can store the graph in adjacency matrix form (this will enables us to find chords efficiently).
Let’s focus on decomposing a cycle C with s vertices, v_1, v_2, \dots v_s. We will attempt to find a chord by checking if an edge between (v_i, v_j) exists in the order (v_1, v_3), (v_1, v_5), \dots (v_1, v_s), (v_2, v_4), (v_2, v_5), \dots (v_{s-2}, v_s). Checking if an edge belongs to the graph is O(1) since we are using adjacency matrix representation. Once we add a chord and split a cycle, we will never check for this edge again. Also when we split a cycle, make sure to keep them “sorted”, i.e. in the same order as they were present in C. Thus every vertex induced cycle is a subsequence of C. If implemented this way, every edge is visited only once, and the total complexity of finding chords is O(s^2) for decomposing C and thus O(\sum s^2) = O(\left(\sum s\right)^2) = O(k^2) in total.
To add and remove cycles C, we can maintain the sequence of moves as a linked list of linked lists (or equivalently your favourite container with dynamic memory for example std::vector in C++). We will just use brute force to construct and add C_1, C_2 in O(k) time.
We will now show that the total number of “cycle” replacements that we need to perform is O(k), thus the total complexity is O(k^2) overall.
Suppose the total number of cycles initially is t with sizes s_1, s_2, \dots s_t respectively.
After one cycle replacement,
- the total number of cycles increases by 1
- the total number of edges increases by 2
After y cycle replacements, there are t + y cycles in total with k + 2y edges in total. As each cycle must have size at least 3, the total number of edges must be at least 3(y + t).
Therefore k + 2y \geq 3(y+t) \implies y \leq k - 3t \leq k - 3. So we cannot have performed more than k-3 cycle replacements.
Thus the total cost of all cycles in our solution is k + 2y which is at most k + 2(k-3) = 3k - 6.
TIME COMPLEXITY:
Part 1 of the solution takes O(n + k^2) time whereas part 2 requires the building of an adjacency matrix (O(n^2)) and a subsequent O(k^2) to reduce the cycles to vertex induced ones.
Thus the time complexity is O(k^2 + n^2 + m) = O(k^2 + n^2) per test case.
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 2'000;
const int MAX_M = 1'000'000;
vector<int> h[MAX_N + 1], g[MAX_N + 1];
int ptr[MAX_N + 1], instack[MAX_N + 1], adj[MAX_N + 1][MAX_N + 1], vis[MAX_M + 1];
void solve() {
int n, m, cnt = 0, tot = 0;
cin >> n >> m;
for (int i=1;i<=n;++i) {
g[i].clear(); h[i].clear(); ptr[i] = instack[i] = 0;
for (int j=1;j<=n;++j) adj[i][j] = 0;
}
vector<array<int, 3>> edges;
for (int i=0;i<m;++i) {
int u, v, w;
cin >> u >> v >> w;
if (w == 1) {
edges.push_back({u, v, w});
h[u].push_back(cnt);
h[v].push_back(cnt);
vis[cnt] = 0;
cnt++;
}
// 0 -> empty; 1 -> label 0; 2-> label 1
adj[u][v] = adj[v][u] = 1 + w;
g[u].push_back(v);
g[v].push_back(u);
if (u > v) swap(u, v);
}
stack<int> dfs;
vector<vector<int>> cycles;
for (int i=1;i<=n;++i) if (ptr[i] < (int)h[i].size()) {
dfs.push(i);
instack[i] = true;
while (!dfs.empty()) {
auto u = dfs.top();
while (ptr[u] < (int)h[u].size() && vis[h[u][ptr[u]]]) {
ptr[u]++;
}
if (ptr[u] >= (int)h[u].size()) {
if (u != i) {
cout << "-1\n";
return;
}
dfs.pop();
continue;
}
auto e = h[u][ptr[u]];
vis[e] = 1;
auto v = edges[e][0] ^ edges[e][1] ^ u;
ptr[u]++;
if (instack[v]) {
vector<int> cycle;
while (cycle.empty() || cycle.back() != v) {
cycle.push_back(dfs.top());
instack[dfs.top()] = false;
dfs.pop();
}
int fsz = cycle.size();
for (int ii=0;ii<fsz;++ii) {
int u = cycle[ii], v = cycle[(ii+1)%fsz];
}
cycles.push_back(cycle);
}
dfs.push(v);
instack[v] = true;
}
}
vector<vector<int>> answer;
for (auto &c : cycles) {
int sz = c.size(), cursz = 2;
vector<int> f;
f.push_back(c[0]);
f.push_back(c[1]);
for (int i=2;i<sz;++i) {
int j = (int)f.size() - 2;
while (j >= 0) {
while (j >= 0 && adj[c[i]][f[j]] == 0) {
--j;
}
if (j < 0) break;
vector<int> cyc;
cyc.push_back(c[i]);
while (f.back() != f[j]) {
cyc.push_back(f.back());
f.pop_back();
}
cyc.push_back(f[j]);
answer.push_back(cyc);
tot += cyc.size();
--j;
}
f.push_back(c[i]);
}
}
cout << answer.size() << '\n';
for (auto &c : answer) {
cout << c.size() << ' ';
for (auto &u : c) cout << u << " ";
cout << '\n';
}
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Tester's Solution
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
auto solve = [&] () {
int n, m; cin >> n >> m;
vector<bitset<1001>> edge(n);
vector<vector<pair<int, int>>> adj(n);
vector<int> par(n);
int ones = 0;
for (int i = 0; i < m; ++i) {
int u, v, w; cin >> u >> v >> w;
assert(u != v);
--u, --v;
edge[u][v] = edge[v][u] = 1;
ones += w;
if (!w) continue;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
par[u] ^= 1, par[v] ^= 1;
}
if (*max_element(begin(par), end(par)) == 1) {
cout << -1 << '\n';
return;
}
vector<int> deg(n), its(n), used(m), mark(n);
auto eulerCircuit = [&] (int src) {
vector<int> st = {src}, ret;
while (!st.empty()) {
int x = st.back(), y, e, &it = its[x], end = adj[x].size();
mark[x] = 1;
if (it == end) {
ret.push_back(x);
st.pop_back();
continue;
}
tie(y, e) = adj[x][it++];
if (!used[e]) {
deg[x]--, deg[y]++;
used[e] = 1;
st.push_back(y);
}
}
reverse(begin(ret), end(ret));
return ret;
};
vector<int> euler;
for (int i = 0; i < n; ++i) {
if (mark[i]) continue;
auto ret = eulerCircuit(i);
for (int x : ret) euler.emplace_back(x);
}
vector<vector<int>> cycles;
mark.assign(n, 0);
vector<int> st;
for (int x : euler) {
if (!mark[x]) st.push_back(x), mark[x] = 1;
else {
cycles.emplace_back();
while (1) {
cycles.back().push_back(st.back());
if (cycles.back().back() == x) break;
mark[st.back()] = 0;
st.pop_back();
}
}
}
vector<vector<int>> ans;
while (!cycles.empty()) {
auto cyc = cycles.back(); cycles.pop_back();
int s = cyc.size();
bool chord = false;
for (int i = 2; !chord and i < s; ++i) {
for (int j = i-2; j >= 0; --j) {
if (i == s-1 and j == 0) continue;
if (edge[cyc[i]][cyc[j]] == 0) continue;
chord = true;
ans.emplace_back();
for (int k = j; k <= i; ++k) ans.back().emplace_back(cyc[k]);
cycles.emplace_back();
for (int k = 0; k <= j; ++k) cycles.back().emplace_back(cyc[k]);
for (int k = i; k < s; ++k) cycles.back().emplace_back(cyc[k]);
break;
}
}
if (chord) continue;
ans.emplace_back(cyc);
}
int tot = 0;
cout << size(ans) << '\n';
for (auto cyc : ans) {
cout << size(cyc) << ' ';
for (int x : cyc) cout << x+1 << ' ';
cout << '\n';
tot += size(cyc);
}
assert(tot <= 3*ones);
};
int t; cin >> t;
for (int test = 1; test <= t; ++test) {
solve();
}
}