Ask AI
Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.
Open Claude Desktopdynamic-programming · graph-algorithms
The organizer’s problem statement is available at the official source link.
sample trace
Grass Cownoisseur: dynamic programming walkthrough
Grass Cownoisseur: use the linked editorial?s dynamic programming, graph algorithms idea on the published sample, then verify the displayed output.
Published input7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 7modelAlgorithm ideaTrack smaller states that summarize partial solutions. For each state, combine the legal predecessor states; the full-task state gives the result.task resultExpected output(file grass.out)
6
SOLUTION NOTES:
Here is an ASCII drawing of the sample input:
v---3-->6
7 |\ |
^\ v \ |
| \ 1 \|
| \| v
| v 5
4<--2---^
Bessie can visit pastures 1, 2, 4, 7, 2, 5, 3, 1 by traveling
backwards on the path between 5 and 3. When she arrives at 3 she
cannot reach 6 without following another backwards path.
- 1
State
Choose a compact value for each partial subproblem so later choices need only that summary. - 2
Transition
Combine legal smaller states to compute reachability, a count, or an optimum for the next state. - 3
Finish
Read the state representing the full task and compare it with the published sample output. - 4
Verify the sample
Use the published sample output to check the result of this idea on the displayed input.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 charsRun output
Run your code to see output.