Solutions for problems given in ETH course Algorithms Lab in Fall 2020. I was excplicitely disallowed to share the problems descriptions. If you want to get them try emailing the responsible faculty members or Googling to find it elsewhere.
The code for these problems is written with the following in mind:
- Readability. It is prevalent in competitive programming to use macros, and extremely dense and unreadable code. I dont find the price for longer names and few more lines too high. I often rewrite the problems to try something new or to see performance gain/loss therefore even I appreciate this.
- Performance. Lot of the problems could be solved with considerably less code. It would pass within the time limits. However, I tried to make the code run fast to a reasonable extent.
- Code quality. I know this is competitive programming and it does not matter much here but I found out I do better when I go a bit slower in terms of writing code and then avoid some of small bugs/issues. This is the main reason why you can see
consteverywhere and special function to load data (to have the loaded data also const).
In case you find any kind of typo, bug, possible improvement, suboptimal solution, wrong explanation or anything else noteworthy do not hesitate to message me at my email simon.hrabec on gmail or get in touch via other means.
How to use this repository:
- Check code snippets to get an idea how to use certain libraries.
- If you get stuck and you already gave the problem some time, read the minimal amount of problem solution to get yourself unstuck.
- After finishing the task check the solutions for alternative ways to approach it
- Check the code if you just wanna compare the code of your solution and see how other people write C++.
- Compare your running time to mine to see how efficient your code is.
- BFS - W08/Clues W13/Sith
- Biconnected Components - W04/Important Bridges
- Binary Search - W05/Asterix the Gaul W10/Worldcup W12/India W12/Moving Books W13/Evolution W13/Marathon W13/Sith W13/On Her Majestys Secret Service
- Bit Manipulation - W10/Worldcup W11/Fighting Pits of Meereen
- CGAL Geometry - W03/Antenna W03/First Hit W03/Hiking Maps W03/Hit
- CGAL::Gmpq/Gmpz (Arbitrary Precision Types) - W05/Motorcycles W07/Radiation
- DFS - W05/Asterix the Gaul W10/Asterix and the Chariot Race W10/New York W11/Return of the Jedi W13/Evolution W13/Sith
- Delaunay Triangulation - W08/Bistro W08/Clues W08/Germs W0811/H1N1 W10/Worldcup W10/Idefix W11/Hand W11/Lestrade W12/Hong Kong W13/Sith
- Dijkstra - W04/Ant Challenge W04/First steps with BGL W06/Tracking W0811/H1N1 W12/Hong Kong W13/Marathon W13/On Her Majestys Secret Service
- Dynamic Programming - W02/Burning Coins W02/The Great Game W03/From Russia with Love W04/Defensive Line W05/San Francisco W12/The Iron Islands W13/Punch
- Graph Duplication - W06/Knights W06/Tracking W08/Surveillance Photograph W09/Placing Knights
- Greedy - W05/Attack of the Clones W05/Boats W07/Octopussy
- Linear Programming - W07/Diet W07/Inball W07/Radiation W07/What is the Maximum W09/Legions W10/Worldcup W11/Lestrade
- Max-Flow-Min-Cost - W09/Casino Royale W09/Real Estate Market W11/Fleetrace W12/Car Sharing W12/India W13/Marathon
- Maximum Flow - W06/Kingdom Defence W06/Knights W06/Shopping Trip W06/Tiles W08/Surveillance Photograph W09/Algocoon Group W09/Placing Knights W10/Asterix in Switzerland
- Maximum Matching - W04/Buddy Selection W06/Tiles W13/On Her Majestys Secret Service
- Minimum Spanning Tree - W04/Ant Challenge W04/First steps with BGL W11/Return of the Jedi
- Prefix Sum - W01/Even Matrices W01/Even Pairs
- Randomization - W03/Antenna W03/First Hit
- Split and List - W05/Asterix the Gaul
- Two Pointers - W02/Beach Bars W02/Search Snippets W02/Deck of Cards W04/Defensive Line
- Union-Find - W10/Idefix W11/Hand
One of the most annoying thing about ALGOLAB (after the hard thinking ^^) is to always copy paste the right definitions for boost graphs, CGAL LP or flow edge adder. For this reason I put together a small set of useful snippets that should cover all your basic needs. It shoud prevent you from always searching the lecture notes or code examples for the relevant lines or going to the CGAL docs for basic syntax. You should find it here at one place. Some of the snippets are in fact the code from lectures or code examples (modified to some extent), some are written from scratch. The all attributions are listed in the code snippet descriptions.