Solutions for problems given in ETH course Algorithms Lab in Fall 2020.
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).
Should you find some typo, bug, improvement or anything related feel free to message me at my email
simon.hrabec on gmail.
How to use this repository:
- Copy-paste relevant code snippets to begin your work
- If stuck and gave the problem already 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++
|Week||Problem of the Week||1st problem||2nd problem||3rd problem||4th problem|
|5||Motorcycles||Asterix the Gaul|
|7||Inball||Radiation||What is the Maximum|
|10||Asterix and the Chariot Race||Asterix in Switzerland||New York|
|11||Fleetrace||Fighting Pits of Meereen||Hand||Lestrade||Return of the Jedi|
|12||Car Sharing||Hong Kong||India||Moving Books|
- BFS - W13/Sith
- Binary Search - W05/Asterix the Gaul W12/India W12/Moving Books W13/Evolution W13/Marathon W13/Sith
- Bit Manipulation - W11/Fighting Pits of Meereen
- CGAL Geometry - W03/Antenna W03/First Hit W03/Hit
- CGAL::Gmpz/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/Germs W11/Hand W11/Lestrade W12/Hong Kong W13/Sith
- Dijkstra - W06/Tracking W12/Hong Kong W13/Marathon
- Dynamic Programming - W13/Punch
- Graph Duplication - W06/Tracking W08/Surveillance Photograph
- Linear Programming - W07/Inball W07/Radiation W07/What is the Maximum W09/Legions W11/Lestrade
- Max-Flow-Min-Cost - W11/Fleetrace W12/Car Sharing W12/India W13/Marathon
- Maximum Flow - W08/Surveillance Photograph W10/Asterix in Switzerland
- Minimum Spanning Tree - W11/Return of the Jedi
- Randomization - W03/Antenna W03/First Hit
- Split and List - W05/Asterix the Gaul
- Union-Find - 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.