how can i prove my solution both Dp and greedy.

Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

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

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

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

1 | adamant | 173 |

2 | awoo | 167 |

3 | SecondThread | 163 |

4 | BledDest | 162 |

4 | Um_nik | 162 |

6 | maroonrk | 161 |

7 | nor | 160 |

8 | -is-this-fft- | 150 |

9 | Geothermal | 146 |

10 | TheScrasse | 143 |

how can i prove my solution both Dp and greedy.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/01/2023 02:52:25 (l1).

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.

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.

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.