As the first problem in the contest, I read this problem first. The problem looked quite interesting, so I spent a bit of time on it before reading the other problems. I ended up immediately guessing the correct greedy, and submitted code that got 83 points, which very quickly became 100 points. I solved this before even attempting to think about the other problems.

The most restrictive element in $$$P$$$ is the one with the largest $$$P[i]$$$. It needs to be either the element with the largest $$$A[i]$$$ or largest $$$B[i]$$$. On the other hand, the least restrictive elements in $$$A$$$ and $$$B$$$ are the ones with the largest $$$A[i]$$$ and $$$B[i]$$$ respectively, since they can have any $$$P[i]$$$ and still fulfill the condition. Since both of these indices give the same use, we should focus on $$$P[i] - i$$$ to determine which one gets the largest $$$P[i]$$$. Clearly, to minimise $$$P[i] - i$$$, we should choose the larger of the 2. Now, notice that we have 1 less element to deal with and a similar problem left on our hands. We can repeat this process again with the new largest $$$A[i]$$$ and $$$B[i]$$$.

This motivates the full greedy solution: Assign the values of $$$P$$$ to the indices in decreasing order of $$$P[i]$$$. While there are still unchosen elements, let $$$x$$$ be the index with the largest $$$A[x]$$$ amongst all unchosen indices, and let $$$y$$$ be the index with the largest $$$B[y]$$$ amongst all unchosen indices. If $$$x = y$$$, assign the currently largest unused value of $$$P[i]$$$ to $$$x$$$. Otherwise, pick the larger of the 2 and assign the largest unused $$$P[i]$$$ to it.

Let's look at the sample testcase for an example. We have $$$A = [3, 0, 4, 1, 2]$$$, $$$B = [0, 3, 2, 4, 1]$$$. As our algorithm goes, we first find the element that we will assign $$$P[i] = 4$$$ to. $$$x = 2$$$ and $$$y = 3$$$, since $$$A[2] = 4$$$ and $$$B[3] = 4$$$. $$$y$$$ is bigger, so we set $$$P[y] = 4$$$ (i.e. $$$P[3] = 4$$$).

On the next run, we are assigning $$$P[i] = 3$$$. Now, $$$x = 2$$$ and $$$y = 1$$$, since $$$A[0] = 4$$$ and $$$B[1] = 3$$$. Now $$$x$$$ is bigger, so we set $$$P[2] = 3$$$.

By continuing the process, every element will get assigned a value.

This algorithm can be proven to work using a simple exchange argument. At any step in the algorithm, since there are only 2 valid choices for the index that takes on $$$P[i]$$$ ($$$x$$$ and $$$y$$$), if the algorithm chose one of them and it was unoptimal, the other one must be used in an optimal solution. However the rest of the algorithm continues as usual and in the end, swapping the values of $$$P[x]$$$ and $$$P[y]$$$ that we had would not make the result any worse. More formal writing is left as an exercise to the reader.

To implement this, we sort the indices by $$$A[i]$$$ and $$$B[i]$$$ in 2 separate arrays, and maintain 2 pointers pointing to the largest element with an undetermined $$$P[i]$$$. We also keep an array representing whether each index has its $$$P[i]$$$ determined yet.

Note that the sorting here needs to be done using counting sort, since permutations can be sorted in $$$O(N)$$$ and the problem setter successfully set tight enough limits ($$$N$$$ up to 5 million), to the point where std::sort fails the time limit. The overall time complexity should be $$$O(N)$$$.

My code in contest is as follows:

#include "exam.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m<h?1:-1))
#define jloop(m, h) for (auto j = m; j != h; j += (m<h?1:-1))
#define kloop(m, h) for (auto k = m; k != h; k += (m<h?1:-1))
#define pll pair<ll, ll>

