# PROG-A-THON March 2021 solution sketches

#### 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!)