Блог пользователя maybesomeone

How to prove solution ?
Автор maybesomeone, история, 2 года назад, По-английски

how can i prove my solution both Dp and greedy.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

see if it gets AC or WA

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    → Ответить
»
2 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

ask your mom

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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
→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

      → Ответить