int minimum_dissatisfaction(int N, vector<int> A, vector<int> B) {
	ll n = N;
	pll a[n], b[n];
	iloop(0, n) a[n - A[i] - 1] = {A[i], i}, b[n - B[i] - 1] = {B[i], i};
	ll ca = 0, cb = 0, cans = 0;
	bool used[n];
	memset(used, 0, sizeof(used));
	iloop(0, n) {
		while (ca < n && used[a[ca].second]) ca++;
		while (cb < n && used[b[cb].second]) cb++;
		if (cb == n || (ca < n && a[ca].second > b[cb].second)) {
			used[a[ca].second] = 1;
			cans = max(cans, (n-i) - (a[ca].second + 1));
		}
		else {
			used[b[cb].second] = 1;
			cans = max(cans, (n-i) - (b[cb].second + 1));
		}
	}
	return cans;
}

This problem was quite interesting, having 2 parts which I could not determine whether they were related. After the contest, errorgorn informed me that the rankings and scores used in the statement (go check it out) were actually taken from last year's IOI. After some digging, here are the actual sources of the scores:

• All 4 members on the scoreboard with country "Singapore" correspond to last year's Korea team.
• The first 2 members of team "Malaysia" correspond to the 2 gold medalists from last year's Singapore team.
• The last member of team "Malaysia" corresponds to Malaysia team's gold medalist last year.
• The 2 members of team "Indonesia" are from team Hungary and Taiwan respectively.

This was interesting to say the least. The problem itself is not bad, and the parts felt similar yet different enough in idea to make this a cool problem.

For the rest of the problem, define $$$f_i(x)$$$ as the number of people up to person $$$i$$$ (zero-indexed) with rank $$$x$$$. For convenience, let $$$f_{-1}(x) = 0$$$ for all $$$x$$$.

We shall start with part (a). The first observation is as follows: If person $$$i$$$ with country rank $$$x$$$ has some person $$$j$$$ in front of them who must be in the same country, then there must be some person $$$i$$$ with country rank $$$x-1$$$ in front of them who must be in the same country.

A quick idea of the proof would be that one can swap the country of person $$$i$$$ and some other people in the same country to change person $$$j$$$. For the formal proof, suppose otherwise. Then there must be at least 2 possibilities of persons $$$a$$$ and $$$b$$$, both with country rank $$$x-1$$$. Suppose without loss of generality person $$$i$$$ is in the same country as person $$$a$$$ in some construction. Then consider swapping the countries of everyone in person $$$a$$$'s country with a worse rank that $$$x-1$$$ and everyone in person $$$b$$$'s country with a worse rank than $$$x-1$$$. One still gets a valid configuration of countries, however person $$$i$$$ has now switched countries and has a different person $$$j$$$ in front of them, a contradiction since person $$$j$$$ is determined.

To continue, consider processing person $$$i$$$ with country rank $$$x$$$ and determining which people in front of them must be from the same country as them. From the observation, it is sufficient to determine the person with rank $$$x-1$$$ (if there exists any) since we can mark them as the same country and in the end, count the number of people connected together (this calls for DSU / UFDS to keep track of who must be together). Consider $$$f_{i-1}(x-1) - f_{i-1}(x)$$$, which is the number of people with country rank $$$x-1$$$ which have not been picked by someone with a country rank $$$x$$$. It is guaranteed to be at least 1 since a valid ranking must exist. If $$$f_{i-1}(x-1) - f_{i-1}(x) \gt 1$$$, there are at least 2 possible people with country rank $$$x-1$$$ who are in the same country. Thus $$$f_{i-1}(x-1) - f_{i-1}(x) = 1$$$ is necessary.

It is, however, not sufficient. Consider a case where the country ranks are $$$[0, 0, 1, 1]$$$. For the last person, $$$f_2(0)-f_2(1)=2-1=1$$$, however it is still possible for them to be in the same country as either one of the 0s. After some thinking and/or guessing, we obtain that $$$f_{i-1}(x-1) - f_{i-1}(x) = 1$$$ must hold, and the previous occurrence of country rank $$$x-1$$$ must be closer than the previous occurrence of country rank $$$x$$$. Another way of looking at this is that if $$$f_{i-1}(x-1) - f_{i-1}(x)$$$ ever exceeds 1, anyone following with country rank $$$x$$$ will not have a guaranteed partner until $$$f_{i-1}(x-1) - f_{i-1}(x)$$$ "resets" to 0.

