What clues do you usually look for when identifying a Greedy problem during a contest? Are there any common patterns, constraints, or characteristics that help you recognize one? I'd love to hear your approaches and experiences!
What clues do you usually look for when identifying a Greedy problem during a contest? Are there any common patterns, constraints, or characteristics that help you recognize one? I'd love to hear your approaches and experiences!
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Look for problems where the best local choice leads to the global optimum. Always verify that the greedy choice is valid.
But what techniques do you personally use to verify that a local optimal choice will actually lead to a global optimum? Do you rely on mathematical proofs, testing, or both?"