BigBag's blog

Weak test cases for problem G from Grakn Forces, or how did I hack tourist
By BigBag, 4 years ago, In English

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.

  • Vote: I like it
  • +269
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Yea, tests were really weak, I've hacked aid's solution because of DSU without any optimization (so it was $$$O(n^3)$$$) and also Errichto hacked mine because of a bug.

There's a description of the bug: when we scan the edges in the ascending order of weights and merge the components if necessary, we always multiply two polynomials that represent the results for the components. Also, if the current edge is the maximal edge contained in some component, we do something like $$$DP[component][1]$$$++, as it's a valid component at the moment. So, merging components A and B to calculate the weight of the heaviest edge in the component we should take max(max_in_A, max_in_B, max_between_A_and_B), so it will amortize to $$$O(n^2)$$$. Due to the bug I was taking only max(max_in_A, max_between_A_and_B) and that also passed the systests...

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -68 Vote: I do not like it

    can you help with codechef long challenge we can do a zoom call? I can pay you

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +53 Vote: I do not like it

      Yeah, I can cheer you to solve the problem by yourself, no problem. Maybe even I won't too expensive!

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -28 Vote: I do not like it

        Cheering probably won't help too because I struggle with DIV2A's.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          Then maybe nothing will help in your case!

          → Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

So tourist submits obviously wrong solutions without proofs, wow.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Cause submitting obviously wrong solutions, but with proofs, is better...

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +41 Vote: I do not like it

One way all the WA uphacks could've been avoided is by using pseudo-multitest: you can make some components with small size and then merge them later; the end result will be correct only if the result for all of those components is also correct. Example of a generator which hacks all the G WA uphacked solutions:

Code
→ Reply