As mentioned earlier, we can use a UFDS / DSU to maintain relationships of who is in the same country. In my code prog denotes $$$f_{i-1}(x) - f_{i-1}(x+1)$$$ while rs denotes whether the values of prog have been reset to 0. There is the special case of someone with country rank $$$0$$$.

#include "country.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m<h?1:-1))
#define jloop(m, h) for (auto j = m; j != h; j += (m<h?1:-1))
#define kloop(m, h) for (auto k = m; k != h; k += (m<h?1:-1))
#define pll pair<ll, ll>
ll par[1000005], sz[1000005];
ll n, cans, tmp;
ll find(ll x) {
	return (x == par[x] ? x : par[x] = find(par[x]));
}
void merge(ll x, ll y) {
	x = find(x), y = find(y);
	if (x == y) return;
	if (sz[x] < sz[y]) swap(x, y);
	par[y] = x;
	sz[x] += sz[y];
}
long long count_same_country(int N, vector<int> country_rank) {
	n = N, cans = 0;
	ll prog[n], a[n], prv[n];
	bool rs[n];
	iloop(0, n) a[i] = country_rank[i], par[i] = i, sz[i] = 1, prog[i] = 0, rs[i] = 1;
	iloop(0, n) {
		if (a[i]) {
			if (prog[a[i]-1] == 1 && rs[a[i]-1]) merge(i, prv[a[i]-1]);
			prog[a[i]-1]--;
			if (prog[a[i]-1] == 0) rs[a[i]-1] = 1;
		}
		prog[a[i]]++;
		if (prog[a[i]] == 2) rs[a[i]] = 0;
		prv[a[i]] = i;
	}
	iloop(0, n) if (par[i] == i) cans += sz[i] * (sz[i] - 1) / 2;
	return cans;
}

For part (b), it helps to consider when 2 people cannot be in the same country. There are 3 possibilities:

• The person in front has a country rank at least that of the person behind.
• There are not enough people in between that can form the chain of people in the same country with successive country ranks.
• The person in front is forced to be connected to someone else instead of that person, like in the scenario $$$[0, 1, 0, 1]$$$ where the last person cannot be with the first person.

The first 2 cases seem reasonable to handle. The first case contributes a lower bound to what country ranks a new person must be to be in the same country, while the second case seems to contribute an upper bound. It turns out that the third case also contributes a lower bound!

The third case borrows a similar idea from part (a): When $$$f_{i}(x-1) - f_{i}(x) = 0$$$, everyone up to that point with country rank $$$x-1$$$ is forced to have the next person from the same country to be indexed at most $$$i$$$. Usefully, $$$f_i(x)$$$ is monotone decreasing on $$$x$$$.

It can be shown (with many details, unfortunately not by me) that these conditions are necessary and sufficient for 2 people to be forced into different countries. In contest, I first implemented a $$$O(N^2)$$$ solution to verify the claim (it gave 21 points on (b)). Processing everyone in increasing order of rank, I assign everyone a range [lh, rh] where a person can potentially share a country with someone new being processed if the country rank of the new person lies in the range. For the 3 possibilities,

• At the start lh = rh = country_rank[i]+1
• If some person with country rank rh shows up, increase rh by 1
• If the count of $$$f_i(lh) - f_i(lh+1)$$$ reaches 0, increment lh

This is easier to check from the perspective of the new person being processed:

• For anyone with rh as the current country rank, increment it
• If the increase in country rank results in $$$f_i(lh) - f_i(lh+1)$$$ where lh + 1 = country_rank[i], increment all such $$$lh$$$

