Finding the maximum rectangle under a histogram

I heard this is classic, but turns out not too hard.

You're given non-negative numbers \(h[0],\ldots,h[n-1]\) representing a histogram. Find the maximum area of rectangle beneath it, i.e. \(\max_{i\leq j}(j-i+1)\min_{i\leq k\leq j}h[k]\) in \(O(n)\) time.

Solution:
Scanning \(h\) from left to right, we maintain a stack of \((height, last, cur)\). \(height\) is height, \(last\) is the last \(x\)-coordinate that is equal or above \(height\), i.e. the leftmost \(x\)-coordinate that covers \(height\), and \(cur\) is current \(x\)-coordinate.

The update logic is this. Suppose we're dealing with \(h[i]\). For each top element with \(height>h[i]\), replace the current maximum area with \(height\times (i-last)\) if the latter is larger. Remove the top element no matter what. Then, if (a) the top element has the same \(height\) as \(h[i]\), update its \(cur\) with \(i\); (b) stack is empty, insert \((h[i], 0, i)\); (c) top element has \(cur=l\), insert \((h[i], l+1, i)\).

When we're done scanning, for each \((height, last, cur)\) in the stack update maximum area with \((n-last)height\) if it's larger.

Finding singletons

For \(i\in\{1,2,3\}\), there are \(2n+i\) integers consisting of \(n+i\) unique ones. \(n\) of them appear twice, and \(i\) of them just once. Find these singletons in \(O(n)\) time with \(O(1)\) space.

Solution with \(O(\log n)\) space:
Too bad, that finding median takes \(O(\log n)\) space! Let \(algorithm_i\) be the algorithm that tackles \(i\) singletons. \(algorithm_1\) is to just XOR all numbers.

\(algorithm_2\): find median \(m\); if it's a singleton, apply \(algorithm_1\) to the rest; otherwise, count how many numbers are below and above \(m\). If both are odd, apply \(algorithm_1\) to each set separately, otherwise XOR all numbers in each set separately to find out which has two singletons, and then apply \(algorithm_2\) to that recursively.

\(algorithm_3\): find median \(m\); if it's a singleton, apply \(algorithm_2\) to the rest; otherwise, count how many numbers are below and above \(m\) -- one set has even size and the other has odd size.XOR all numbers in the even-sized set to check if it contains singleton. If it does, apply \(algorithm_2\) to it and apply \(algorithm_1\) to the other; otherwise apply \(algorithm_3\) recursively to the other.


Real solution:
\(algorithm_2\): XOR all numbers to get \(s\). From \(s\) find a bit \(b\) that is \(1\) in \(s\). Now there must be odd numbers with bit \(b\) equal to \(0\) and odd numbers with bit \(b\) equal to \(1\). XOR each set separately to get these two singletons.

\(algorithm_3\): If \(s\) is not zero, find a similar bit \(b\). There are odd numbers with \(b\) set to \(1\) and even numbers with \(b\) set to \(0\). Figure out if the second set has singleton by XOR, and act accordingly. If \(s=0\), find a bit \(b\) that not all numbers agree. There are even numbers with \(b\) set to \(1\) and odd numbers with \(b\) set to \(0\). Decide if the first set has two singletons by XOR and then proceed.

Online number partitioning

You have a bunch of numbers $a_1,a_2,\ldots,a_n$ each in the form of \(2^{-k}\) where $k\in\mathbb{N}$, and they sum up to \(1\). For example, $a_1=1/4, a_2=1/8, a_3=1/2, a_4=1/8$. You want to partition them into two groups of equal sum. It has to be done online: for each number $a_i$ you have to decide which group to throw into before knowing the value of $a_{i+1},\ldots,a_n$. You do not know $n$ in advance. How?

================================================

Solution:
For each number, if adding it to group \(A\) doesn't make it exceed \(1/2\), then do it. Otherwise add it to group \(B\). 

