If you prefer a video explanation: BALNET Video Solution - February Long Challenge 2020
PROBLEM LINK:
Author: Alexey Zayakin
Tester: Radoslav Dimitrov
Editorialist: William Lin
DIFFICULTY:
Hard
PREREQUISITES:
Observations
PROBLEM:
There are N wires, all initially alive. There are M balancers which much be processed in order. Balancer i can be set to direct from wire x_i to wire y_i or from wire y_i to wire x_i. We start with N tokens on the left, one on each wire. Then, the tokens start moving to the left. Whenever a token encounters a balancer, it moves to the wire pointed to by the balancer. Direct the balancers so that at least \frac{N}{2} wires have a token in the end.
QUICK EXPLANATION:
We will use induction to prove that after any set of balancers, we can partition the wires into \frac{N}{2} pairs, and for each pair, we can choose, independently of other wires, exactly one wire in the pair to have a token. This also gives us the strategy to set the balancers.
EXPLANATION:
Let’s call a wire alive if a token starting from the left can reach the wire after all of the balancers. Otherwise, the wire is dead. Our goal is to set the balancers so that at least \frac{N}{2} wires will be alive in the end.
In the sample test case, if we configure the balancers as shown above, wires 2, 4, and 5 will be alive while wires 1 and 3 will be dead.
Let’s consider working with small cases and seeing which combinations of alive and dead wires we can achieve in the end.
In the picture above, the number 1 means alive and the number 0 means dead. Each of the 4 columns represents a possible result of the wires. Depending on the direction of the top balancer, we have two possible results for the top pair: Either the first wire will be alive or the second wire will be alive. Similarly, we have two possible results for the bottom pair. These pairs are independent of each other, so we have four possible results.
With that set of balancers, we can easily obtain \frac{N}{2} alive wires. What if there are more balancers?
If we add an additional balancer between the top pair of wires, we can just treat the two balancers on the top pair of wires as one: We can set their directions to be the same, or we can completely ignore the first balancer.
The more interesting case is when we add a balancer between the two pairs. We can do some casework to figure out which final states are possible.
From the casework above, we know that we can obtain the final states in the picture below:
Is there anything special about these final states? Those are the same final states as if we had two balancers arranged like:
So, whenever we add a new balancer which connects two different pairs, we can perform the following transformation:
This shows that for even N, we will always have a pairing of the wires, such that we can choose any wire in each pair to be alive. This implicitly shows that we can always have \frac{N}{2} alive wires.
Proof
At the start, we can pair the wires arbitrarily, such as pairing wire i with i+1 for all odd i. It’s obvious that we can choose any wire in each pair to be alive.
Then, assume that there exists a pairing for the first k balancers. Consider the k+1-th balancer. If it connects wires already in the same pair, the pairing doesn’t change. Otherwise, we apply the transformation described above to obtain a new pairing. So there also exists a pairing for the first k+1 balancers.
We have shown that a solution always exist, but how do we actually find the solution (the directions of the balancers)?
Let p_i be the wire paired with wire i. First, we will find a possible final pairing p first by processing the balancers from left to right. We know that we can choose any wire from each pair to be alive, so let’s arbitrarily set one wire in each pair to be alive. We will work backward to find the state of the wires after M-1 balancers, the state of the wires after M-2 balancers, and so on. While doing so, we will be able to determine the directions of the balancers.
Note that during this process, we also need the pairing p after balancer i for each i. We will store the changes we make to p while processing the balancers from left to right (to find the final pairing) and recover p as we process the balancers from right to left.
So let’s say, in one iteration, that we already processed the last M-i balancers, and now we have the state of the wires after the first i balancers. Finding the direction of the i-th balancer is simple: we point balancer i to x_i if x_i is alive and y_i otherwise.
Now, we need to find the state of the wires after the first i-1 balancers. There are a few cases for this.
Cases
If balancer i connects two wires in the same pair, it doesn’t matter which wire in the pair is alive, so, in this case, we don’t need to change the states of any wires.
If balancer i connects two wires from two different pairs, we may need to change the states of x_i, y_i, p_{x_i}, and p_{y_i}. The states of those wires before balancer i can be found according to the states after balancer i (you can refer to the picture for the each of the four cases above). Note that instead of using something like four if statements, there is an easier way to write this, which can be found in my implementation.
We are still missing the case when N is odd, but fortunately, everything is still pretty much the same.
Instead of \frac{N}{2} pairs, we will have \frac{N-1}{2} pairs and a single wire. In addition to guaranteeing that we can choose any wire in each pair to be alive, we also need the single wire to be alive. Then, we will have at least \frac{N}{2} alive wires.
The additional case we need to consider is when a balancer connects a single wire with a wire in a pair.
Case
The possible states of the wires is shown below:
We add a new balancer:
Two of the final states we can achieve with this new balancer is shown below:
Note that these two states are the same as if we removed the original balancer:
So, when we add a new balancer between a single wire and a pair, we will still obtain a valid pairing after the balancer.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int MX = 1000000;
int x[MX], y[MX], p[MX];
bool active[MX];
char ans[MX + 1];
int main() {
int T;
ignore = scanf("%d", &T);
while (T--) {
int n, m;
ignore = scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
ignore = scanf("%d %d", x + i, y + i);
x[i]--;
y[i]--;
}
fill(p, p + n, -1);
vector<tuple<int, int, int>> changes;
auto change = [&](int t, int i, int val) {
changes.emplace_back(t, i, p[i]);
p[i] = val;
};
for (int i = m - 1; i >= 0; i--) {
int a = p[x[i]], b = p[y[i]];
if (y[i] == a) continue;
if (a != -1 && b != -1) {
change(i, a, b);
change(i, b, a);
}
else {
if (a != -1) change(i, a, -1);
if (b != -1) change(i, b, -1);
}
change(i, x[i], y[i]);
change(i, y[i], x[i]);
}
for (int i = 0; i < n; i++) active[i] = p[i] < i;
for (int i = 0; i < m; i++) {
assert(active[x[i]] == false || active[y[i]] == false);
while (changes.empty() == false && get<0>(changes.back()) == i) {
int i, val;
tie(ignore, i, val) = changes.back();
changes.pop_back();
p[i] = val;
}
ans[i] = '^';
int a = p[x[i]], b = p[y[i]];
if (y[i] != a) {
if (a != -1 && b != -1) {
ans[i] = active[a] ? 'v' : '^';
}
else {
if (a != -1) ans[i] = 'v';
if (b != -1) ans[i] = '^';
}
}
if (ans[i] == '^') {
active[x[i]] = active[x[i]] || active[y[i]];
active[y[i]] = false;
}
else {
active[y[i]] = active[y[i]] || active[x[i]];
active[x[i]] = false;
}
}
ans[m] = 0;
printf("%s\n", ans);
}
return 0;
}
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);
int read_int();
int n, m;
int x[MAXN << 1], y[MAXN << 1];
int match[MAXN];
void read() {
n = read_int();
m = read_int();
for(int i = 0; i < m; i++) {
x[i] = read_int();
y[i] = read_int();
}
}
int dir[MAXN << 1], last[MAXN];
// dir[i] = 0 means x[i] -> y[i] (down)
// dir[i] = 1 means x[i] <- y[i] (up)
inline bool is_up(int i, int x) {
return ::x[i] == x;
}
pair<int, int> child_gates[MAXN << 1];
bool to_prop[MAXN << 1];
void propagate(int g) {
to_prop[g] = false;
if(g < m) {
return;
}
int gate_up = child_gates[g].first;
int gate_down = child_gates[g].second;
if(dir[g]) {
if(is_up(gate_up, x[g])) dir[gate_up] = 1;
else dir[gate_up] = 0;
if(is_up(gate_down, y[g])) dir[gate_down] = 0;
else dir[gate_down] = 1;
} else {
if(is_up(gate_up, x[g])) dir[gate_up] = 0;
else dir[gate_up] = 1;
if(is_up(gate_down, y[g])) dir[gate_down] = 1;
else dir[gate_down] = 0;
}
propagate(gate_up);
propagate(gate_down);
}
void solve() {
// We will always keep match[match[x]] = x, and from every match either x or match[x] will reach the end
// This means that we will have at least ceil(n / 2) tokens that will reach the end
for(int i = 1; i <= n; i++) {
match[i] = i;
}
int additional_gates_cnt = m;
for(int i = 0; i < m; i++) {
// We will always match X and Y here
dir[i] = 0;
to_prop[i] = true;
if(match[x[i]] == x[i] && match[y[i]] == y[i]) { // Both X and Y are solo matches
match[y[i]] = x[i];
match[x[i]] = y[i];
} else if(match[y[i]] == y[i]) { // Y is a solo match, but X isn't
// We need to change direction of last[x[i]]
if(is_up(last[x[i]], x[i])) dir[last[x[i]]] = 0;
else dir[last[x[i]]] = 1;
match[match[x[i]]] = match[x[i]];
match[x[i]] = y[i];
match[y[i]] = x[i];
} else if(match[x[i]] == x[i]) { // X is a solo match, but Y isn't
// We need to change direction of last[y[i]]
if(is_up(last[y[i]], y[i])) dir[last[y[i]]] = 0;
else dir[last[y[i]]] = 1;
match[match[y[i]]] = match[y[i]];
match[x[i]] = y[i];
match[y[i]] = x[i];
} else {
if(x[i] == match[y[i]]) {
last[x[i]] = i;
last[y[i]] = i;
continue;
}
int g = additional_gates_cnt++;
dir[g] = 0;
to_prop[g] = true;
x[g] = min(match[x[i]], match[y[i]]);
y[g] = max(match[x[i]], match[y[i]]);
child_gates[g] = {last[x[g]], last[y[g]]};
to_prop[last[x[g]]] = false;
to_prop[last[y[g]]] = false;
last[x[g]] = g;
last[y[g]] = g;
match[x[i]] = y[i];
match[y[i]] = x[i];
match[x[g]] = y[g];
match[y[g]] = x[g];
}
last[x[i]] = i;
last[y[i]] = i;
}
for(int i = additional_gates_cnt - 1; i >= 0; i--) {
if(to_prop[i]) propagate(i);
}
for(int i = 0; i < m; i++) {
if(!dir[i]) cout << "v";
else cout << "^";
}
cout << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
T = read_int();
while(T--) {
read();
solve();
}
return 0;
}
const int maxl = 100000;
char buff[maxl];
int ret_int, pos_buff = 0;
void next_char() { if(++pos_buff == maxl) fread(buff, 1, maxl, stdin), pos_buff = 0; }
int read_int()
{
ret_int = 0;
for(; buff[pos_buff] < '0' || buff[pos_buff] > '9'; next_char());
for(; buff[pos_buff] >= '0' && buff[pos_buff] <= '9'; next_char())
ret_int = ret_int * 10 + buff[pos_buff] - '0';
return ret_int;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
const int mxN=1e6;
int t, n, m, x[mxN], y[mxN], p[mxN];
array<int, 2> r[mxN][4];
bool b[mxN];
char ans[mxN];
void solve() {
cin >> n >> m;
//set initial pairing
for(int i=0; i<n/2; ++i) {
p[2*i]=2*i+1;
p[2*i+1]=2*i;
}
//single
if(n&1)
p[n-1]=n-1;
//find final pairing
for(int i=0; i<m; ++i) {
cin >> x[i] >> y[i], --x[i], --y[i];
//store the changes to p so we can recover them later
r[i][0]={x[i], p[x[i]]};
r[i][1]={y[i], p[y[i]]};
r[i][2]={p[x[i]], x[i]};
r[i][3]={p[y[i]], y[i]};
if(p[y[i]]==y[i])
swap(x[i], y[i]);
if(p[x[i]]==x[i]) {
//x[i] is single
//p[y[i]] will be the new single
p[p[y[i]]]=p[y[i]];
} else if(p[x[i]]^y[i]) {
int px=p[x[i]], py=p[y[i]];
//pair up px and py
p[px]=py;
p[py]=px;
}
//pair up x[i] and y[i]
p[x[i]]=y[i];
p[y[i]]=x[i];
}
//find final states
for(int i=0; i<n; ++i)
b[i]=i<=p[i];
//go back and find the directions
for(int i=m-1; ~i; --i) {
//recover p
for(int j=0; j<4; ++j)
p[r[i][j][0]]=r[i][j][1];
//set direction of balancer
ans[i]=b[x[i]]^x[i]>y[i]?'^':'v';
//update the states of the wires
if(p[x[i]]==x[i]) {
b[x[i]]=1;
b[y[i]]=0;
} else if(p[x[i]]^y[i]) {
b[x[i]]=b[p[y[i]]];
b[y[i]]=b[p[x[i]]];
}
}
for(int i=0; i<m; ++i)
cout << ans[i];
cout << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while(t--)
solve();
}
SUBTASKS:
There is an interesting solution to several of the subtasks using Maximum Flow (thanks to @nik_84 for mentioning it). We can start with N source nodes representing the wires, each having an output flow of 1. Whenever we have a balancer, we limit wires x_i and y_i to have a flow of at most 1 combined. We should create 2 nodes representing the balancer, with the nodes for wires x_i and y_i directing into the first node, and the first node directing into the second node with a capacity of 1. Then, the new nodes for x_i and y_i will be the second node of the balancer. You can see the comment below for a picture of an example.
Please give me suggestions if anything is unclear so that I can improve. Thanks 
