Competition Committee - May 1, 2020

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: A Tough Night

Testdata: download

This problem essentially came down to checking that the input list was 1,2,3,...,n except that some of the elements might have been replaced by “unintelligible”. One way to do this is to create a for loop from 1 to n, and check whether the ith word is either equal to i or “unintelligible”.

Complexity: O(n)

2: Railway Turntable

Testdata: download

In this problem, you had to calculate the shortest distance between two angles a and b. For a solution to this problem, you needed to subtract the two angles from each other and analyse a few cases. An example of a solution is the following:

def solve(a, b):
        if b - a > 180:      
             return b - a - 360          
        elif a - b > -180        
             return b - a            
        else:       
             return b - a + 360

There are of course also different ways to calculate this. Two important caveats were that your angle had to be negative if the angle was counter-clockwise and that it should output 180 instead of -180 when the numbers are diametrically opposed.

Complexity: O(1)

3: Cramped Trains

Testdata: download

For this problem, you were given the capacity of the train and a list of how many people entered the train, left the train or had to wait because there was no room. You had to check whether this data was consistent.

To solve this, you could just simulate the train trip. Keep track of the number of passengers p, which is 0 initially. At each station, do the following: Check that no more than p passengers leave the train Update the number p Check that p is not more than the capacity of the train Check that passengers only wait if the train is full Lastly, check that the train is empty at the last station.

Complexity: O(n), with n the number of stations

4: Outsourcing Code

Testdata: download

This problem was about finding out how many days are needed to finish a project if you outsource the components to others and you know how long each component takes to finish. It costs you 1 day to explain a component to someone else and you can only explain a single component each day.

The insight here was that it is optimal to outsource the components in descending order of the time the component takes to finish. You could then solve the problem by sorting the components on decreasing time and outputting max(position + dev. time + 1)

Complexity: O(n log n), with n the number of components

5: Path Tracing

Testdata: download

In this problem, you were given a start and end position and a set of instructions. You know that exactly one of these instructions is incorrect and you need to figure out which one.

What you could notice here is that the instruction list had a length of at most 50, so you have enough time to try out every possible (single) modification to the instruction sequence until you find one that works. You loop through all the instructions and for every instruction try replacing it by Left/Right/Forward and then check if this new instruction sequence leads you to the target.

Complexity: O(n^2), with n the number of instructions

6: ViAs AtOMoS

Testdata: download

For this problem, you were given a list of words and had to check whether it is possible to form the words using only elements from the periodic table. The difficulty here is that some letters appear as the starting letter in multiple elements. For example, we have both “B” and “Ba”, so if your string contains “ba”, you have to choose one of the two. Note that choosing greedily does not work. The word “bal” is possible to form using “B” and “Al”, but not if you choose “Ba” first.

You could implement a recursive algorithm that when faced with a choice such as between “B” and “Ba” tries both possibilities. However, this leads to an exponential time algorithm and since n can be at most 50000, this will be too slow.

The solution to this problem is a dynamic programming approach. You keep track of a boolean array subword[k] for 1<= k <= n indicating whether it is possible to form the subword from the start up to the kth position. You start by initialising subword[0] to true and then set subword[k] to true if: word[k-1] is true and the last letter forms an element symbol, or; word[k-2] is true and the last two letters form an element symbol Once you have calculated subword[n], you know whether the whole word can be formed.

Complexity: O(n), where n is the length of the word.

7: Call Center

Testdata: download

You are given a list of timestamps of when calls are placed, which all take 1000 milliseconds. You need to figure out how many employees, who can handle k calls at once, you need so you can handle all calls without any delay.

The first insight here is that you can see any call ti as an interval (ti, ti + 1000). The question then becomes to find the maximum number of intervals that overlap.

The general idea to solve this is to loop through all incoming call in the order they occur. At the same time, we keep track at each time point how many calls are taking place concurrently. However, note that we require a solution that runs in linear time, any solution in quadratic time will be too slow. So we need to be careful here to do this in a smart way so that we can keep track of this number of concurrent calls in constant time.

We can do this by using a queue datastructure as follows: Put all incoming calls in a FIFO queue according to call time Before a new call is added, pop all the calls that are at least 1000 ms old Keep track of the maximum size S of the queue Output ceil(S/k)

Complexity: O(n)

8: Door sensors

Testdata: download

Given a directed graph, you need to report two things: (a) which buildings are no longer reachable from the entrance and (b) from which buildings is it impossible to reach the entrance.

For problem (a), you can do a depth-first or breadth-first search from the entrance. While you perform this search, mark all the visited buildings. All the unmarked nodes at the end of your search are the unreachable buildings.

For problem (b), you can do something similar. However, now we reverse the direction of all the edges. We then do a depth-first or breadth-first search from the entrance. All unmarked nodes now represent the buildings from which you become trapped.

Complexity: O(n+m), where n is the number of buildings and m the number of connections

9: Chocolate Board

Testdata: download

In this problem, your goal is to split a nm bar of chocolate into piles of size a and nm - a by breaking it horizontally/vertically as few times as possible. You can solve this problem with the following observations: One split is sufficient if a is divisible by n or m Two splits suffice if a can be factored into a = x*y where x <= n and y <= m, or if n*m - a can (You can check this in O(n) time by trying all possible values of x) Three splits are always sufficient

