how can i prove my solution both Dp and greedy.

# | User | Rating |
---|---|---|

1 | tourist | 3817 |

2 | jiangly | 3628 |

3 | Benq | 3584 |

4 | slime | 3498 |

5 | maroonrk | 3486 |

5 | djq_cpp | 3486 |

7 | Radewoosh | 3438 |

8 | cnnfls_csy | 3427 |

9 | zh0ukangyang | 3423 |

10 | orzdevinwang | 3399 |

# | User | Contrib. |
---|---|---|

1 | -is-this-fft- | 183 |

2 | awoo | 178 |

3 | dario2994 | 168 |

4 | SecondThread | 167 |

5 | Um_nik | 165 |

6 | maroonrk | 164 |

7 | adamant | 163 |

8 | kostka | 162 |

9 | antontrygubO_o | 157 |

10 | errorgorn | 156 |

how can i prove my solution both Dp and greedy.

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/08/2022 06:33:28 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

see if it gets AC or WA

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.

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

ask your mom

thank you i asked your mom. now you are my step son

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.

SpoilerDo not use proof by accepted because it doesn't help you improve at proving things.

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

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?

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

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