The problem
A delivery van starts at junction s of a town with one-way streets. At each junction v, value[v] parcels are waiting. The van may drive along the streets for as long as it likes, through any junction any number of times, and it collects the parcels of every junction it passes, the first time it is there. What is the largest number of parcels it can collect?
most_collected(3, [(0, 1), (1, 0), (0, 2)], [0, 5, 7], 0) # 12
most_collected(2, [(0, 1)], [3, 4], 1) # 4
In the first, the van goes to 1, back to 0, then on to 2. Streets may repeat, and a street may lead from a junction to itself. Values are 0 or more.
Limits
- Up to 100,000 junctions and 150,000 streets.
- A chain of 100,000 streets in a row: searches must not use recursion.
Builds on ADDP-2 DP on DAGs.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Just the start | Not run | |
| 2 | One street | Not run | |
| 3 | No way back | Not run | |
| 4 | A loop | Not run | |
| 5 | Into a loop and out again | Not run | |
| 6 | Choose the better branch | Not run | |
| 7 | Each junction counts once | Not run | |
| 8 | Out of reach | Not run | |
| 9 | Repeated streets and a street to itself | Not run | |
| 10 | Greedy goes wrong | Not run | |
| 11 | Two loops joined | Not run | |
| 12 | A loop with two exits | Not run | |
| 13 | A tangle of 30 | Not run | |
| 14 | A one-way chain of 100,000 | Not run | |
| 15 | A ring of 100,000 | Not run | |
| 16 | A chain of 30,000 loops | Not run | |
| 17 | 60,000 junctions, random | Not run |