Solutions and explanations for problems in the Algorithm Lab at ETH (2020)
| Index | Problem | Keywords | Solution | Explaination |
|---|---|---|---|---|
| W1.1 | Even Pairs | partial sum | code | idea |
| W1.2 | Build the Sum | trivial | code | idea |
| W1.3 | Dominoes | trivial | code | idea |
| W1.4 | Even Matrices | partial sum | code | idea |
| W2.1 | Burning Coins | DP | code | idea |
| W2.2 | The Great Game | DP | code | idea |
| W2.3 | Beach Bars | DP, sliding window | code | idea |
| W2.4 | Search Snippets | DP, sliding window | code | idea |
| W2.PoTW | Deck of Cards | DP, sliding window | code | idea |
| W3.1 | Hit | trivial | code | idea |
| W3.2 | First Hit | trivial | code | idea |
| W3.3 | Antenna | trivial | code | idea |
| W3.4 | Hiking Map | sliding window | code | idea |
| W3.PoTW | From Russia with Love | DP | code | idea |
| W4.1 | First Steps with BGL | trivial | code | idea |
| W4.2 | Ant Challenge | shortest path | code | idea |
| W4.3 | Buddy Selection | max matching | code | idea |
| W4.4 | Important Bridges | bridge | code | idea |
| W4.PoTW | Defensive Line | DP | code | idea |
| W5.1 | Boats | greedy | code | idea |
| W5.2 | Attack of the Clones | greedy | code | idea |
| W5.3 | San Francisco | DP | code | idea |
| W5.4 | Asterix the Gaul | binary search, split&list | code | idea |
| W5.PoTW | Motorcycles | DP | code | idea |
| W6.1 | Shopping | max flow | code | idea |
| W6.2 | Knights | max flow | code | idea |
| W6.3 | Tiles | max flow, max matching | code | idea |
| W6.4 | Kingdom Defense | max flow | code | idea |
| W6.PoTW | Tracking | shortest path | code | idea |
| W7.1 | What is the maximum | LP | code | idea |
| W7.2 | Diet | LP | code | idea |
| W7.3 | Inball | LP | code | idea |
| W7.4 | Radiation | exponential search, LP | code | idea |
| W7.PoTW | Octopussy | greedy, memory | code | idea |
| W8.1 | Bistro | D-Trig | code | idea |
| W8.2 | Germs | D-Trig, sorting | code | idea |
| W8.3 | H1N1 | D-Trig, MST, widest(or most narrow) path | code | idea |
| W8.4 | Clues | D-Trig, CC, 2-coloring | code | idea |
| W8.PoTW | Surveillance Photographs | max flow | code | idea |
| W9.1 | Real Estate Market | min cost max flow | code | idea |
| W9.2 | Placing Knights | max independent set | code | idea |
| W9.3 | Algocoon Group | min cut | code | idea |
| W9.4 | Casino Royale | min cost max flow | code | idea |
| W9.PoTW | Astérix and the Roman Legions | LP | code | idea |
| W10.1 | World Cup | D-Trig, LP | code | idea |
| W10.2 | Asterix in Switzerland | min cut | code | idea |
| W10.3 | Asterix and the Chariot Race | DP | code | idea |
| W10.4 | New York | DP, dfs | code | idea |
| W10.PoTW | Idefix | binary search, D-Trig | code | idea |
| W11.1 | Lestrade | LP | code | idea |
| W11.2 | Return of the Jedi | bfs, MST, widest(or most narrow) path | code | idea |
| W11.3 | The Tourney of the Hand | D-Trig | code | idea |
| W11.4 | The Fighting Pits of Meereen | DP | code | idea |
| W11.PoTW | Fleetrace | min cost max flow | code | idea |
| W12.1 | India | min cost max flow | code | idea |
| W12.2 | Hong Kong | D-Trig, MST, widest(or most narrow) path | code | idea |
| W12.3 | Car Sharing | min cost max flow | code | idea |
| W12.4 | Moving Books | DP, binary search | code | idea |
| W12.PoTW | The Iron Islands | DP, sliding window | code | idea |
| W13.1 | Punch | DP | code | idea |
| W13.2 | Evolution | DFS | code | idea |
| W13.3 | Sith | binary search, CC | code | idea |
| W13.4 | Marathon | max flow, shortest path | code | idea |
| W13.PoTW | Lannister | LP | code | idea |
| W14.PoTW | On Her Majesty’s Secret Service | binary search, max flow | code | idea |