dv.jakhar's blog

Do you actually prove?
By dv.jakhar, 4 years ago, In English

Hello, I am curious to know if you try to prove observations you make for a problem during the ongoing contest or you are like "I think this can be done this way"...??

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

Comments Comments (7)
| Write comment?
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I always prove in the contests that can only submit once(CNOI mode)

I usually prove it if it's easy and the pernalty affects

I usually prove-by-ac in an IOI-mode contest and the method is easy-coding.

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

I don't bother with formality and rigor, but I always try to at least justify any observations I make.

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

No most of the time. We usually come up with examples* to verify the hypotheses. And rely on gut feeling too. Sounds iffy but solving competitive programming problems doesn't require much rigor. Sure, you should test your submission carefully and make sure not to make silly mistakes during a contest but mathematical proofs sound way over the top.

I have nothing against proofs, though. Proofs are awesome. They're just not that useful during a contest.

* Your brain isn't a good random number generator. It is rather biased. Write a computer program to generate test cases instead. You can work them out by hand, however. A dozen cases or so and you can be very confident that your algorithm is correct.

Also I second what Shisuko said.

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

Not exactly prove, but I try to convince myself about some observations I made using contradictions and inductions.

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

I trust in my luck :v

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

I won't ever use an observation I cannot justify.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Love it!!

    But sometimes if we don't go with our gut feeling, we might get late in submitting the sol? How u deal with that?

    For eg. suppose your competitors have already solved it fast, and you have some intuition that might work. Do you actually wait & prove it, or do you just implement and submit?

    → Reply