dvjakhar31's blog

By dvjakhar31, 7 weeks 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

»
7 weeks 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.

»
7 weeks 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.

»
7 weeks 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.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Well, as said in this comment:

    But it's not like after I'm finished thinking I start to prove. Usually the proof just develops as part of the problem solving process.

    I think, this somewhat explains, that the guts feeling is the feeling when you think you have done enough proves that your solution should be correct. So, most of the time, there are some proofs that are just there instinctively, while you are thinking. That's why, it's not really true to say something like:

    No I don't prove my observations during contests

    Also in the same blog where the comment above was, this question was asked. You might find something there, too.

»
7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I trust in my luck :v

»
7 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

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