Блог пользователя gelastropod

Counterexample to IOI Sphinx model code
Автор gelastropod, история, 5 месяцев назад, По-английски

So I was trying to upsolve IOI 2024 Q6 Sphinx. In the editorial phase 2 states to split the condensed graph into two sets, and perform binary search on these sets for every colour, to determine which components have what colour. However, each binary search needs $$$\log N\approx8$$$ queries to perform the actual binary search, along with an additional query to "confirm" that no other component in the set has that colour. Along with the rest of the solution, this gives a query count of $$$3N+a+N\log N$$$, where $$$a$$$ is the number of monochromatic components. This means that, in the worst case, the solution would take $$$4N+N\log N$$$, which is up to $$$3000$$$ queries, more than is allowed in the problem. At first, I thought that there would be some amortisation which keeps the query count under the limit of $$$2750$$$ queries, but then I made the following construction:

Consider the test case with $$$N=250$$$ vertices, all with different colours. Then, the graph is constructed by taking the first 248 vertices, and for each of these vertices construct an edge between that vertex and both vertices 249 and 250 (1-indexed). Testing this test case on the model code provided by IOI, it took $$$2977 \gt 2750$$$ queries to finish?

Is this a counterexample to the model solution for IOI Sphinx? The testcase I used is below, you can test it out yourself.

Test case used

Edit: I used the model_solution/solution.cpp file, apparantly it works on other solutions.

Edit: This testcase also breaks some people's solutions, https://oj.uz/submission/1372712 for example.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +117
  • Проголосовать: не нравится

ioi results
Автор gelastropod, история, 5 месяцев назад, По-английски

bigW and GirrySnake777 will AK ioi!

we need to flip the problem inside out

#include "multi.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
	using ull = unsigned long long;

	struct info {
		int idx1, idx2;
		ull weight;
	};

	const ull c1 = 0xFF, c2 = 0xFFFFFFFFFFFF, c3 = 0xFFFFFFFFFFFFFF;
	constexpr ull pack(info i, int type) { return ((ull)(i.idx1) << 56) + type * ((ull)(i.idx2) << 48) + i.weight; }
	constexpr info unpack(ull i, int type) { return info{ (int)(i >> 56), (int)((i >> 48) & c1), i & (type ? c2 : c3) }; }

	int N, r, i;
	ull total;
	vector<ull> A, B, C;
	vector<info> infos, auxinfo;
	vector<int> p, ss;
	vector<int> leaders;
	vector<ull> edgeweights;
	vector<pair<int, int>> bedges;

	int fin(int n) {
		if (p[n] == n) return n;
		return p[n] = fin(p[n]);
	}

	void join(int a, int b, bool add = 1) {
		int oa = a, ob = b;
		a = fin(a), b = fin(b);
		if (a == b) return;
		if (a < b) swap(a, b);
		if (add && i == min(oa, ob)) total += A[max(oa, ob)];
		ss[b] += ss[a];
		p[a] = b;
	}

	void reset() {
		A.clear(); B.clear(); C.clear();
		infos.clear(); auxinfo.clear(); p.clear(); ss.clear();
		leaders.clear(); edgeweights.clear(); bedges.clear();
	}
}

