Competition Committee - March 8, 2021

We hope you had fun during the contest! On this page, you can find the solution sketches to the problems in the PROG-A-THON. You can also download the testdata that we used to judge your solutions here. So if you want to find out which testcase your solution failed on, you can test that out yourself with the data. If you still have any questions about the solutions to these problems or you want to know for example why your solution got a Wrong Answer or Time Limit Exceeded verdict, you can of course always send us an email at competitie@svia.nl.

1: BBQ playlist

Testdata: download

You were given $n$ song lengths and a crossfade of $c$ and you should determine how long it takes to listen to the complete playlist.

The first step is to convert the m:ss input format into just seconds. Then we subtract (n-1)*c seconds for the crossfades. Finally, we convert the seonds back to the hh:mm:ss format.

You should only do the conversion back to minutes at the latest step. Otherwise, 1:00 minus 10 seconds might become 1:-10 instead of 0:50!

2: Fun with fractions

Testdata: download

To solve this problem, suppose you are given a fraction in the form x/y. Then you can simply convert it to a mixed fraction by calculating z = (x // y) and w = (x % y). The answer is then equal to z w/y.

3: Archery

Testdata: download

Per testcase, for every (x,y) one should find the smallest p such that x*x + y*y <= 20*20*p*p holds. This can be done naively in a for/while loop, as well as with integer division (both are fast enough). Add 11 - p to the score counter and print it at the end of each test case, but only if p < 11.

Pseudocode to calculate points for a shot at (x,y) python for p in 1..11: if x*x + y*y <= 20 * 20 * p * p: points += 11 - p break

4: Hospital routing software

Testdata: download

The problem here was to find the shortest path from A to B in a 'half-circular grid'. One way you could do this (that would be within the time limit) was to simply run Dijkstra.

However, if you think a little bit more about the problem, there is a shorter, faster solution possible. The first observation is that every shortesdt route consists of at most three parts: first, walk towards the center, then walk along a circular arc and finally walk away from the center.

So you could also loop over all the relevant circle arcs and find the shortest path among them. In fact, because you are optimizing something linear, the shortest path is always either the outermost or the innermost route.

Example pseudocode:

def route(x, y, r, x1, y1, x2, y2): center_route_length = (y1 + y2) * (r / y) inner_route_length = abs(y1 - y2) * (r / y) + \ abs(x1 - x2) * (pi * min(y1, y2) * (r / y) / x) return min(center_route_length, inner_route_length)

Complexity: O(n), O(1)

5: Cheating the system

Testdata: download

For each Program Committee simulate how many votes are needed to achieve a majority. This can be done by taking one vote at a time from the currently highest voted party and adding it to the party of via. This can (but doesn't nessecaryily have to) be speed up by taking enough votes at a time from the currently highest voted parties until they are equal to the next highest voted party.

Then, (greedily) take the districts that need the fewest votes until party via has won the majority of Program Committees. Print the sum of the votes of the districts you have picked.

6: Trampoline

Testdata: download

The general idea to solving this problem is to convert the problem into a graph. You create a node for every trampoline and the start and end point. You can easily calculate the shortest path between any two of these nodes: either walk directly from start to end, or (if you start at a trampoline) use the trampoline and walk the remaining distance (always launch in the same direction as where you are headed).

On the resulting graph you can run a shortest path algorithm such as Dijkstra to determine the shortest path.

Complexity: O(n^2 log(n))

7: Movie maker

Testdata: download

Suppose that you want to have item $i$ lexicographically at the $p_i$th place by value. Compose every name from three parts:

'1' + i + '0' * p_i

Where the number i is padded to a fixed width. '0' * p_i means that we pad the number with p_i zeroes.

8: Perseverance's traveled path

Testdata: download

Problem: given an path of n vertices v_i and arrival times a_i, and a sampling time interval t, find the path recorded by the navigation system and compute the relative loss of distance.

The first position of the estimated path is always v_1 at time 0. Then for each time interval, find the position on the actual path for the next vertex. Compute the distance for both paths and compute the difference.

Example pseudocode:

``` s_real = 0 s_record = 0 p = v_1

for g in 0,t,2t,...,a_n Find the next vertex v_i having g < a_i. Compute p1, the position at time g, by interpolating between v_{i-1} and v_i. s_record = s_record + ||p-p1|| p = p1

Print percentage (s_real - s_record) / s_real ```

9: Meshed security

Testdata: download

Implement your favorite path finding algorithm from top to bottom, implementing a system to prevent passing sensors (or rather; circles). Then, one by one add the sensors, until you can no longer reach the top.

10: A Farewell to the Table Football Table

Testdata: download

The problem is to find a subset of a given sequence of positive integers a_1 ... a_n such that a_i >= 2a_{i-1} that sums to t. Thus we know that a_i > sum(a_1 ... a_{i-1}). Therefore the solution must use the largest a_i such that a_i <= t. To solve this problem we must substract greedily the largest number that is smaller or equal to t, until t = 0. If this turns out to be impossible we print 0 and exit, otherwhise we print the names that correspond with the chosen numbers.

It is important to note that a_i can be a very large number. Therefore a language must be used that has big integers or you should implement big integers yourself. Surprisingly, for this reason it is the easiest to solve the problem in python, because python supports big integers out-of-the-box.

11: Fairy Park

Testdata: download

The problem is the following: given a graph G = (V, E), per node a time tv and a cost cv , and a time t∗for all edges. You are traversing the graph starting at 1 and at every node you pass you have stay kt_v time and spend kc_v money with k ≥ 1. What is the least amount of money you need to spend such that you arrive at 1 after X time?

The problem is a variant of Knapsack. The time is the “weight”, X is the size of the bucket, and cv is the “gain” of an edge. You should extend the standard Knapsack-DP to handle the graph structure. Use DP over the current node v and the time t you can move freely from e. Finally, you should add a special treatment for entering the park. The answer is therefore dp(1, X - t_1) + c_v.

12: Completing the puzzle

Testdata: download

The problem here is to assemble a puzzle consisting of pieces that all have unique edges. A possible approach you could take is the following:

• Choose an arbitrary puzzle piece and place it at the origin (0,0)
• Perform a breadth-first search from this piece and fix the coordinates and orientation of the other puzzle pieces as is needed to fit these pieces.
• Check that this solution is indeed valid (i.e. there are no gaps, there is no overlap, the puzzle is rectangular)

Note that each step can be done in at most linear time.

Complexity: O(n)

13: Memory management

Testdata: download

The general idea of this problem is to find, given a sequence of numbers $a_1, \dots, a_n$, a contiguous subsequence that maximizes the greatest common divisor of that subsequence multiplied by the length of the subsequence.

Because of the bounds, a quadratic solution that simply calculates this number for every contiguous subsequence is too slow.

Enumerate the right boundary j from left to right. Store the smallest left boundaries i where i <= j that give a distinct GCD and calculate the maximum.

14: Climbing wall

Testdata: download

Problem: scale a climbing wall without running out of stamina

We can observe that the required stamina is at most h * w * 9 = 5625. Solution outline: * Create a set of graph nodes from all reachable holds on the wall. * Copy every node s times to count the remaining stamina at that hold. * For an edge from hold u to v taking t amount of stamina, insert an edge from every copy of node u to every node v with exactly t less stamina remaining. * Use Dijkstra's algorithm to find the shortest path from the bottommost hold to the topmost hold, and compute the total distance of the path.

15: Ordering student IDs

Testdata: download

The essence of this problem comes down to finding indices $i < j$ that describe a minimal-length substring of the IDs such that the order with respect to the substring is identical to the original order.

Note first of all that if any two subsequent strings $s_k$ and $s_{k+1}$ are ordered correctly w.r.t. substring $(i,j)$, then all strings are ordered correctly.

For each index i, we compute $\alpha_{ki}$, the smallest index such that $s_{k}$ and $s_{k+1}$ are sorted correctly w.r.t the interval $(i, \alpha_{ki})$. We can determine all $\alpha_{ki}$ for two subsequent strings in O(l) if we use dynamic programming.

We then determine for each index $i$ the maximum $\alpha_{ki}$ over all $k$ and we finally output the sortest interval among all $(i, max_k {\alpha_{ki}})$

Complexity: O(n*l)

16: Mirrors

Testdata: download

The problem here is to find out how many orientations there are in which we can send a light particle so that it reaches the end point (possibly making use of the one-time mirrors).

Note that because a mirror disappears after reflecting a particle, there can be only one solution for every subset permutation. Because N is smaller or equal than 8, we can iterate over all subsets and permutations.

For a subset permutation, we can mirror the plane and its elements for each mirror to model the reflected world. Then finally we can simply find the angle of the line between start and end.

Furthermore, you need to ensure that you handle corners correctly: if the particle would travel too close to a corner, you should ignore it.

Complexity: O(N^2 * N!)