Some Olympiad Problems
This page contains problems from computer olympiads that I authored or co-authored, as well as some CS puzzles. The problems on this page are from the Balkan Olympiad in Informatics (BOI), the Romanian National Olympiad in Informatics (ONI), the Romanian olympic team selection (LOT). Let me end with the message of the scientific committee from BOI 2003 (you can guess I was on the committee):
We want to assist contestants in their Computer Science training. Therefore, the competition problems aim to cover precisely the material contestants haven't covered at home. (BOI 2003 Magazine)
Contest Problems
[12] Sorting by reversals (ONI'04)
You are given an array A[1..N]. Your goal is to sort A by the following type of operation: pick some indices i,j and reverse the subarray A[i..j]. Such an operation costs j-i+1, i.e. the length of the portion which is reversed. Your sorting algorithm should have a total cost of O(N lg^2 N).
This is a classic problem related to computational biology. To develop a solution, we first find a way to sort sequences of zeros and ones in O(NlgN) time. This is done through a variant of merge sort. First, sort the two halves of the array recursively. Then, the array will look like: 0..01..10..01..1. All we need to do is to reverse the middle two sequences of ones and zeros, which has a cost linear in N. Now we can use this solution as a subroutine to solve the general case. Our algorithm is similar to quicksort, where we partition at each level around the median. To do the partitioning step, we need to move all elements smaller than the median to the left, and all the ones bigger to the right. This is done by marking smaller elements with zero and larger ones with one, and applying the zero-one sorting subroutine. You may find it interesting to think how to use radix sort instead of quick sort for the second part. To do that, you need to find a way to make the subroutine a stable sorting algorithm.
[11] Order statistics in the Farey sequence (BOI'03)
The Farey sequence of order N is the sorted sequence of irreducible fractions P/Q, 1<=P<Q<=N. The problem asks to determine the K-th fraction in the sequence. The algorithm should run in O(N (lgN)^2).
The first idea is to use meta binary search. Assume we have a subroutine that counts the number of fractions in the sequence less than a given value. Using this, we can do a binary search to determine the number X, such that the answer is between X/N and (X+1)/N (these fractions need not be irreducible). Then we can simply list all the fractions in the range (there are at most N of them) and find an order statistic. The needed subroutine can be implemented as follows. First create an array A[I] with the number of fractions (not neccesarily irreducible) with denominator I which are less than X. Then, at step I, subtract A[I] from A[k*I] for all valid k. This yields a O(NlgN) algorithm for the subroutine, and a O(N (lgN)^2) algorithm for the whole problem. Using some clever tricks, the time can be improved to O(NlgN) and the space can be reduced to O(sqrt(N)).
[10] Romanian investor problem (BOI'03; joint work with Mugurel Ionut Andreica)
A Romanian investor has two bank accounts: one in euro, and one in lei. Since the investor has a good credit history, the bank allows his accounts to contain negative amounts. All the transfers in and out of his account in euro are known for the following N days. At the end of any of these days, the investor can decide to bring his euro account to zero. Each time he does that, the balance of his account in euro is converted entirely into lei, and added to the account in lei. A tax of T lei is charged for this operation. On day D the parity is 1 euro = D lei. The investor is forced to bring his euro account to zero at the end of day N. The challenge is to maximize the amount of lei he has at the beginning of the N days.
First observe that you never want to convert a positive amount into lei (except on day N, when you're forced to). Indeed, if you wait longer, the parity will increase, so you get more money. If at any point you have a deficit, you might or might not decide to convert, depending among others on T. So first we do a "compression", where we add any positive inflow to the next day, until we get a negative amount. At this point, all remaining transfers are payments (except possibly on the last day, where we don't have a decision anyway). We handle these cases using an obvious dynamic program, which holds the best solution upto day D, if we do a conversion on this day. To get a good time bound, we hold a "back pointer" indicating the optimal day of the previous conversion for any D. Observe that these form an increasing sequence, so when determining the optimum for, say, day D+1, we don't need to look before the back pointer for day D. It is not hard to show (using elementary Math) that an optimal back pointer can never be more than O(sqrt(N)) transactions into the past. This immediately implies that the algorithm runs in time O(N*sqrt(N)).
[9] Grundy coloring of a tree (BOI'03)
A machine is passed a permutation of the nodes of a given tree. The machine analyzes the nodes in the order given by the permutation, and assigns to each node the smallest color (integer number) that has not been used to color an adjacent node. Determine the maximum number of colors that can be used, if the machine is given an appropriate permutation. The solution should be liniar in the number of nodes in the tree.
The solution is based on a rather nontrivial dynamic program. For every edge (u,v), imagine removing this edge, and obtaining two subtrees rooted at u and v. Interleaving the nodes of the two subtrees in the permutation does not help, so we can always put one subtree before the other (but which subtree is first does matter). For u (and similarly for v), we calculate the maximum color it can get by an optimal arrangement of the nodes in its subtree. We only care about the maximum, because if an arrangement guaranteeing color K exists, then there also exists another arrangement giving any color less than K. To calculate this value for u, we look at all children of u (in the appropriate subtree). For each edge connecting u to a child, we care about the maximum color achievable on the child's side (since trees we care about always shrink, this means that the DP is not cyclic). One final trick is needed to get linear time. Note that if u has C children, we compute some value for it C times, and look at the other C-1 children each time, which is clearly bad. But we can observe that the maximum color of u only varies by 1 in all these cases. This suggests a clever way to compute these values in O(1) for each child except the first two (we can obviously afford to do it in O(C) twice). Indeed, the second time we visit a node, we have information about all neighbors, so we can determine how "important" each one is. When we later consider any additional neighbor, we can determine in constant time the implications of not having this neighbor as a child.
[8] Majority coin (LOT'03)
You have N coins, of 3 possible types (gold, silver, bronze). One of these types forms a majority, i.e. there are > N/2 coins of that type. You do not know the type of each coin; the only possible operation is comparing two coins for equality (check whether they have the same type). You perform rounds of comparisons: during one round, you may do as many comparisons as you wish in parallel, but a coin may only be involved in one comparison. You must determine a coin of the majority type in an minimal number of rounds (this value is not specified in the problem statement).
There is a solution that only requires 3 rounds in the worst case, and this is optimal. In the first round, we compare floor(N/2) pairs of coins. If the coins of a pair are of different types, we ignore the pair. If N is odd, there is one coin not included in any comparison. Here's how to handle it: if the number of remaining pairs is even, pretend the single coin is actually the first "pair"; otherwise, ignore it. These rules insure that strict majority is preserved among the remaining pairs. For the second round, we form a list of the remaining pairs, and compare each pair with its predecessor and successor. Since a pair consists of two identical coins, we can perform two pair comparisons simultaneously (even if we have a single coin as the first "pair", this works because it has no predecessor, so only one comparison is needed). We now break the list into sets of adjacent pairs of the same type. In the third round, we compare each set with it's second predecessor and second successor. Now we have enough information to determine the type of every set relative to the type of its two closest predecessors, which is enough to solve the problem. It is also not hard to prove that 3 rounds is indeed optimal, though this requires some attention to detail.
[7] Repeated substring (LOT'03)
Given a string of N symbols, determine the longest substring which appears at least K times in the string. The solution should run in O(NlgN).
There is a very nice solution based on suffix arrays. First do the suffix array construction as follows. Perform lgN rounds; after round i each substring of length 2^i is assigned an integer ID, giving its position in the sorted array of all substrings of length 2^i. Each round runs in O(N) (use base-N radix sort). For this application, we keep the IDs from all intermediate steps, which takes O(NlgN) memory. We now apply meta-binary search to find the length of the required substring. Suppose we know the answer is at least L (we have assigned IDs to all substrings of length L and there are at least K identical values). Now, we want to test if the answer is at least L+delta. All we have to do is assign IDs to substrings of length L+delta and check if any ID appears at least K times. A potentially simpler solution is based on hashing; this solution is randomized and only requires O(N) memory. The idea is still to do a meta-binary search for the answer. To test if the answer is at least L, assign a hash code to every substring of length L and check if any hash code appears at least K times. Assigning a hash code to all substrings can be done in O(N); this test can be repeated, since it is probabilistic (if you select from a universal family of hash functions). The best implementation assigns large (32 bit) hash codes to strings, and puts them in a hash table for integers to count multiple occurances. Careful implementation yields excellent running times and astronomically low probabilities of error.
[6] Telegraph (ONI'03, extended team selection)
A telegraph machine can transmit only lines and dots; it takes 2 seconds to transmit a line, but only 1 second to transmit a dot. We generally want to transmit texts containing letters of the Latin alphabet, and digits (so we have N<=36 symbols in total). Therefore, a prefix-free encoding using lines and dots is needed. Given the frequencies of the N symbols in a large text, find the minimum time it takes to transmit the text using a suitable encoding. The solution should run in O(N^4) time, and use O(N^3) space.
This is a special case of Huffman coding with unequal letter costs (a polynomial solution is not known for the general case). We need to construct a modified Huffman tree, in which the right child of a node is considered at depth 2 below the node itself. If we take the level traversal of the leaves in this tree, the symbols must appear in decreasing order of frequency (by a greedy exchange argument). So we must only determine the topology of the tree. This can be done by conceptually building the tree from root to leaves using a dynamic programming algorithm; the state is given by the number of internal nodes one and two levels above, and the total number of leaves on upper levels. Note that we can construct the algorithm so that it doesn't need to include the level in the state (this is needed to get the required complexity). Constant factors are significantly improved if we implement this using a memoized recursive call (it turns out only about 10% of the array needs to be computed).
[5] Complete sorting network verification (LOT'02)
A complete sorting network is a sorting network with N input wires of depth D that has D*(N/2) comparators (so, it is "complete"). The problem is to verify that a given network actually sorts (more precisely, the problem was inspired by the 0-1 principle, and asked to count the sequences of 0's and 1's that are not sorted correctly). When N is even, the algorithm should run in O(3^(N/2) * D) time.
The first idea is that after the first comparator layer, there are exactly 3^(N/2) possible input sequences. Second, to test whether all these input sequences are sorted correctly, one need not simulate the network's behavior for every one, but rather generate the sequences in Gray-code order and only trace the 1-bit modification (easy to do in O(D) time).
[4] Sum of divisors (ONI'02, senior division)
Given A and B, calculate the sum of all divisors of A^B, modulo Q.
The solution is to find the prime factors of A, and the corresponding powers, and notice that the sum of all divisors can be expressed as a product of geometric sums, with a sum for every prime factor. It is also interesting to find a way to calculate a geometric sum modulo Q in logarithmic time. This can be done by writing 1+A+A^2+...+A^(2K-1) = (1+A^K) * (1+A+...+A^(K-1)). This recurrence is parallel to the recurrence for calculating A^K by halving K, so we can evaluate both in logarithmic time. Therefore, besides factorization, the problem can be solved in total running time of O(lgA*lgB).
[3] A family of diophantine equations (ONI'02, extended team selection)
Consider the diophantine equation: Sum(i=1,D):A[i]*(X[i]^3)=0 (with D fixed). Here A[i] are given coefficients and X[i] are integers. Count the solutions for this equation, with X[i] in [-L,+L], where L is given. The problem was inspired by Euler's sum of powers conjecture, and the idea behind the solution can also be used to search for counterexamples to the conjecture in an efficient way. This problem can be solved in O(L^(D/2) * lgL) time and O(L^(D/4)) space.
The idea is to move half of the unknows to the right hand side (classical meet in the middle attack), and merge the list of possible values for the left and right hand sides. Of course, we need to generate the list of possible values for one side in sorted order; this can be done efficiently by breaking the expression in two, sorting the O(L^(D/4)) possible values for each half, and then using a heap of size O(L^(D/4)) (we have O(L^(D/4)) "generators").
[2] Connected components on a grid (ONI'02, extended team selection; joint work with Roxana Tâmplaru)
Consider N points at different integer coordinates on a K*K grid. The points are given in lexicografic order (sorted by the x coordinate, and breaking ties according to the y coordinate). We consider two points adjacent if they are neighbors on the grid, and define a connected component in the usual way. The problem asks to list the number of points in each connected component. The algorithm should run in O(N lg*N) time and O(K) space.
The solution is not too hard to see: we scan the points in the given order, and organize the points in disjoint sets. Let's say at step i we consider the point P[i]. There can be at most two points adjacent to P[i] that have been scanned already. The first possibility is P[i-1]. To identify the second in O(1) time, we keep an index j<i among the last K points, "merging" the current column with the last one according to y coordinates. Then, at step i we either add P[i] to a connected component (set), or unite two connected components and add P[i] to the union. So each step can be done in O(lg*N) amortized time. The algorithm requires O(K) memory.
[1] Searching for substrings (ONI'02, senior division)
Consider a string of length N (large). You are given M (large) strings of length at most L (small), and asked to count the appearances of each of the M substrings in the long string. The problem is "on-line", i.e. a query must be answered before the next substring is read. The algorithm should use O(N) memory and O(N*L + M*L*lgN) time. [Note: there are data structures that give better time performance and still use O(N) memory; in the contest however, the memory restrictions were very strict and the constants hidden by the O-notation where very important.]
The solution uses a variation of suffix arrays. We sort all substrings of length L of the original string (this can be done easily in O(N*L) time using radix sort and it only requires 2*N pointers). Then we can do two binary searches for each given substring (to find the limits of the intervals and thus count the occurences). Contestants also had to use a "dirty" trick the halve the memory needed. The idea was to break the string of length N (which was about 2^18) into segments that could be indexed with the 16 bit pointers and work with each segment separately (this increases the running time, but doesn't use "large" 32-bit pointers).
Puzzles
[6] Middle third (probleme@ldc.ro, 2004)
Assume L is a regular language (i.e. accepted by a finite automaton). Consider L' = { b | (Exists) a,c : |a|=|b|=|c|, abc in L }, i.e. L' consists of the middle thirds of words from L. Is L' regular?
Consider an NFA (nondeterministic finite automaton) with states (x,y,z), where x,y,z are states of the DFA accepting L. We will make x trace a backward, y trace b forward, and z trace c backward. Formally, we have a transition from (x,y,z) to (x',y',z') iff in the original DFA: x' -> x under some character, y -> y' under the input character, and z' -> z under some character. The initial states are (x,x,z), where x is any state and z is a final state (formally, we have an initial state going through epsilon transitions to all these states). The final states are (x,y,y), where x is the initial state and y is any state.
[5] The missing number (probleme@ldc.ro, 2000?)
Given N and a set of N-1 distinct integers in the range 1..N, the problem is to determine the missing number, using little space. Think of N on the order of 100'000.
One might consider the following code, which tries to compute the sum 1+2+...+N and then subtracts each number from this sum; what remains is the missing number:
sum = n * (n + 1) / 2; for(i = 0; i < n - 1; i++) sum -= read_number(); return(sum);This doesn't always work. If N = 100k and we have 32-bit integers, the computation on the first line will overflow, and the result will be bogus. A very nice way to fix this is:
sum = n * (n + 1); for(i = 0; i < n - 1; i++) sum -= read_number() * 2; return(sum / 2);We have eliminated the division in the computation of the sum. Now sum will hold the correct value of twice the sum, modulo 2^32. By subtracting the double of each number, we are left with the double of the missing number. Since this is at most 200k, we have the correct value (not just modulo something), so we can divide and get the right answer.
[4] Compressing a file system
Suppose you want to back up a partition of your hard drive, and you want to compress it to save space. So, you take your favorite compression utiliy, and have it compress /dev/hd??. But the compressed file turns out to be much larger than the amount of data on that partition. Why, and how do you fix it?
This is because the compressor doesn't know that the free blocks on disk are actually free. These blocks typically contain junk left over from deleted files, and the compressor treats them as data. An easy and cute fix is: mount /dev/hd?? /mnt ; cat /dev/zero > /mnt/fill ; rm /mnt/fill ; umount /mnt. This will zero out all free blocks, and the compressor will only work hard to compress the actual data.
[3] Binary search with addition and subtraction (probleme@ldc.ro, 2004)
You are given a sorted array A[1..N], and you want to search for a given element. But you may only use additions and subtractions, and O(1) memory. Can you obtain O(lgN) running time?
Instead of searching based on powers of two, we can search based on Fibonacci numbers, which also grow exponentially. Maintain the current search range to be [a, a + F(k)] and keep F(k), F(k-1) in two registers. Then, you can compute F(k-2) by one subtraction and test A[a + F(k-2)]. The new range is either [a, a+F(k-2)] or [a+F(k-2), a+F(k-2) + F(k-1)]. We can compute the needed Fibonacci numbers based on the previous two, and throw the old ones away.
[2] Greatest common divisor (probleme@ldc.ro, 2004)
Given N numbers between 1 and U, find their greatest common divisor in O(N + lgU) time.
The simplest algorithm works: find the GCD of the first two numbers, then the GCD of this value and the third number, and so on. Each GCD is computed using Euclid's algorithm. This takes time O(1 + lg min(a,b) - lg gcd(a,b)) -- in the first step, the maximum drops below the minimum; then after every two iterations, the current maximum drops below a half, and the algorithm stops when it reaches the gcd. Over n calls, this sum telescopes because one of the input numbers is the output gcd of the previous call.
[1] The halting problem (probleme@ldc.ro, 2003)
Given the description of a program and an input, the halting problem asks whether the program eventually halts on that input. Prove that the halting problem is undecidable, via the busy beaver problem. A busy beaver is a Turing Machine with N states, which, starting from a blank tape, writes the maximum number of ones possible on the tape, and halts (call this value f(N)).
First we'll prove that f(N) is an uncomputable function. Begin by observing that it is an increasing function (for example, we could add isolated states that don't matter). Assume now that there exists a Turing Machine computing f(N). Since this machine is fixed and finite, it has O(1) states. Build another machine, which contains the description of a number N. This machine will run the original machine to compute f(N), then it will count between 0 and f(N)+1 outputting ones. The number of states of this machine is O(1) in addition to the states needed to enconde N, which is at most poly(lgN) using binary encoding. Since this machine outputs more than f(N) ones, we have f(poly(lgN)) > f(N) so the function is not increasing, contradiction.
Now we prove that the halting problem is undecidable. Assume some Turing Machine decided the halting problem. Then we could compute f(N). Given a number N, we could iterate through all possible machines with N states (a finite number). For each such machine, we could first test whether it halts. If not, it cannot be a busy beaver. Otherwise, we simulate the machine and count the number of ones it outputs. At the end we output the maximum for all machines.