algolab
algolab copied to clipboard
Published
20 hours ago •
dsparber
dsparber
My solutions for the ETH Algorithms Lab 2020
Algorithms Lab 2020
Build
mkdir build
cd build
cmake ..
make -j8
Problems
| Task | Implementation | Score | Week | Topics |
|---|---|---|---|---|
| Build the Sum | build_the_sum.cpp | 100 | Week 1 | --- |
| Dominoes | dominoes.cpp | 100 | Week 1 | --- |
| Even pairs | even_pairs.cpp | 100 | Week 1 | --- |
| Even Matrices | even_matrices.cpp | 100 | Week 1 | --- |
| Deck of Cards | deck_of_cards.cpp | 100 | Week 2* | DP |
| Burning Coins | burning_coins.cpp | 100 | Week 2 | DP |
| The Great Game | the_great_game.cpp | 100 | Week 2 | DP |
| Beach Bars | beach_bars.cpp | 100 | Week 2 | SW |
| Search Snippets | search_snippets.cpp | 100 | Week 2 | SW |
| Russia | russia.cpp | 100 | Week 3* | DP |
| Hit | hit.cpp | 100 | Week 3 | Geo |
| First Hit | first_hit.cpp | 100 | Week 3 | Geo |
| Antenna | antenna.cpp | 100 | Week 3 | Geo |
| Hiking Maps | hiking_maps.cpp | 100 | Week 3 | Geo |
| Defensive Line | defensive_line.cpp | 100 | Week 4* | SW & DP |
| First Steps with BGL | first_steps.cpp | 100 | Week 4 | SP |
| Ant Challenge | ant_challenge.cpp | 100 | Week 4 | MST & SP |
| Buddy Selection | buddy_selection.cpp | 100 | Week 4 | MM |
| Important Bridges | important_bridges.cpp | 100 | Week 4 | 2CC |
| Motorcycles | motorcycles.cpp | 100 | Week 5* | Geo |
| Boats | boats.cpp | 100 | Week 5 | Greedy |
| Attack of the Clones | attack_of_the_clones.cpp | 100 | Week 5 | Greedy |
| San Francisco | san_francisco.cpp | 100 | Week 5 | DP |
| Asterix the Gaul | asterix_the_gaul.cpp | 100 | Week 5 | BS & SL |
| Tracking | tracking.cpp | 100 | Week 6* | SP |
| Shopping Trip | shopping_trip.cpp | 100 | Week 6 | MF |
| Knights | knights.cpp | 100 | Week 6 | MF |
| Tiles | tiles.cpp | 100 | Week 6 | MF |
| Kingdom Defence | kingdom_defence.cpp | 100 | Week 6 | MF |
| Octopussy | octopussy.cpp | 100 | Week 7* | DP-like |
| Maximize it | maximizeit.cpp | 100 | Week 7 | LP |
| Diet | diet.cpp | 100 | Week 7 | LP |
| Inball | inball.cpp | 100 | Week 7 | LP |
| Radiation | radiation.cpp | 100 | Week 7 | LP |
| Surveillance | surveillance.cpp | 100 | Week 8* | MF |
| Bistro | bistro.cpp | 100 | Week 8 | DT |
| Germs | germs.cpp | 100 | Week 8 | DT |
| H1N1 | h1n1.cpp | 100 | Week 8 | DT, MST |
| Clues | clues.cpp | 100 | Week 8 | DT, 2C, CC |
| Legions | legions.cpp | 100 | Week 9* | LP |
| Casino Royale | casino.cpp | 100 | Week 9 | MCMF |
| Real Estate | real_estate.cpp | 100 | Week 9 | MCMF |
| Algocoon | algocoon.cpp | 100 | Week 9 | MC |
| Placing Knights | placing_knights.cpp | 100 | Week 9 | MaxIS |
| Idefix | idefix.cpp | 100 | Week 10* | DT & UF |
| Chariot Race | chariot_race.cpp | 100 | Week 10 | DP-like |
| New York | new_york.cpp | 100 | Week 10 | SW over tree |
| Worldcup | worldcup.cpp | 100 | Week 10 | LP & DT |
| Switzerland | switzerland.cpp | 100 | Week 10 | MF |
| Fleet Race | fleetrace.cpp | 100 | Week 11* | MCMF |
| Return of the Jedi | return_of_the_jedi.cpp | 100 | Week 11 | 2nd best MST |
| Lestrade | lestrade.cpp | 100 | Week 11 | LP & DT |
| Hand | hand.cpp | 100 | Week 11 | DT, UF |
| Meereen | meereen.cpp | 100 | Week 11 | DP |
| Iron Islands | iron_islands.cpp | 100 | Week 12* | SW |
| Car Sharing | carsharing.cpp | 100 | Week 12 | MCMF |
| Hong Kong | hongkong.cpp | 100 | Week 12 | DT, SP |
| India | india.cpp | 100 | Week 12 | BS & MCMF |
| Moving Books | moving_books.cpp | 100 | Week 12 | Greedy |
| Lannister | lannister.cpp | 100 | Week 13* | LP |
| Evolution | evolution.cpp | 100 | Week 13 | DFS & BS |
| Marathon | marathon.cpp | 100 | Week 13 | SP & MF |
| Punch | punch.cpp | 100 | Week 13 | DP |
| Sith | sith.cpp | 100 | Week 13 | DT & BS |
| Secret Service | secret_service.cpp | 100 | Week 14* | BS & MF |
Legend
- *: This was a "Problem of the Week"
- 2C: 2-Coloring / Bipartition
- 2CC: 2-Connected Components / Biconnected Components
- BS: Binary Search
- CC: Connected Components
- DFS: Depth First Search
- DP: Dynamic Programming
- DT: Delaunay Triangulation
- Geo: Geometric
- LP: Linear Programming
- MC: Min. Cut
- MCMF: Min. Cost Max. Flow
- MF: Max. Flow
- MM: Maximal Matching
- MST: Minimum Spanning Tree
- SL: Split & List
- SP: Shortest Path
- SW: Sliding Window
- UF: Union Find
Official Solutions
For some problems, an official solutions was released. You can find them in this repository as well.
dsparber