Koala Game

Subtarea 1

Asignamos una sola piedra a la primera copa. La copa mínima es aquella en la que Koala no tiene mayoría.


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;
}

Usa 1 turno.

Subtarea 2

Búsqueda binaria del valor máximo.

Supongamos que tenemos una lista de candidatos posibles para el máximo. Sea $L$ la longitud de esta lista. Asignamos a cada candidato $\lfloor \frac{N}{L} \rfloor$ piedras. Koala siempre asignará sus piedras de modo que la copa máxima obtenga mayoría.


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];
}

Usa 4 turnos.

Subtarea 3

Asignamos $x$ piedras a las copas 0 y 1 hasta que Koala las trate de forma distinta; en ese momento podemos saber cuál es mayor.

Podemos buscar $x$ por búsqueda binaria: si tanto 0 como 1 reciben más de $x$ piedras, aumentamos $x$ ; si no, lo disminuimos.

Como $9 + 10 + \dots + 17 > 100$ , el valor máximo de $x$ que necesitamos probar es 9, lo que mejora mucho nuestra búsqueda binaria.


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]);
}

Usa 3 turnos.

Subtarea 4

Primero, observemos que $700 \approx N \log N$ . Esto sugiere que necesitamos una estrategia tipo mergesort.

Como esta vez tenemos 200 piedras a disposición, podemos usar un turno para comparar dos copas asignando 100 piedras a ambas y 0 piedras a las demás. Como podemos comparar copas de forma eficiente, luego usamos mergesort para hallar los valores de cada copa.


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;
	a.insert(a.begin(), v.begin(), v.begin() + (v.size() + 1) / 2);
	b.insert(b.begin(), v.begin() + (v.size() + 1) / 2, v.end());
	a = mergesort(a, N, W), b = mergesort(b, N, W);
 
	vector<int> sorted;
	int aptr = 0, bptr = 0;
	while (aptr < a.size() && bptr < b.size()) {
		if (compare(a[aptr], b[bptr], N, W)) sorted.push_back(a[aptr++]);
		else sorted.push_back(b[bptr++]);
	}
	sorted.insert(sorted.end(), a.begin() + aptr, a.end());
	sorted.insert(sorted.end(), b.begin() + bptr, b.end());
 
	return sorted;
}
 
void allValues(int N, int W, int *P) {
	if (W == 2 * N) {
		vector<int> v;
		for (int i = 0; i < N; i++) v.push_back(i);
		vector<int> sorted = mergesort(v, N, W / 2);
		for (int i = 0; i < N; i++) P[sorted[i]] = i + 1;
	}
}

Usa menos de 700 turnos.

Subtarea 5

Usamos una estrategia recursiva que resuelve un rango conocido $[L, R]$ en exactamente $L + R - 1$ movimientos, partiendo $[L, R]$ en $[L, k]$ y $[k + 1, R]$ para algún $k$ en exactamente 1 movimiento.

Asignamos a cada copa que sabemos que está en $[L, R]$ $x = \lfloor \min(\sqrt{2 * L}, \frac{M}{R - L + 1}) \rfloor$ piedras y luego revisamos en qué posiciones Koala colocó más de $x$ piedras después de la ronda. Con esa información hallamos $k$ , que siempre estará en el rango $[L, R]$ .


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;
		for (int i : v)
			if (R[i] > x) greater.push_back(i);
			else less.push_back(i);
 
		split(less, N, W, P, l, l + less.size() - 1);
		split(greater, N, W, P, r - greater.size() + 1, r);
	}
}
 
void allValues(int N, int W, int *P) {
	if (W == N) {
		vector<int> v;
		for (int i = 0; i < N; i++) v.push_back(i);
		split(v, N, W, P);
	}
}

Usa 99 turnos.