### BigBag's blog

By BigBag, 3 years ago,

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.

• +269

By BigBag, 7 years ago, translation,

Hi everyone!

Codeforces Round #373 (Div. 1 + Div. 2) will take place on 23 September 2016 at 16:05 MSK. Please note that the timing is unusual.

This time tasks for you were prepared by me (Matvey Aslandukov) and my brother _XuMuk_ (Andrew Aslandukov). It is our first codeforces round and we hope you'll enjoy it. We want to say special thanks to Seyaua (Ievgen Soboliev), AlexFetisov (Alexandr Fetisov) and winger (Vladislav Isenbaev) for testing the problems, GlebsHP for his help with the contest preparation, and MikeMirzayanov for the excellent platforms Polygon and Codeforces.

Coincidentally, the date of the round falls on my birthday, so I am very happy that I can spend that day surrounded by our friendly community :)

There will be five problems and two hours to solve them. Traditionally, the scoring distribution will be announced later.

Good luck!

UPD1:

Scoring:

Div. 2 : 500 1000 1500 2250 2250

Div. 1 : 500 1250 1250 2000 2500

The problems are sorted by difficulty but as always it's recommended to read all the problems.

UPD2:

Contest complete! Thank you all for participating :)

Unfortunately, as noted Um_nik, many solutions of div.1 B task, including the author's, were incorrect. Now we are working on this problem. If we still manage to find the right solution and answers on pretests will be the same, the round may be rated. Otherwise, it will be unrated.

Thus final results significantly delayed. We apologize for the situation. If you have thought about the correct solution — write to us.

UPD3:

We made a decision to start system testing with the current solutions and tests. The question will be round either rated or not is still opened.

UPD4:

After considering different option and estimating their pros and cons, Codeforces team decided that the main factor to make a decision on whether the round should be rated or not is how much the bug affected the results.

In the second division, only two participants managed to implement the correct greedy algorithm for the original incorrect version of the problem D, thus we consider the effect of this problem on the final standing to be negligible. The contest for division two will be rated.

Things are very different for division one, as there were plenty submission to problem B and problems B and C took the most part of participants worktime during the contest. Assuming this fact we suppose that this bug affected the final results a lot and there is no way to consider its influence on each particular participant. As a result, the contest for division one will be unrated.

The only thing left to do is to apologize to the participants. We will do our best to avoid such situations in the future.

UPD5:

Congratulations to the winners!

Div.1:

Div.2: