R. Zoo Management
46th Annual hosted by ICPC World Championship AASTMT Problem R Zoo Man...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
46th Annual hosted by
ICPC World
Championship AASTMTProblem R Zoo Management Time limit: 5 seconds When managing a zoo, you sometimes want to move the animals between enclosures. You might figure out that the zebras will enjoy the spacier enclosure currently occupied by the penguins, while the penguins might want to move to the colder enclosure where the koalas currently live; and koalas will move to an empty enclosure that can be filled up with eucalyptus. So, you would move the koalas first, to free up the colder enclosure, then move the penguins there, and finally move the zebras. The way you move animals is by using special tunnels that con- A picture of a zoo with a camel, a donkey and (part of) a goat. nect the enclosures — you do not want the animals to move out- side, both because of the risk that they will be scared, and because of the risk that they might run away and hurt themselves. Unfortunately, you have acquired more animals recently, and all the enclosures are now full, which makes moving animals around much harder. Imagine, for instance, that the koalas were to move to the former zebra enclosure — you cannot move any set of animals first. Instead, what you learned to do, is to move the animals at the same time — the zebras, koalas and penguins start moving down different tunnels at the same time, and arrive at their new enclosures at the same time — and thus they never meet. Note that you cannot just swap the animals in two connected enclosures this way (because they would meet in the tunnel and become scared). So, now you have a puzzle. You have a list of enclosures, each with an animal type inside; some of those enclosures are connected by tunnels. You can, any number of times, choose some set of animals and move each one to an enclosure adjacent by tunnel, as long as the animal in that enclosure is also moved as the part of the same move, and no tunnel is used more than once as a part of the same move. You also have your vision of the perfect way to position the animals. Is it possible to do so, in a series of moves?
Input
The first line of the input consists of two integers n (1 ≤ n ≤ 4 · 105 ) and m (0 ≤ m ≤ 4 · 105 ), indicating the number of enclosures and tunnels. Then follow n lines, the ith of which contains two integers bi (1 ≤ bi ≤ 106 ) and ei (1 ≤ e ≤ 106 ), indicating the type of animal that is in enclosure i at the beginning, and the type of animal that you want to be in enclosure i after all the moves. You may assume that e1 , . . . , en is a permutation of b1 , . . . , bn . Then follow m lines describing the tunnels. Each line contains two integers x and y (1 ≤ x < y ≤ n), indicating that enclosures x and y are connected by a two-way tunnel. No two enclosures are connected by more than one tunnel.
Output
If it is possible to move the animals so that every enclosure contains the desired animal type, output possible. Otherwise, output impossible.
World Finals | ICPC 2023 Luxor
46th Annual hosted by
ICPC World
Championship AASTMTSample Tests
3 3
1 4
4 7
7 1
1 2
2 3
1 3possible2 1
1 2
2 1
1 2impossible5 6
10 40
20 30
30 50
40 20
50 10
1 2
2 3
1 3
3 4
3 5
4 5possible4 4
10 10
10 20
20 10
20 20
1 2
2 3
3 4
1 4impossibleEditorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Key Observations
A bridge can never be used in any move, because no cycle contains a bridge. So animals never cross bridges, and every connected component after removing bridges is independent.
Inside one bridge-free component there are three qualitatively different cases:
the component is a single simple cycle;
the component is a cactus made of several simple cycles sharing only vertices;
some edge belongs to more than one cycle.
On a single simple cycle, the only possible operation is a rotation of that cycle, so the target sequence must be a cyclic shift of the initial sequence.
If some edge belongs to more than one cycle, then one can realize arbitrary swaps and therefore arbitrary permutations of the vertices in that component.
If the component is a cactus with more than one cycle, then all even permutations are possible. If at least one cycle has even length, that cycle itself is an odd permutation, so in fact all permutations become possible.
Algorithm
Find all bridges and remove them.
For each remaining connected component:
first compare the multisets of initial and target animal types inside the component;
if the component is a simple cycle, build the cyclic order of vertices and test cyclic equivalence of the two label sequences;
otherwise run one DFS inside the component and count, for each tree edge, how many back edges cover it.
If some tree edge is covered by more than one back edge, then some edge lies on multiple cycles, so the component allows all permutations.
Otherwise the component is a cactus. Check whether one of its cycle lengths is even:
if yes, all permutations are possible;
if not, only even permutations are possible.
In the even-only case, parity matters only when all labels in the component are distinct. Then compute the parity of the permutation sending the initial labeling to the target labeling. enumerate
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
No animal can ever cross a bridge.
Proof.
Each move is a union of directed cycles. A bridge belongs to no undirected cycle, so it cannot be used in any move. Hence animals remain forever inside the same connected component of the graph after bridges are removed. □
Lemma 2.
If a bridge-free component is a simple cycle, then the reachable labelings are exactly the cyclic shifts of its current labeling.
Proof.
The only cycle present in the component is the whole component itself, so every move rotates the labels by one step clockwise or counterclockwise. Repeating such moves gives exactly all cyclic shifts and nothing else. □
Lemma 3.
If a bridge-free component contains an edge that lies on more than one cycle, then every permutation of its vertices is achievable.
Proof.
The standard argument used in the official sketch shows that three edge-disjoint paths between two vertices allow a transposition of arbitrary labels inside that subgraph. Combining such local swaps with the available cycle rotations generates the full symmetric group on the component. □
Lemma 4.
If a bridge-free component is a cactus with more than one cycle, then every even permutation is achievable. If one of its cycles has even length, then every permutation is achievable.
Proof.
For two adjacent cycles in a cactus, the commutator \[ aba^{-1}b^{-1} \] acts as a 3-cycle on labels, so the alternating group is generated. Thus every even permutation is reachable.
A cycle of length $L$ is a permutation of sign $(-1)^{L-1}$. Hence an even-length cycle is an odd permutation. Once both all even permutations and one odd permutation are available, the full symmetric group is generated. □
Theorem.
The algorithm outputs
possibleexactly when the target arrangement can be achieved.Proof.
By Lemma 1, components after bridge removal are independent, so it is necessary and sufficient to solve each one separately.
If a component is a simple cycle, Lemma 2 gives the exact criterion. Otherwise, the DFS cover counts tell us whether some edge lies on multiple cycles. In that case Lemma 3 applies and only multiset equality is needed. If not, the component is a cactus, so Lemma 4 tells us whether all permutations or only even permutations are available.
In the even-only case, when some label appears at least twice, swapping two equal labels changes the permutation parity without changing the final arrangement, so parity imposes no restriction. If all labels are distinct, the parity of the unique permutation from the initial labeling to the target labeling is the exact remaining condition. Therefore the algorithm is correct. □
Complexity Analysis
Bridge finding and the later DFS traversals are linear. Comparing label multisets inside components requires sorting their labels, so the total running time is $O((n+m) + n \log n)$, and the memory usage is $O(n+m)$.
Implementation Notes
The code uses an iterative DFS for both bridge finding and cycle-structure analysis to avoid recursion-depth problems at $4 \cdot 10^5$ vertices and edges.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
namespace {
struct Edge {
int to = 0;
int id = 0;
};
struct Frame {
int v = 0;
int parent_edge = -1;
int it = 0;
};
vector<int> build_cycle_order(const vector<int>& verts, const vector<vector<Edge>>& graph,
const vector<char>& blocked) {
int start = verts[0];
int prev = -1;
int cur = start;
vector<int> order;
order.reserve(verts.size());
do {
order.push_back(cur);
int next = -1;
for (const Edge& e : graph[cur]) {
if (blocked[e.id]) {
continue;
}
if (e.to == prev) {
continue;
}
next = e.to;
break;
}
prev = cur;
cur = next;
} while (cur != start);
return order;
}
template <class T>
bool is_cyclic_shift(const vector<T>& a, const vector<T>& b) {
if (a.size() != b.size()) {
return false;
}
if (a.empty()) {
return true;
}
int n = static_cast<int>(b.size());
vector<int> pi(n, 0);
for (int i = 1; i < n; ++i) {
int j = pi[i - 1];
while (j > 0 && b[i] != b[j]) {
j = pi[j - 1];
}
if (b[i] == b[j]) {
++j;
}
pi[i] = j;
}
vector<T> text = a;
text.insert(text.end(), a.begin(), a.end());
int j = 0;
for (int i = 0; i < 2 * n - 1; ++i) {
while (j > 0 && text[i] != b[j]) {
j = pi[j - 1];
}
if (text[i] == b[j]) {
++j;
}
if (j == n) {
int pos = i - n + 1;
if (pos < n) {
return true;
}
j = pi[j - 1];
}
}
return false;
}
bool same_multiset(const vector<int>& verts, const vector<int>& start, const vector<int>& target) {
vector<int> a;
vector<int> b;
a.reserve(verts.size());
b.reserve(verts.size());
for (int v : verts) {
a.push_back(start[v]);
b.push_back(target[v]);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
return a == b;
}
bool even_permutation_possible(const vector<int>& verts, const vector<int>& start,
const vector<int>& target) {
unordered_map<int, int> freq;
freq.reserve(verts.size() * 2);
for (int v : verts) {
++freq[start[v]];
}
for (const auto& entry : freq) {
if (entry.second >= 2) {
return true;
}
}
unordered_map<int, int> target_pos;
target_pos.reserve(verts.size() * 2);
for (int i = 0; i < static_cast<int>(verts.size()); ++i) {
target_pos[target[verts[i]]] = i;
}
vector<int> perm(verts.size());
for (int i = 0; i < static_cast<int>(verts.size()); ++i) {
perm[i] = target_pos[start[verts[i]]];
}
vector<char> seen(verts.size(), false);
int cycles = 0;
for (int i = 0; i < static_cast<int>(verts.size()); ++i) {
if (seen[i]) {
continue;
}
++cycles;
int cur = i;
while (!seen[cur]) {
seen[cur] = true;
cur = perm[cur];
}
}
int parity = (static_cast<int>(verts.size()) - cycles) & 1;
return parity == 0;
}
void solve() {
int n, m;
cin >> n >> m;
vector<int> start(n), target(n);
for (int i = 0; i < n; ++i) {
cin >> start[i] >> target[i];
}
vector<vector<Edge>> graph(n);
for (int id = 0; id < m; ++id) {
int u, v;
cin >> u >> v;
--u;
--v;
graph[u].push_back({v, id});
graph[v].push_back({u, id});
}
vector<int> tin(n, 0), low(n, 0), parent(n, -1), parent_edge(n, -1);
vector<char> is_bridge(m, false);
int timer = 0;
for (int root = 0; root < n; ++root) {
if (tin[root] != 0) {
continue;
}
vector<Frame> stack;
stack.push_back({root, -1, 0});
parent[root] = -1;
parent_edge[root] = -1;
while (!stack.empty()) {
Frame& frame = stack.back();
int v = frame.v;
if (tin[v] == 0) {
tin[v] = low[v] = ++timer;
}
if (frame.it < static_cast<int>(graph[v].size())) {
Edge e = graph[v][frame.it++];
if (e.id == frame.parent_edge) {
continue;
}
int to = e.to;
if (tin[to] == 0) {
parent[to] = v;
parent_edge[to] = e.id;
stack.push_back({to, e.id, 0});
} else {
low[v] = min(low[v], tin[to]);
}
} else {
stack.pop_back();
if (parent[v] != -1) {
low[parent[v]] = min(low[parent[v]], low[v]);
if (low[v] > tin[parent[v]]) {
is_bridge[parent_edge[v]] = true;
}
}
}
}
}
vector<int> deg_non_bridge(n, 0);
for (int v = 0; v < n; ++v) {
for (const Edge& e : graph[v]) {
if (!is_bridge[e.id]) {
++deg_non_bridge[v];
}
}
}
vector<int> comp_id(n, -1);
vector<vector<int>> components;
for (int start_v = 0; start_v < n; ++start_v) {
if (comp_id[start_v] != -1) {
continue;
}
queue<int> q;
q.push(start_v);
comp_id[start_v] = static_cast<int>(components.size());
components.push_back({});
while (!q.empty()) {
int v = q.front();
q.pop();
components.back().push_back(v);
for (const Edge& e : graph[v]) {
if (is_bridge[e.id]) {
continue;
}
if (comp_id[e.to] == -1) {
comp_id[e.to] = comp_id[start_v];
q.push(e.to);
}
}
}
}
vector<char> seen(n, false);
for (const vector<int>& verts : components) {
if (!same_multiset(verts, start, target)) {
cout << "impossible\n";
return;
}
long long edge_count = 0;
bool all_deg_two = true;
for (int v : verts) {
edge_count += deg_non_bridge[v];
if (deg_non_bridge[v] != 2) {
all_deg_two = false;
}
}
edge_count /= 2;
if (edge_count == static_cast<long long>(verts.size()) && all_deg_two) {
vector<int> cycle = build_cycle_order(verts, graph, is_bridge);
vector<int> a;
vector<int> b;
a.reserve(cycle.size());
b.reserve(cycle.size());
for (int v : cycle) {
a.push_back(start[v]);
b.push_back(target[v]);
}
if (!is_cyclic_shift(a, b)) {
cout << "impossible\n";
return;
}
continue;
}
int root = verts[0];
vector<int> depth(n, -1), delta(n, 0), order;
vector<int> parent2(n, -1), parent_edge2(n, -1), iter(n, 0);
bool non_cactus = false;
bool has_even_cycle = false;
vector<int> stack;
stack.push_back(root);
depth[root] = 0;
while (!stack.empty()) {
int v = stack.back();
if (iter[v] == 0) {
order.push_back(v);
}
if (iter[v] < static_cast<int>(graph[v].size())) {
Edge e = graph[v][iter[v]++];
if (is_bridge[e.id] || e.id == parent_edge2[v]) {
continue;
}
int to = e.to;
if (depth[to] == -1) {
depth[to] = depth[v] + 1;
parent2[to] = v;
parent_edge2[to] = e.id;
stack.push_back(to);
} else if (depth[to] < depth[v]) {
++delta[v];
--delta[to];
int cycle_len = depth[v] - depth[to] + 1;
if ((cycle_len & 1) == 0) {
has_even_cycle = true;
}
}
} else {
stack.pop_back();
}
}
for (int i = static_cast<int>(order.size()) - 1; i >= 1; --i) {
int v = order[i];
if (delta[v] > 1) {
non_cactus = true;
}
delta[parent2[v]] += delta[v];
}
if (non_cactus || has_even_cycle) {
continue;
}
if (!even_permutation_possible(verts, start, target)) {
cout << "impossible\n";
return;
}
}
cout << "possible\n";
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2022/R-zoo-management/solution.texC++ implementationcompetitive_programming/icpc/2022/R-zoo-management/solution.cppStatement textcompetitive_programming/icpc/2022/R-zoo-management/statement.txtStatement PDFcompetitive_programming/icpc/2022/R-zoo-management/statement.pdfMetadatacompetitive_programming/icpc/2022/R-zoo-management/meta.jsonYear packetcompetitive_programming/icpc/2022/contest_problems.pdf