Complexity: O(n)

10: A different game of chess

Testdata: download

This problem is about a simplified form of chess where you only have pawns that cannot change columns. The player who makes the last possible move is the winner. Your goal is to find out who wins if both players play optimally.

Note first of all that the only real choice that the players have is whether to move a pawn in the starting position two places forward or just one place forward. Let us call a pawn that can (still) move two squares a wildcard. If there are no wildcards left, it is simply a matter of parity. If the player to move has a wildcard left, while his opponent does not, he can win by using his wildcard to “set the parity” in his favour.

The strategy is then to neutralize the opponent’s wildcards by moving your pawns forward in those columns. If one player can manage to neutralize all wildcards before his opponent, he wins. If both players neutralize each other’s wildcards at the same time, it is down to parity.

Lastly, what if both sides have a wildcard in the same column? If n > 4, these columns can be ignored: the player who would win in the absence of these columns, can wait for his opponent to move in one of these columns and respond appropriately in the same column.

We need to analyze the special case n=4 separately. If the number of columns with double wildcards is even, the columns can be ignored: the winning player can copy his opponent’s move in another column. If the number of columns is odd, White wins, since he can set the parity in his favour.

11: Magic Store and the Troll

Testdata: download

The problem becomes easier to analyse if we assume that instead of giving our Troll one piece of information (namely the item that we just walked out of the store with), we give it our whole strategy. This of course does not help us, but it also does not help the Troll. A strategy here is a sequence (s1, s2, …, s_{k+1}) of items (where the Troll can destroy at most k items). The Troll chooses which item we can keep, and the price we pay for this is the price of this item plus all the previous ones.

The key observation is now that for the optimal strategy for us, it always holds that value(s1) <= value(s2) <= .. <= value(s_{k+1}). So a sequence that is increasing with respect to value.

We can then solve the problem using dynamic programming. we sort all the items such that value(1) <= value(2) <= .. <= value(n). We then let dp[i][q] denote the optimal gain for the set of items {i, i+1, .., n} with the Troll able to cast his spell q times.

If we want to pick item i, then either: the Troll lets us have it: value(i) - cost(i) the Troll destroys it: - cost(i) + dp[i+1][q-1] Of course, the Troll chooses the worst of these two options. We also have the possibility of ignoring item i, but then we should never get back to it (as the optimal strategy is to visit the items in order of increasing value). So the complete dynamic programming recurrence will be: dp[i][q] = max(dp[i+1][q], min(value(i) - cost(i), -cost(i) + dp[i+1][q-1]))

Complexity: O(nk), where n is the number of items and k the number of items the Troll can destroy.

12: Congo’s experiments

Testdata: download

In this problem, you need to find the number of “loops” in a 2d grid. You can assume that loops do not overlap and always have exactly two neighbors.

A possible way to solve this problem is to loop through every cell and keep track of whether we have already visited this cell. If we find a ‘#’ cell that has not yet been visited, we increment the number of found loops by one and subsequently visit all ‘#’ cells in this loop until we are back at the starting cell (and mark them all visited). Because all the ‘#’ cells have exactly two neighbors who must be part of the loop, it is easy to find the next ‘#’ cell to visit in the loop.

Complexity O(m*n), where m is the height and n the width of the grid

13: Choosing the next problem

Testdata: download

The problem consists of finding out whether you can make a uniformly random choice of n elements with a k-sided die and returning the smallest t such that this is possible.

The first insight is that this essentially boils down to finding the smallest t such that k^t is divisible by n. One way to do this efficiently is the following: compute k, k^2, k^3, … modulo n by repeated multiplication and stop when you get zero. The answer is at most log(n), which is at most 29, so stop when you get there.

14: Cavia

Testdata: download

First of all, note for this problem that the problem essentially boils down to finding the longest string from the dictionary of words that starts on a given index. Once you know for every starting index the longest string starting on that index, you can solve the problem by greedily iterating (starting from position 0) and finding the length of the longest string which can be added to the already matched part.

Because the text and the dictionary both can have length of 3*10^5 characters, we need to be careful how to do this. If you do this naively (i.e for every starting index loop through all the strings in the dictionary), you will get a quadratic running time, which exceeds the time limit.

There are a few different approaches to do this smartly: You could create an Aho-Corasick automaton using all strings from the dictionary Create a suffix array from all concatenated strings from the dictionary and make an LCP (longest common prefix) array. Then iterate over it, keeping the minimum from the last dictionary string to find the number. Divide strings on input by those which are longer than sqrt(N) and the rest. For those longer, we use the KMP algorithm. For those shorter, we use a trie.

Complexity: varying from O(n) to O(n sqrt(n))

15: Tetris

In this problem, you need to write a Tetris AI that can always clear at least one row. Note first of all that because the game uses a bag randomizer, you are guaranteed to get any specific piece every 14 pieces (you cannot get the same bad piece over and over).

Because this is a simplified game, you cannot slide pieces under those already placed. So if the first piece is an S or Z, it becomes impossible to clear the first row. However, with the right orientation of pieces, it becomes possible to clear the second row using each of the 7 tetrominoes.

So the solution is to build the second row from left to right, always rotating the pieces appropriately. If the current piece is too wide, drop it on the left instead. If you do this smartly, you will always be able to clear the second row before you fill up the whole field.