Then for each person, the number of people in front who cannot be in the same country is the number of people whose range does not include the country rank.

The code for this partial solution is as follows:

long long count_diff_country(int N, vector<int> country_rank) {
	ll n = N, cans = 0;
	ll prog[n], a[n], lh[n], rh[n];
	iloop(0, n) a[i] = country_rank[i], prog[i] = 0;
	iloop(0, n) {
		jloop(0, i) {
			if (lh[j] > a[i] || rh[j] < a[i]) cans++;
			if (rh[j] == a[i]) rh[j]++;
		}
		if (a[i]) {
			prog[a[i]-1]--;
			if (!prog[a[i]-1]) jloop(0, i) if (lh[j] == a[i]) lh[j]++;
		}
		prog[a[i]]++;
		lh[i] = rh[i] = a[i]+1;
	}
	return cans;
}

To speed this up, notice that we only care about the values of $$$lh$$$ and $$$rh$$$ and not about the indices that correspond to them. We can thus use a data structure such as a segment tree to store these values. The AC code for this part is as follows:

ll seg[2][2000005];
void upd(ll X, ll V, ll id) {
	for (seg[id][X += n] += V; X > 1; X >>= 1) seg[id][X>>1] = seg[id][X] + seg[id][X^1];
}
ll qu(ll S, ll E, ll id) {
	E++;
	ll res = 0;
	for (S += n, E += n; S != E; S >>= 1, E >>= 1) {
		if (S&1) res += seg[id][S++];
		if (E&1) res += seg[id][--E];
	}
	return res;
}
long long count_diff_country(int N, vector<int> country_rank) {
	n = N, cans = 0;
	ll prog[n], a[n];
	iloop(0, 2*n) seg[0][i] = seg[1][i] = 0;
	iloop(0, n) a[i] = country_rank[i], prog[i] = 0;
	iloop(0, n) {
		cans += qu(a[i]+1, n-1, 0);
		cans += qu(0, a[i]-1, 1);
		tmp = qu(a[i], a[i], 1);
		upd(a[i], -tmp, 1);
		upd(a[i]+1, tmp, 1);
		if (a[i]) {
			prog[a[i]-1]--;
			//if (!prog[a[i]-1]) jloop(0, i) if (lh[j] == a[i]) lh[j]++;
			if (!prog[a[i]-1]) {
				tmp = qu(a[i], a[i], 0);
				upd(a[i], -tmp, 0);
				upd(a[i]+1, tmp, 0);
			}
		}
		prog[a[i]]++;
		upd(a[i]+1, 1, 0);
		upd(a[i]+1, 1, 1);
	}
	return cans;
}

You may try to see how the 2 pieces of code here basically do the same thing. This now runs in $$$O(N\log N)$$$

This problem was quite cool. Initially, it reminded me of a certain algorithm that turns out was part of the intended solution, but I couldn't finish the problem with it. Fortunately the problem has many ways to go about solving. The other FC (literalchild) reportedly used a different solution.

Also I once said that XOR is my favourite operation, and it still is.

The minimum maximum cost of steps suggests the use of a minimum spanning tree (MST) on the steps. Once the MST is built, one can use methods such as Kruskal Reconstruction Tree or binary lifting (my preference) to query for path maximums on the MST. This is where the idea of using Boruvka's algorithm first appeared, since someone once told me that Boruvka's is good for MSTs on graphs with many edges; unfortunately, I could not finish the problem using it although the intended solution apparently uses it.

I first coded out the direct MST solution, adding all steps between ancestors and nodes to the graph that would be MST'ed on.