vector<ull> strategy(int _N, int _r, int _i, vector<ull> _A, vector<ull> _B) {
	reset();
	N = _N, r = _r, i = _i, A = _A, B = _B;
	if (N == 2) return { A[!i] };
	C.resize(N, 0);
	ss.resize(N, 1);
	for (int j = 0; j < N; j++) p.push_back(j);
	for (int j = 0; j < N; j++) infos.push_back(unpack(B[j], !((i == j && r != 4 && r != 1) || (i == 0 && r == 4))));
	auxinfo.resize(N, { -1, 0, c2 });
	total = (r == 1 ? 0ull : infos[i].weight);
	info crnt{ 0, 0, c2 }; ull minw = c2;
	for (int j = 0; j < N; j++) {
		if (i == j) continue;
		if (A[j] < crnt.weight) crnt.weight = A[j], crnt.idx2 = j;
		if (crnt.weight < minw) {
			swap(minw, crnt.weight);
			swap(crnt.idx1, crnt.idx2);
		}
	}
	if (r == 1) {
		for (int j = 0; j < N; j++) join(j, infos[j].idx1);
		for (int j = 0; j < N; j++) {
			if (ss[fin(j)] == 2) {
				if (infos[j].weight < infos[infos[j].idx1].weight) join(j, infos[j].idx2);
				else join(infos[j].idx1, infos[infos[j].idx1].idx2);
			}
		}
	}
	else if (r <= 5) for (int j = 0; j < N; j++) p[j] = infos[j].idx1;
	if (r == 2 || r == 3) {
		crnt.weight = c2;
		for (int j = 0; j < N; j++) if (infos[i].idx1 != fin(j) && A[j] < crnt.weight) crnt.weight = A[j], crnt.idx2 = j;
		infos[i] = crnt;
		for (int j = 0; j < N; j++) if (infos[j].weight < auxinfo[fin(j)].weight) auxinfo[fin(j)].weight = infos[j].weight, auxinfo[fin(j)].idx2 = infos[j].idx2, auxinfo[fin(j)].idx1 = j;
		for (int j = 0; j < N; j++) if (auxinfo[fin(j)].idx1 != -1) join(auxinfo[fin(j)].idx1, auxinfo[fin(j)].idx2);
	}
	else if (r == 4) {
		if (i == 0) for (int j = 1; j < N; j++) total += infos[j].weight;
	}
	if (r == 3 || r == 4 || (r == 5 && i == 0)) {
		for (int j = 0; j < N; j++) if (p[j] == j) leaders.push_back(j);
		for (int j = 0; j < leaders.size(); j++) for (int k = 0; k < j; k++) bedges.push_back({ j, k });
		edgeweights.resize(leaders.size(), c2);
	}
	if (r == 0) for (int j = 0; j < N; j++) C[j] = pack(crnt, 1);
	else if (r == 1 || r == 2) {
		crnt.weight = c2, crnt.idx1 = fin(i);
		for (int j = 0; j < N; j++) if (crnt.idx1 != fin(j) && A[j] < crnt.weight) crnt.weight = A[j], crnt.idx2 = j;
		for (int j = 0; j < N; j++) C[j] = pack(crnt, 1);
		C[i] = pack({ crnt.idx1, 0, total }, 0);
	}
	else if (r == 3) {
		for (int j = 0; j < leaders.size(); j++) for (int k = 0; k < N; k++) if (fin(k) == leaders[j] && A[k] < edgeweights[j]) edgeweights[j] = A[k];
		for (int j = 1; j <= bedges.size(); j++) C[j] = pack({ fin(i), 0, edgeweights[bedges[j - 1].first] }, 1);
		for (int j = bedges.size() + 1; j < N; j++) C[j] = pack({ fin(i), 0, 0 }, 1);
		C[0] = pack({ fin(i), 0, total }, 0);
	}
	else if (r == 4) {
		if (i == 0) C[0] = pack({ fin(i), 0, total }, 0);
		else if (i <= bedges.size()) {
			crnt.weight = c2, crnt.idx1 = fin(i);
			for (int j = 0; j < N; j++) if (infos[j].idx1 == leaders[bedges[i - 1].second] && infos[j].weight < crnt.weight) crnt.weight = infos[j].weight;
			C[0] = pack(crnt, 1);
		}
		else C[0] = pack({ fin(i), 0, 0 }, 1);
	}
	else if (r == 5) {
		if (i == 0) {
			vector<pair<ull, pair<int, int>>> edges;
			for (int j = 1; j <= bedges.size(); j++) edges.push_back({ infos[j].weight, bedges[j - 1] });
			sort(edges.begin(), edges.end());
			p.clear();
			for (int j = 0; j < leaders.size(); j++) p.push_back(j);
			for (int j = 0; j < bedges.size(); j++) {
				if (fin(edges[j].second.first) == fin(edges[j].second.second)) continue;
				join(edges[j].second.first, edges[j].second.second, 0);
				total += edges[j].first;
			}
			return { total };
		}
	}
	return C;
}

Edit:

peak

Thank you all for the amazing support I have recieved!

Полный текст и комментарии »

  • Проголосовать: нравится
  • -18
  • Проголосовать: не нравится