Favorites Round Up - Part 1
The course on competitive programming has been a great way of exploring some really fun puzzles. Here is a recap of some of my favorites so far.
#1 Numbers Game: GCJ 2010 Round 1A, problem C
Two players are given two numbers x and y; and they can, on their turn, subtract any multiple of one of the numbers from the other one.
Task: for x and y in , how many pairs (x,y) are winning for the first player?
As a warm up, one could come up with a recursive strategy to figure out if a given pair (x,y) is winning for the first player.
So we could go over all (x,y) with x and y in and count the winning ones using this algorithm as a subroutine. Now it turns out... that's too expensive! ⏳
It turns out that there is a neat characterisation of when a pair (x,y) is winning, allowing us to only loop over all x in , and count - in one shot - the number of partners y that make winning pairs with x. This characterisation involves the golden ratio! Details here:
or if you prefer to read, check out the official editorial on which this video is based.
#2 Simple Skewness from 8VC Venture Cup 2016 - Elimination Round
The simple skewness of a set of numbers is its mean minus median. Given a list of (not necessarily distinct) integers, find a non-empty subset (with repetition) with the maximum simple skewness.
Noting that any singleton set has a simple skewness of zero, we know that the simple skewness of the optimal subset is non-negative. We could:
- sort the list
- guess the median
- guess the size of the subset (2k+1)
Note that it's ok to fixate on odd-sized subsets: if we have an optimal set S with an even number of elements, dropping the upper middle element does not decrease the simple skewness of the set, assuming that S has non-negative simple skewness. You can find a proof here.
A set with the best largest possible simple skewness, given that it has 2k+1 elements and median x, can be built out greedily! It consists of:
- the last k elements
- the k elements lined up behind x in the sorted order.
But this approach, at , is still too expensive.
It turns out that the way the mean evolves as you go over all values of k is bitonic (first increases, then decreases); and this is crucially because of the way the greedily chosen sets above evolve.
This can be shown using induction + the mediant inequality. Here's a blog with more details, and here's the corresponding lecture from the course:
3 War - UVa 10158
Despite the depressing problem name, this is a problem with some very nice structure. Here's the abstract setting:
We are given a graph G with green and red edges.
- The subgraph F induced by the green edges ('friendships') partitions G into two cliques.
- The subgraph H induced by the red edges ('rivalries') is a complete bipartite subgraph.
You don't get to see the edges. Instead, you have a stream of addGreenEdge(u,v) and addRedEdge(x,y) operations.
Every so often, you have to correctly answer queries of the form:
- Are x and y connected by a red edge?
- Are x and y connected by a green edge?
Also - turns out friends and rivals live by three rules! Who knew, phew:
- Friendship is transitive.
- A common rival makes two people friends.
- A rival of a friend is also a rival.
The thing that makes this a puzzle is that you'd like to efficiently track everything that you can infer from the
Simulating all possible implications is possible, but too expensive...
So this turns out to be a really neat application of the Union-Find data structure for the friendships + bookkeeping for the rivalries.
For those who like to read, some indicative hints can be found here, and here's also the lecture based on this problem: