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
In the future all problemsetters should be required to ask GPT 5.5 xhigh or better to solve their problems in order to eliminate their own fakesolves.
True, but we should also go back and retroactively check all of our "solutions" from the past, seeing as how GPT is literally eliminating Erdos's fakesolves as we speak.
To be fair, that was a conjecture, not a fakesolve.
Factually, this is correct. But given that Erdos just gave a lower bound of $$$\Omega(X/\log X)$$$ in a problem of $$$O(X)$$$ upper bound, and claimed THAT to be the actual bound, I'd say it is kind of a fakesolve.
This problem does have an $$$11N$$$ solution. I guess other testers would have implemented that. Though this is a lesson that you shouldn't give unnecessarily tight limit..