A k-ary week

Last week, the 200 participants of Facebook Hacker Cup Round 3 were fighting for the 25 spots in the Seattle onsite (problems, results, top 5 on the left, analysis). This time double- and triple-checking was not the best approach, as one needed to solve the first three problems quite quickly to get through. Congratulations to Egor on the victory!

The hardest problem required both a careful implementation and several key insights. You are given a sequence of n positive integers h_i, and a number k. You're allowed to do the following k times: take an integer, and decrease it by 1 (but it must remain positive). After you do this, we compute the maximum value of h_i+h_j+abs(i-j). How small can this maximum value be?

In my previous summary, I have mentioned two interesting problems. The first one, coming from TopCoder, asked to find any sequence of 500 positive integers up to 10¹⁸, such that any two adjacent numbers in this sequence are coprime, and any two non-adjacent numbers in this sequence are not coprime.

As usual with such "constructive" problems, a lot of different approaches are possible. I think the most beautiful approach is the randomized one, as described in the analysis. Let's take the first n primes, and each of the 500 numbers will be a product of some k of them. To build the sequence, we will pick each number at random from all possible products of some k of those primes that do not include the k primes used to build the previous number. This will guarantee that adjacent numbers will be coprime. After generating each number, we will also verify if it's coprime with any other number except the one directly preceding it. If yes, we'll regenerate it again at random, and so on until this number fits, then move on to the next number.

Why does this work, and how to pick n and k? I can only offer some advice partly based on intuition here. Obviously k must be chosen in such a way that the product of the largest k of the first n primes does not exceed 10¹⁸. Also, k must be close to n/2, but not too close :) Basically, the higher is k, the more likely it is for two random numbers with k bits out of n to share a common bit. However, when k approaches n/2 a different mechanic comes into play: the bits (primes used) in the sequence start to alternate, and thus the numbers at an odd distance are more likely to be coprime. Practically speaking, n=23 and k=10 seems to work with a comfortable margin. Still, it's not entirely clear to me how to expect this solution to work before trying it out - I think it requires the right kind of statistical intuition.

The other problem I mentioned was from AtCoder: you start with n zeros and m ones on a blackboard, and you're also given a number k such that k-1 divides n+m-1. You repeatedly pick any k numbers on the blackboard, erase them, and instead write their arithmetic mean (which is not necessarily an integer). Since k-1 divides n+m-1, you will eventually end up with just one number. How many different values can this last number have? n and m are up to 2000.

The right approach to this problem is to build a rigorous mental model of what's going on. We can view the computation as a rooted tree: the root of the tree corresponds to the final value, each non-leaf node has exactly k children corresponding to the values used to obtain the value of this node, and there are n+m leaf nodes corresponding to the original numbers, each containing either 0 or 1, with exactly m 1s. There will be d=(n+m-1)/(k-1) inner nodes in the tree.

We can then notice that the final value is uniquely determined by the depths of each 1 leaf node. More precisely, a 1 at distance p from root contributes 1/k^p to the final value. Now it's clear that the final value must be representable as x/k^q, where q<=d. For a given value, let's pick the minimum such q. How do we determine if it's representable given x and q?

Representing x/k^q as a sum of m terms of form 1/k^p is equivalent to representing x as a sum of m terms of form k^q-p. In other words, we need to represent x in k-ary system with sum of digits equal to m, but where each digit can be arbitrarily big. It's not hard to see that the minimum sum of digits is achieved if we use the standard representation of x in k-ary system, and all other representations are obtained by replacing one of the 1s with k smaller 1s. We can make at most d-q such replacements (since q out of d tree nodes are already used for the initial representation).

To summarize, for each q<=d we just need to count the amount of numbers x with q digits in k-ary system with sum of digits equal to m-(k-1)*y, where 0<=y<=d-q, and with nonzero last digit. This is now a standard dynamic programming task, and note that we didn't need to have any insights or magical ideas to arrive at it - just gradually expanding our understanding of the problem domain.

Thanks for reading, and check back next week!