To prove its correctness, suppose that at some point we cannot add $2^{-k}$ to neither group. Let the smallest numbers in group $B$ be $2^{-m}$. We have $k<m$, or else we can add $2^{-k}$ to group $B$. Since we could not add $2^{-m}$ to group $A$, the remaining space in $A$ is less than $2^{-m}$. The remaining space in $B$ is at most $2^{-k}-2^{-m}$. Hence the total space is less than $$2^{-m}+2^{-k}-2^{-m}=2^{-k}.$$ This is a contradiction.

Balancing numbers

There are \(2n+1\) coins each associated with a weight. When we remove any coin, we can split the rest into two piles each with \(n\) coins such that the sum of one pile equals the sum of the other. Prove that all coins have the same weight.

Proof:
First I got this big hint to consider only integers, for which it is simpler: every number should have the same parity (again?!), and since adding a constant to all numbers or dividing them all by \(2\) when they are even does not remove the property, we can keep doing these to them. It is clear that initially all numbers are the same.

So why could there be no non-integer not all the same that hold the property? This has something to do with linear algebra. Essentially we are seeking the null space of a certain linear operator \(A\), and we want to prove it's \((1,\ldots,1)^T\). \(A\) consists of integer coefficients, and if its null space is not \((1,\ldots,1)^T\), then it certainly contains points with rational and therefore integer coordinates that are not all equal, a contradiction.

Numbers game

Given a sequence of \(n\) integers \(a_1,\ldots,a_n\), we map it to \(|a_1-a_2|,\ldots,|a_{n-1}-a_n|,|a_n-a_1|\). We repeat this process again and again until all numbers become zero. For what \(n\) is this process guaranteed to stop?

Solution:

Interestingly parity (not me!) plays a central role here. It turns out all sequences terminate if and only if all \(0-1\) sequences do. Why? If all \(0-1\) sequences terminate then any integer sequence eventually becomes an all-even sequence, and it doesn't harm to divide every number by \(2\), and the process repeats. Note that the maximum number in the sequence never goes up, and goes down by half each time they are divided by \(2\), so this process clearly will not go on forever than hence must stop.

So for what \(n\) could all \(0-1\) sequences terminate? It is not hard to show that if \(k\) qualifies, then \(2k\) does too, so all powers of two qualify. Clearly an odd \(n\) does not qualify, because unless initially all numbers in the sequence are equal, the second to the last step is obtain the alternating sequence \(0,1,\ldots,0,1\), which doesn't exist for odd \(n\).

What about an even \(n\) not a power of two? Here comes the most fun part. If \(n=(2k+1)2^m\), divide the sequence into \(2k+1\) blocks, each of length \(2^m\). Let each block starts with either \((0,\ldots,0)\) or \((1,0,\ldots,0)\). With the same argument used to show that \(2k\) qualifies if \(k\) does, we can show that after a cycle a block becomes \((1,0,\ldots,0)\) if either itself or the subsequent block is \((1,0,\ldots,0)\), and \((0,\ldots,0)\) if it is identical to the subsequent block. So, its behavior is identical to \(n=2k+1\) if \((1,0,\ldots,0)\) is considered \(1\) and \((0,\ldots,0)\) is \(0\). Since an odd \(n\) does not qualify, neither does \(n=(2k+1)2^m\).

No crossing!

On the 2D plane there are \(n\) blue and \(n\) red points, no three of them are co-linear. Then we can always pair a blue point with a red one and draw \(n\) segments between them, one from each pair, such that no two segments cross with each other.

My proof:
Induction is handy here. If the convex hull has points of both colors, we could isolate a red and an adjacent blue one with the rest, and induction will work. Otherwise, say all points on the convex hull are red and we shoot rays from a fixed red points \(u\) on the convex hull. Each ray divides other \(2n-1\) points into two groups, and we count the number of blue points minus the number of red points in each group. At some point these two numbers are \((-1,2)\) and at the other \((2,-1)\). Then one of the rays has one of the numbers \(0\), and the induction will work again.

Another proof:
When there is intersection, we can always replace the two intersecting segments by another two that don't intersect and reduce the total lengths of segment. The process cannot go on infinitely because the total length is bounded from below. Therefore there will be a time when we could not do this replacement anymore, i.e. no segment intersect with another.