APIO 2017 - Koala Game

Subtask 1

Assign a single stone to the first cup. The minimum cup is the one where Koala doesn't have a majority.

Copy
int minValue(int N, int W) {
	fill(B, B + N, 0);
	B[0] = 1;
	playRound(B, R);
	if (R[0] < 2) return 0;
	else
		for (int i = 1; i < N; i++)
			if (!R[i]) return i;
}

Uses 1 turn.

Subtask 2

Binary search for the maximum value.

Assume we have a list of possible candidates for the maximum. Let this list be of length $L$. Assign each candidate $\lfloor \frac{N}{L} \rfloor$ stones. Koala will always assign her stones so that the maximum cup gets a majority.

Copy
int maxValue(int N, int W) {
	vector<int> v;
	for (int i = 0; i < N; i++) v.push_back(i);
	while (v.size() != 1) {
		int k = W / v.size();
		fill(B, B + N, 0);
		for (int i : v) B[i] = k;
		playRound(B, R);
		v.clear();
		for (int i = 0; i < N; i++)
			if (R[i] > k) v.push_back(i);
	}
	return v[0];
}

Uses 4 turns.

Subtask 3

Assign cups 0 and 1 $x$ stones until Koala treats them differently, at which point we can tell which is greater.

We can binary search for $x$: if both 0 and 1 get more than $x$ stones, increase $x$ and otherwise, decrease $x$.

Since $9 + 10 + \dots + 17 > 100$, the maximum value of $x$ we need to try is 9, which improves our binary search significantly.

Copy
int greaterValue(int N, int W) {
	int l = 1, r = 9;
	while (l != r) {
		int mid = (l + r) / 2;
		B[0] = B[1] = mid;
		playRound(B, R);

		if (R[0] > mid && R[1] > mid) l = mid + 1;
		else if (R[0] <= mid && R[1] <= mid) r = mid - 1;
		else return (R[0] < R[1]);
	}
	B[0] = B[1] = l;
	playRound(B, R);
	return (R[0] < R[1]);
}

Uses 3 turns.

Subtask 4

First, notice how $700 \approx N \log N$. This suggests that we need a mergesort-like strategy.

Since we have 200 stones at our disposal this time, we can use one turn to compare two cups by assigning 100 stones to both of them and 0 stones to the other cups. Since we can compare cups efficiently, we can then use mergesort to find the values of each cup.

Copy
inline bool compare(int a, int b, int N, int W) {
	fill(B, B + N, 0);
	B[a] = B[b] = W;
	playRound(B, R);
	return (R[b] > W);
}
vector<int> mergesort(vector<int> v, int N, int W) {
	if (v.size() == 1) return v;

	vector<int> a, b;

Uses fewer than 700 turns.

Subtask 5

We use a recursive strategy that solves for a known range $[L, R]$ in exactly $L + R - 1$ moves by splitting $[L, R]$ into $[L, k]$ and $[k + 1, R]$ for some $k$ in exactly 1 move.

Assign each cup we know to be in $[L, R]$ $x = \lfloor \min(\sqrt{2 * L}, \frac{M}{R - L + 1}) \rfloor$ stones and then check which positions Koala has placed more than $x$ stones next to after the round. We can then find $k$ from this information, which will always be in the range $[L, R]$.

Copy
void split(vector<int> v, int N, int W, int *P, int l = 1, int r = 100) {
	if (l == r) P[v[0]] = l;
	else {
		int x = min((int)sqrt(2 * l), W / (r - l + 1));

		fill(B, B + N, 0);
		for (int i : v) B[i] = x;

		playRound(B, R);
		vector<int> less, greater;

Uses 99 turns.