Today I was upsolving a problem 1408G - Clusterization Counting from the recent Grakn Forces 2020 contest. I've solved it, however I didn't really like my solution. So I decided to view how other participants solved this problem. Of course, I first opened the tourist's submission (94320762), because his codes are always written in a good style and are easy to understand.
But when I carefully looked through his solution, I was a little bit confused, because he used the idea, which I supposed to be wrong.
The idea is the following: computers with indices $$$x_1$$$, $$$x_2$$$, $$$\ldots$$$, $$$x_k$$$ form a valid set, iff for each $$$i \in$$$ {$$$x_1, x_2, \ldots, x_k$$$}, values $$$a[i][x_1]$$$, $$$a[i][x_2]$$$, $$$\ldots$$$, $$$a[i][x_k]$$$ are smaller then all $$$a[i][j]$$$, where $$$j \notin$$$ {$$$x_1, x_2, \ldots, x_k$$$}. It's obvious that it's a necessary condition for being a valid set, and while solving this problem I first thought, that it can be also a sufficient condition. But after thinking a little bit, I realized that it's not a sufficient condition. For example on the following test:
4
0 1 2 3
1 0 4 5
2 4 0 6
3 5 6 0
Computers with indices $$$1, 2, 3$$$ don't form a valid set due to $$$a[2][3] > a[1][4]$$$, however all conditions are true: $$$a[1][2] < a[1][4]$$$, $$$a[1][3] < a[1][4]$$$, $$$a[2][1] < a[2][4]$$$, $$$a[2][3] < a[2][4]$$$, $$$a[3][1] < a[3][4]$$$ and $$$a[3][2] < a[3][4]$$$.
So I decided to run tourist's submission on this test and it turned out, that his output was wrong. After I successfully hacked his submission, I also run all 97 accepted solutions from the contest on that test case, and 13 of them turned out to be wrong. Among them were 3 submissions from the participants who took places in the top 10.
I think that there are many different tests which fail this idea, so it's strange that none of them was present in the system tests. Maybe the reason is that there are only 24 system tests in this problem. A similar situation (a small number of system tests) happened to the problem 1408F - Two Different from this round. So I think that preparing a larger number of tests is a good idea, especially for the hard problems where there are not too many submissions to test.
