The sixth day lets us build a »Voronoi diagram« under the Manhattan distance, where the seeds are given.
To crack the problem, we need to figure out which cells in the diagram will turn out to be infinite. For this, we use two ingredients:
- The function
closestcalculates the seed closest to a given point, returning 0 in case of a tie and index of the closest seed (starting at 1) otherwise.
- Manually hardcoding the size of a “sufficiently large” bounding box of all seeds, the infinite cells will correspond precisely to:
Finally, we need to calculate the size of the largest finite cell.
The second part asks us to calculate the number of grid coordinates with a total sum of distances from all of the seeds less than 10000. All needed to do here is to find the size of another, for this problem “sufficiently large”, bounding box. Next, a simple bruteforce iteration suffices.
In the seventh day, we are given a list of instructions/tasks, together with constraints saying that some tasks must be performed before others. We will be interested in “optimal” ways to perform the tasks.
To simplify sum cumbersome operations with the graph, we will use some functions from the
Given a graph of dependencies, the first part asks us to find the lexicographically smallest topological ordering of this graph. This is something that
networkx already has a function for.
In the second part, we are given additional information: for each task, we now know the amount of time it takes. Our workforces has now been increased to 5 workers and we are interested in knowing the smallest possible time in which our workers can complete all of the task. We opt for greedy approach. At each iteration we either:
- see that some worker is free, in which case we assign to him the least-time consuming task from all tasks which are available at the moment.
- see that all workers are busy, in which case we can fast-forward the time until some of the workers finishes his task. We then mark the task as done and free the worker.
We also note that the first part might have been solved by setting
nworkers = 1 and printing the tasks as they get assigned to the single worker.
In the eight day, we are given tree flattened in a specific recursive way. Given this flattened version, we are supposed to perform some calculations involving leaves of the tree.
In the recursive functions below, we will be accessing the elements of the list from the back, we thus reverse the list immediately during parsing.
In the first part, we need to sum up the values attached at each leave. This is quite easy to do just by mimicking the flattening process recursively. Note that we, very conveniently, use the
pop() function of Python lists, which allows us to consecutively, and recursively, iterate over the whole list.
In the second part, rather than summing up the values attached at the leaves, we will need to sum up scores calculated at each node. The calculation of the score gets more involved, but can be still done just by mimicking the flattening process recursively.
In the ninth day, we are given a circular list of marbles, into which we will be inserting new marbles in a specific way, placed by players taking turns.
The first part asks us to simulate the game. Since any new marble will be placed within small distance 7 from the last one, we can simmulate the whole game via rotation of the circular array. This can be done very efficiently using the Python’s
deque, which offers precisely the operation of rotation (both clockwise and anticlockwise). We then blindly implement the rules of the game as given by the problem statement.
In the second part, we are required to do nothing else than to play the game with a bigger amount of marbles. Since the implementation with
deque is sufficiently fast, there is nothing else to do.
In the tenth day, we are given a collection of particles in a grid, together with their corresponding velocities. We are told that the particles will align to form a sentence at a particular nonnegative time.
Apart from parsing of the input, we prepare for the first time a utility function that will be needed: The »ternary search«, which can minimize a convex function in a logarithmic time.
In the first part, we are supposed to find the sentence formed when the particles align. For this, we will use the following heuristic (which is not guaranteed to work in general; if we however assume the given velocities to be somehow random, this heuristics will do well): we will try to minimize the diameter of the set of particles, where the diameter is defined as:
Since this function is first decreasing and, after reaching its minimum, increasing, we may use ternary search to find the minimum. After calculating the optimal time for the diameter to be minimal, we simply print the positions of the particles.
The second part only asks us for the time when the particles align. This has been already calculated.