#include "teleport.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m<h?1:-1))
#define jloop(m, h) for (auto j = m; j != h; j += (m<h?1:-1))
#define kloop(m, h) for (auto k = m; k != h; k += (m<h?1:-1))
#define pll pair<ll, ll>
#define INF 2000000000000000LL
ll n, p[50005], a[50005], x, y, z;
vector<ll> adj[50005];
vector<pair<ll, pll>> ae;
vector<pll> adj2[50005];
ll twok[17][50005], twok2[17][50005], dp[50005], cc;
ll par[50005], sz[50005];
ll find(ll x) {
	return (par[x] == x ? x : par[x] = find(par[x]));
}
ll merge(ll x, ll y) {
	x = find(x), y = find(y);
	if (x == y) return 0;
	if (sz[x] < sz[y]) swap(x, y);
	par[y] = x;
	sz[x] += sz[y];
	return 1;
}
void dfs(ll nd, ll pr) {
	for (auto it : adj[nd]) if (it != pr) {
		a[it] ^= a[nd];
		dfs(it, nd);
	}
}
void dfs2(ll nd, ll pr) {
	twok[0][nd] = pr;
	iloop(1, 17) {
		if (twok[i-1][nd] == -1) break;
		twok[i][nd] = twok[i-1][twok[i-1][nd]];
		if (twok[i][nd] != -1) twok2[i][nd] = max(twok2[i-1][nd], twok2[i-1][twok[i-1][nd]]);
	}
	for (auto it : adj2[nd]) if (it.second != pr) {
		dp[it.second] = dp[nd] + 1;
		twok2[0][it.second] = it.first;
		dfs2(it.second, nd);
	}
}
ll lca(ll x, ll y) {
	ll cans = 0;
	if (dp[x] < dp[y]) swap(x, y);
	iloop(16, -1) if (dp[x] - dp[y] >= 1<<i) {cans = max(cans, twok2[i][x]); x = twok[i][x];}
	if (x == y) return cans;
	iloop(16, -1) if (twok[i][x] != twok[i][y]) {
		cans = max({cans, twok2[i][x], twok2[i][y]});
		x = twok[i][x], y = twok[i][y];
	}
	cans = max({cans, twok2[0][x], twok2[0][y]});
	return cans;
}
void init(int N, vector<int> P, vector<int> W) {
	n = N;
	memset(twok, -1, sizeof(twok));
	p[0] = -1, a[0] = 0;
	iloop(1, n) {
		p[i] = P[i], a[i] = W[i];
		adj[p[i]].push_back(i);
	}
	dfs(0, -1);
	ae.clear();
	iloop(0, n) {
		x = p[i];
		while (x != -1) {
			ae.push_back({a[x] ^ a[i], {x, i}});
			x = p[x];
		}
	}
	sort(ae.begin(), ae.end());
	cc = 0;
	iloop(0, n) par[i] = i, sz[i] = 1;
	for (auto it : ae) {
		if (merge(it.second.first, it.second.second)) {
			cc++;
			adj2[it.second.first].push_back({it.first, it.second.second});
			adj2[it.second.second].push_back({it.first, it.second.first});
			//cout << it.first << " " << it.second.first << " " << it.second.second << endl;
			if (cc == n-1) break;
		}
	}
	dfs2(0, -1);
}

int minimum_energy(int U, int V) {
	x = U, y = V;
	return lca(x, y);
}

This got 20 points In $$$O(N^2\log N)$$$.

Next, I was eyeing the 28 points subtask $$$W \lt 128$$$ along with the $$$9$$$ points from the easier $$$W \le 1$$$. This suggests that having a small number of possible edge weights (and thus path costs) may mean something. Using this, I obtained an observation:

Given a node, if 2 of its ancestors have the same path cost from it, there exists an MST where at most 1 of these steps is included.

This is immediate after noticing from XOR properties that the step cost between the 2 ancestors must be 0.

Using this, I come up with the following algorithm: for each node, find all unique path costs to an ancestor, then include only 1 of each such path cost in the computation of the MST. There are only $$$NW$$$ path costs in the MST computation now, so the time complexity is $$$O(NW\log{NW})$$$. To implement, note that XOR properties allow us to simply store the parents by their prefix XORs from the root. The modified dfs function is as follows, with the part in the main computation function adding edges removed:

