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.
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.
Auto comment: topic has been updated by gelastropod (previous revision, new revision, compare).
Auto comment: topic has been updated by gelastropod (previous revision, new revision, compare).
Auto comment: topic has been updated by gelastropod (previous revision, new revision, compare).
I suggest we implement hacking phase in ioi