how can i prove my solution both Dp and greedy.
how can i prove my solution both Dp and greedy.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
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.
ask your mom
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.
Do 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.