Favorites Round Up - Part 1

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

📖

Problem Statement.

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

📖

Problem Statement

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:

  1. sort the list
  2. guess the median
  3. 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:

  1. x
  2. the last k elements
  3. 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:

📖

Problem Statement

We are given a graph G with green and red edges.

  1. The subgraph F induced by the green edges ('friendships') partitions G into two cliques.
  2. 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:

  1. Are x and y connected by a red edge?
  2. Are x and y connected by a green edge?

Also - turns out friends and rivals live by three rules! Who knew, phew:

  1. Friendship is transitive.
  2. A common rival makes two people friends.
  3. 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 addGreenEdge() and addRedEdge() queries.

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: