Solutions for the Algorithms Lab 2023 course at ETH Zurich.
Problem | Solution idea |
---|---|
The Great Game | Parallel game, DP starting from end. |
Burning Coins | Min-max DP, pick coin from either side each iteration and memoize (left, right) as state space. |
Beach Bars | Sliding window, keep track of maximum. |
Lord Voldemort | Precompute all intervals that sum to |
James Bonds' Sovereigns | Burning coins with more min players. |
Important Bridges | Find biconnected components with 2 vertices, a.k.a. 1 edge. |
Buddy Selection | For each student-pair, compute the amount of common interests (sort the interests and linearly compare them). Then, each student is vertex in graph and there is an edge between students if they have more than |
Ant Challenge | Read in all graphs as separate graphs, then Prim's algorithm to figure out their edges. The final graph minimizes the weights of the edges. |
The Iron Islands | Within arm, sliding window. Then, to compute for intervals between two arms, construct a map that maps cost to max amount of islands (and the arm it is part of). Then, for every arm go over the islands, and figure out how many islands maximally can be covered by taking the mapping of the corresponding cost. |
Antenna | Minimum enclosing circle. CGAL has a function for this. |
Hiking Maps | For each triangle, figure out which hikes it covers by checking whether the two points are within the triangle. This can be done by checking whether each point is on the left side of all edges or on the right side of all edges. Then, sliding window. |
Planet Express | Strong components contain vertices that can be teleported between, since all points within a strong component are pairwise reachable. Then, for each strong component, we add a "supervertex" that maps all vertices to each other with this teleportation mechanism. Then, Dijkstra's. |
Moving Books | Greedy where strongest person takes heaviest book every iteration (store books in multiset and use lower_bound). |
Asterix the Gaul | This problem is NP-hard, so we use split and list. Binary search over amount of potions. |
Severus Snape | Dynamic programming with state space (amount of A potions picked, minimum amount of happiness) where the value is the maximum power. Then, go over all potion counts with happiness H. Then, we greedily choose B potions such that we have enough wit and still enough power left. |
Boats | Start from the left. Each iteration, we consider a boat. If the ring is covered by another boat, check whether it is possible to place this boat, such that the total width of boats is smaller, then place it. Otherwise, do not change. |
Motorcycles | Use CGAL::Gmpq to represent the slopes for easy comparison. We go over every motorcycle, starting from the bottom. For every iteration i , we check everything j below it whether they crash. If j already crashes, skip. If slope(i) >= slope(j) , i stops (early terminate), otherwise j stops. |
Tiles | See it as a chess board. Max flow where we connect every white squares to the black squares (if they are both spots that need to be tiled). Source goes to white and black goes to target. If flow == number of open spots, it is possible. |
London | Max flow where we have vertices for every letter in the note and vertices for every cutout. Connect letter vertices to cutout vertices that contain the letter. Connect source to letters with how many of that letter is needed. Connect cutout to target with how many cutouts there are. |
Coin Tossing Tournament | Match and player vertices. Connect player match vertices to their winner. If unknown winner, connect to both. Source to match and players to target with flow equal to their amount of wins in the leaderboard. Then, compare flow to sum of wins. |
Knights | Vertex capacity on intersections. Undirected edges by adding edges in both ways (it works). Connect outer intersections to target (dependent on how many pathways there are out from there). |
Octopussy | Greedily choose which bomb to work toward according to detonation time. Then, defuse all children by DFS and count how much time it takes. Then, each iteration, we compare the elapsed time to the detonation time of the bomb. If past, the bomb has gone off. |
Bistro | Triangulation with t.nearest\_vertex() . |
H1N1 | Triangulation. Then, construct a graph where the faces are the vertices and the edges have weight equal to the length of the edge between two faces. Then, do a modified Dijkstra's algorithm that computes the maximum bottleneck to get out of the convex hull. Use this |
Germs | Triangulation makes it easy to find closest points. Then, minimize the time till death for each (also compute to the wall). Then, put all times in a vector, sort, and take min, median, and max. |
GoldenEye | Three modified Kruskal's algorithms. The first only adds components with edges that require less than or equal to p power. Then, to check whether a mission is possible, compute distance to nearest vertex, and see whether the two points are within the same component. The second does the same but adds edges until every mission is do-able. The third does the same as the second but only with the missions from the first. |
Kingdom Defence | Min, max capacities. Each vertex has a demand and a supply. |
Suez | Linear program, where we want to maximize the total perimeter. Add constraint for every new picture pair so they do not touch after scaling. Then, only consider the closest old picture. |
Inball | Linear program with variables |
Idefix | Triangulation with Kruskal's, where we differentiate between tree and bone vertices. For the first problem, we compute how many bones are reachable from each tree. Then, we do union-find and add bone together. Then, output maximum amount of bones. For the second problem, we have to triangulate trees and bones. If we have a tree-bone edge, we add 1 bone to the component of the tree. If we have a tree-tree edge, we add them together into the new component. If greater than k after adding, output radius. |
Canteen | Min cost max flow where each day is a vertex. Then, we can keep meals between days by vertex between consecutive days. Add meals each day and sell meals each day. |
Placing Knights | We model the problem such that there is an edge between all positions that collide with each other. We then want to compute the size of the maximum independent set. This is bipartite graph, so we can compute the minimum vertex cover by max flow. Then, output number of nodes - minimum vertex cover. |
Real Estate Market | Not hard min cost max flow with additional contraint, where we assign buyers to properties and each property is connected to its state to constrain amount of properties old in a state. |
Algocoon Group | This is a min cut problem. We want to find the min cut between any two nodes. We do this by fixing one vertex and computing the min cut with all other vertices (both ways). |
Casterly Rock | Linear program, where we first separate the points. Make sure that |
San Francisco | Dynamic programming with state space (amount of moves left, current vertex). DFS through children to maximize score. Do this for all amount of moves, 1 to k, and compute maximum score. If greater than x, output amount of moves. |
Rubeus Hagrid | First, compute the traversal time and descendants of each subtree. We do DFS with a greedy approach as to how we pick the next child to explore. We pick the child that maximizes descendants / traversal time , which sorts them according to losing the least amount of gold. |
Surveillance Photographs | Max flow with two copies of the graph (in the same data structure). In one graph, they can roam freely, then they pick up a photograph by going to the other graph, after which they need to get to a police station to get to the target. Also, the second graph has 1 capacity on all edges. |
Clues | We first do triangulation to find closest stations for all stations. Then, we create a graph that connects stations to other stations with less than r range. Then, compute the bipartite graph of this to check whether there is interference. But, we also need to check within each color of the partition, because there are edge cases. Then, just do Kruskal's with only edges less than r . For each point pair we can then check whether they are connected. |
India | We want to find the maximum amount of luggage with a constraint on the cost. Thus, we cannot do it in one min cost max flow. More luggage => More money. So, we binary search over amount of luggage (maybe binary search is not necessary). |
Asterix and the Chariot Race | Dynamic programming with three values per vertex: Min cost such that root is repaired, Min cost such that root is saved, Min cost such that root is not necessarily saved, but it's children are. From this, the recurrence relationship is easy to find. |
Dean Thomas | Same as H1N1, but we also need to consider large faces that we can reach. To do this, use dual to find size of face, and add to initialization of priority queue (just like we add infinite face with its size, which is infinity). |
Asterix and the Roman Legions | Linear program with variables |
The Phantom Menace | Min cut with vertex capacities. |
Pied Piper | Go forward and backward at the same time. Backward goes over reverse graph. Then, DP with (forward vertex, backward vertex) as state space. Make sure that forward != backward always. If cannot continue: invalid path. If forward > backward: continue backward. If backward > forward: continue forward. Maximize number of rats. https://github.com/cristianpjensen/eth-algorithms-lab/blob/master/README.md |
New York | Use std::multiset and std::deque . Then DFS. Make sure the history is at most m . Each time when we explore child, we remove parent, add child. And, then when we get back, we put them back again to the original state. std::multiset allows for easy min and max computation with *multiset.begin() and *multiset.rbegin() . |
Return of the Jedi | Leia explores with Prim's algorithm. So, we first compute the edges of her plan. Then, compute the MST while disallowing one of the edges. Do this for every edge and minimize cost. |
Rumpelstilzchen | Key insight: Max flow from |
World Cup | Linear program with fairly easy variables. Hard part are the circles. The key insight is that we only need to go over circle line is if exactly one is in the circle. So, we precompute in all circles that the points are in. |
Schneewittchen | Only the dangerous mines matter because we can put all not dangerous children's materials into them. Then, we have the following recursive constraint: |
The Augean Stables | Binary search over amount of hours worked, since more hours worked is more clean stables. Find minimum number of hours such that all are clean. |
Casino Royale | Model the stops as vertices, where the train goes through. Then, we model the missions as taking a seat from the train and going to destination, restricting the amount of agents that can be in the train at once. Need non-negative costs, so we need to add (y-x) * 128 to mission costs and 128 to train. |
DHL | Take exactly one from either stack each iteration, so the cost is additive, rather than multiplicative. |
The Fighting Pits of Meereen | DP where state space is (north history, south history, p-q ). Compute excitement from size of set that contains fighters. Then, paths are invalid if excitement is negative. Maximize the summed excitement. |
On Her Majesty's Secret Service | For each agent, compute the distance to each shelter. We can compute for a time t , whether it is possible for everyone to get to safety. This is done by bipartite matching. So, we binary search over it, because more time means more safe agents. Find minimum time necessary. |