maybesomeone's blog

How to prove solution ?
By maybesomeone, history, 2 years ago, In English

how can i prove my solution both Dp and greedy.

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

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

see if it gets AC or WA

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

    he is probably asking this so that he can know if his solution is correct before submitting. Basically if he can write a valid proof for his algorithm, then he can be sure that he won't get penalty for incorrect submission during contests.

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

ask your mom

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

Proving that your solution is correct is a valuable skill to a competitive programmer. For dp, proof by induction is usually useful. For greedy solutions you could use another type of proof (direct proof or by contradiction) or proof by accepted if you're bad at proving things.

Spoiler
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that's why you're 1700. just trust your intuition. but a strong intuition requires solving a tons of problems

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

      well sometimes the intuition works (for me in case, on <Div2C it almost always does), but sometimes the intuition causes WA on TC2. can this pain be avoided?

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

      i wrote this when i was a 1500 and have since changed my views.

      → Reply