maybesomeone's blog

By maybesomeone, history, 3 months ago, In English

how can i prove my solution both Dp and greedy.

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

»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

see if it gets AC or WA

  • »
    »
    3 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

you don't need to prove anything to anyone bro. Just keep grinding hard and let your success be the proof B)

»
3 months ago, # |
  Vote: I like it +12 Vote: I do not like it

ask your mom

»
3 months 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
  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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?

    • »
      »
      »
      2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just submit to see if it can be accepted in order to find whether Dp or greedy is right. Best wishes.