# 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:

- 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:

- x
- 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:

**Problem Statement**

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 `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: