BALNET - Editorial

If you prefer a video explanation: BALNET Video Solution - February Long Challenge 2020

PROBLEM LINK:

Practice
Div-1 Contest

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.

diagram2

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.

Cases




There are actually more final states, but we only need to consider these four.

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 :slight_smile:

7 Likes

anxious to read the detailed version. By the way…really great editorials so far!

3 Likes

For those who haven’t seen it, I have created a video solution as a substitute while I finish writing up the editorial.

2 Likes

I think video solutions is a much better way to understand hard problems, Thanks :slight_smile:

3 Likes

Editorial finished and updated!

3 Likes

@tmwilliamlin Really great tutorials. Appreciate it. But I really liked the way to solve the subtask of this problem using max flow. If possible, you should explain the intention behind constraints and just the solution for subtasks as well. Thanks

3 Likes

I actually thought that the quadratic subtask was for badly implemented intended solutions. Do you mind explaining how this becomes a max-flow problem?

Consider N nodes and 2*M nodes for edges(dummy nodes for limiting flow through that edge by 1), from each of this edge node, we attach both possibility on left and right side. Look at the picture to get better understanding. If max flow >= N+1/2 , then answer exist and we can trace it by checking flow along edges. SOLUTION : CodeChef: Practical coding for everyone

I was able to get the worst running time of 7 sec for given problem with optimised dinic’s solution.

1 Like

It can be reduced to 2*m+2 nodes, but doesn’t make a big difference

3 Likes

@carre could you elaborate on how?

Yes, but it doesn’t worth big effort to implement it, you won’t go any further than with nik_84 solution. Anyway…
As you can see in nik’s posted image, you can simply remove the nodes 1 to 4 and for each of the N wires add an edge from source to the in-node asociated to the first balancer that node is connected to. For example, in the image you would add 2 edges from source to 5 and one edge from source to 6. If any wire is not connected to a balancer you can simply not consider that wire an reduce the pretended max_flow by one.
So, the number of nodes of the graph is 2*M (two nodes for each balancer) plus 2 more nodes for source and destination.

If you’re still interested in this partial solution, you can check a cleaner version than the one I submitted during the contest here.

Thanks a lot for sharing. Actually sharing this is quite important. Thanks a lot again :slight_smile:

1 Like

I see, Thanks for sharing :smiley: