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)

[12]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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).

[6]

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]

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

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

[4]

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]

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]

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]

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.