rick_sanchez_c-137's blog

Jury's solution proved incorrect by counter example, what if it wasnt?
By rick_sanchez_c-137, history, 7 years ago, In English

Wubalubadubdub!

Today the jury solution for problem A (div1a/div2c) was proved incorrect by a hack from a contestant. But what if it wasn't? Maybe this would be unnoticed by everyone. Maybe for ever. Does this mean that there are other problems such as this one in which the problematic test cases weren't found?

The input in this case were pretty small, only 4 positive numbers, two of which were bounded by 12. One can only wonder about other problems, maybe with more complex test cases, maybe solved by a smaller sample of people, that are erroneously considered easy or correct. Maybe the outputs are correct for the considered input bounds, but the proof in the editorial isn't. Maybe there isn't a correct proof, just the coincidence that a certain algorithm gives correct output in every case.

I can only conclude that the lack of proof that competitve programming instigates can be dangerous. When someone fails to solve a problem as fast as the majority of others they may belive that they are overthinking, that others see that the obvious solution in a matter of seconds, when, in fact, it is just a generalized incorrect human intuition built to perform well in this kind of competitions. 

Maybe we lie too often to ourselves that we undestand a problem. 

Perhaps the editorials should be what they should be, proofs. But what do I know? I am just a slave in the universe inside yours. In a commedy show. Or maybe you are inside mine? And therefore, your existance is a lie. Or isn't it? It can't be a lie, afterall, everyone agrees otherwise.
  • Vote: I like it
  • +101
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

It's pretty simple to me. If you are solving a problem in a contest, then you can rely on intution and it would be fine.

Howwever if you want to start setting problems then you better prove solutions especially to such problems.

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

There's a fine line between sharp intuition and proof, and a huge gap between dumb guesses and intuition.

Today many people decided not to do A, hell, many of us decided not to even participate because A looked incredibly fishy. The most experienced even went on to solve safer problems that might look harder and ignored A altogether, or at least for a while.

Intuition's fine and valuable.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +26 Vote: I do not like it

    Yes, I also agree that intuition is valuable, it gaves humans the majority of our inventions that wouldn't come up randomly.

    But this contest shows how important proofs are, many reds tested the contest before, and coulnd't see the mistake. Maybe at least the contest setters shuold proove their solutions. Just because the majority of contests are correct without proof, doesn't mean that they are unecessary. Ensure that it works in every case isn't what algorithms is all about?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +20 Vote: I do not like it

      I do agree that a problem that's just weird heavy casework isn't enjoyable at all and something you can't directly prove from correct intuition isn't what we should be aiming for. I mean, that's why I mentioned people avoiding A: I don't think it's a bigger problem of blind intuition, plenty of people had enough intuition to avoid A and to know that obvious solutions were likely to fail.

      I think that the wider intuition which is built by competitive programming is good. At a lower level simplistic, badly formed "intuition" can fool people into just sending answers that happen to be correct, but I think you can't get very far doing this. I'd expect the intuition developed by nutellas to be amazingly sharp and them to be able to come up with proofs quickly if needed.

      → Reply
»
7 years ago, # |
  Vote: I like it -12 Vote: I do not like it

"Maybe there isn't a correct proof, just the coincidence that a certain algorithm gives correct output in every case" --> That, by itself, is a proof. If you run an algorithm and ensures it gives correct outputs for all possible cases, you are proving that this algorithm is, in fact, correct. It's not an elegant proof, it's a brute-force one, but a proof nonetheless.

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

    He means testcase, not all possible cases in mathematical world. Nobody calls getting AC on like 60 ~ 100 testcases as a "proof".

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

Solvers might "want to" rely on intuition, but setters should not. Setters always have to prove, and they do. There might be some mistake in proof that even setters and solvers all don't know. But I think the possibility is low. And why should we waste time about something we can not know?

Although it's impossible for CF authors to forgot such common sense, I asked them about it — just in case. So let's wait for it.

http://codeforces.net/blog/entry/52944?#comment-370104

→ Reply