vector<ll> prv[130];
void dfs(ll nd, ll pr) {
	iloop(0, 128) if (prv[i].size()) ae.push_back({i^a[nd], {prv[i].back(), nd}});
	prv[a[nd]].push_back(nd);
	for (auto it : adj[nd]) if (it != pr) {
		a[it] ^= a[nd];
		dfs(it, nd);
	}
	prv[a[nd]].pop_back();
}

This motivates the idea that not all edges may be useful. After deliberating on this thought, I obtain a stronger version of the previous observation that can be used to solve the problem:

Given a node, if the path costs to 2 of its ancestors have the same most significant bit, there is an MST solution with at most 1 of these steps. In particular, the step with the larger cost should not be needed.

This is immediate after noticing that the path costs between the 2 ancestors must, by XOR properties, have a smaller most significant bit and thus smaller value.

If we only include steps from nodes to their ancestors which, out of all other such steps sharing the same most significant bit, is minimal, there will be only $$$O(N\log W)$$$ edges to check for in the MST. This should be fast enough.

To pull this off, I use a binary trie to store all values of the prefix XORs from the root. At every node, the code checks through the binary trie to find the minimal value for each most significant bit, as well as which node it is from. This is done as such:

• If the current traversal has deviated from the prefix XOR to the node, the most significant bit has been passed and thus it is optimal to minimise the XOR, i.e. match the bits in the prefix XOR to the node whenever possible.
• If the current traversal perfectly matches the prefix XOR to the node, visit both children in the trie.

This gets all $$$O(\log W)$$$ ancestors. After that, just run the MST as per usual.

The code with the trie and the modified dfs function is as follows. The gt flag in the trav (traversal) function in the trie is 1 if the path has deviated from the prefix XOR to the node and 0 otherwise.

vector<ll> useful;
struct node {
	node *l, *r;
	vector<ll> vs;
	ll cn = 0, dpt;
	node (ll dpn) {
		dpt = dpn;
		if (dpt == g) return;
		l = new node(dpn + 1);
		r = new node(dpn + 1);
	}
	void add(ll X, ll V) {
		cn++;
		if (dpt == g) {
			vs.push_back(V);
			return;
		}
		if (X%2 == 0) l->add(X>>1, V);
		else r->add(X>>1, V);
	}
	void rm(ll X) {
		cn--;
		if (dpt == g) {
			vs.pop_back();
			return;
		}
		if (X%2 == 0) l->rm(X>>1);
		else r->rm(X>>1);
	}
	void trav(ll V, bool gt) {
		if (cn == 0) return;
		if (dpt == g) {
			useful.push_back(vs.back());
			return;
		}
		if (gt) {
			if (V%2 == 0) {
				if (l->cn) l->trav(V>>1, 1);
				else r->trav(V>>1, 1);
			}
			if (V%2 == 1) {
				if (r->cn) r->trav(V>>1, 1);
				else l->trav(V>>1, 1);
			}
			return;
		}
		if (V%2 == 0) {
			l->trav(V>>1, 0);
			r->trav(V>>1, 1);
		}
		else {
			l->trav(V>>1, 1);
			r->trav(V>>1, 0);
		}
	}
} *root;
void dfs(ll nd, ll pr) {
	useful.clear();
	ll cv = 0, ctm = a[nd];
	iloop(0, g) {cv = cv*2 + (ctm%2); ctm >>= 1;}
	root->trav(cv, 0);
	//for (auto it : useful) cout << nd << ":" << it << endl;
	for (auto it : useful) ae.push_back({a[it]^a[nd], {it, nd}});
	root->add(cv, nd);
	for (auto it : adj[nd]) if (it != pr) {
		a[it] ^= a[nd];
		dfs(it, nd);
	}
	root->rm(cv);
}

This runs in $$$O(N\log{W}\log{N\log{w}})$$$.