So the qualifying round is over and ~1500 people (including me ) got all the questions out successfully. 8523 people got the required 33 points to advance to the first round.
Questions were very mathematical, only the 3rd question really had any algorithmic design to it.
Q1) This was an amazingly convoluted way of asking when an n bit integer is all 1’s. It boiled down to k % (1 << n) == (1<< n)-1, a single line. I suspect the problem was inspired by reading Knuth. He has a section where he describes the bit effect of adding 1 to a number (among other things…) the least significant 0 and all less significant bits toggle. Which is the same as how a chain of ‘snappers’ was described to work.
Q2) This was a very mathematical question, with a barb to annoy anyone who’s programming language doesn’t include a big integer. The question was given a set of up to 1000 numbers, what is the maximum common divisor you can get by increasing them all by the same a non-negative integer, and more specifically what is the minimum non-negative integer which gives that maximum common divisor. The kicker being that the numbers were anything up to 10^50, so they won’t fit in a 64bit integer.
The solution comes from identifying an upper bound on the common divisor of n numbers is the GCD of the absolute differences between the numbers. Then if the minimum number is a multiple of the GCD the rest of the numbers will be as well, which is always achievable for any set of numbers. For .Net 4 the problem was trivial – BigInteger has a GCD method, so you just parse the numbers, calculate the absolute differences, calculate the gcd, calculate the mod of any entry with respect to the gcd, and if non-zero subtract that from the gcd to get the minimum shift. GCD can be implemented using euclid algorithm if it wasn’t there. And if you didn’t have biginteger, good luck… My code had one change compared to the description above. I sorted the entries rather than calculate absolute differences, but I’m pretty certain that isn’t required.
Q3) This problem had the longest implementation, but is mathematically simpler than problem 2. The question was given a roller coaster with k seats and n groups of people of specific sizes in a specific order and the roller coaster does R runs per day and every paying customer is worth 1 dollar and everyone who went on the roller coaster goes back on the end of the queue in the same order they went on to the rollercoaster (no one ever leaves), how much money will the roller coaster operators get in a given day?
So it is a simple simulation problem, but R can be extremely large, making simulating all of them too expensive. Also k*R can be larger than 32bit integer, so you need to be careful you don’t overflow using 32bits at inappropriate times. The algorithmic key here is to identify that the simulation of a run is always the same for any given starting offset into the queue, so you only have to consider at most 1000 simulations (the maximum value for n). The final piece is to realise that if you ever get back to the same starting person, you have started a loop and that sequence of simulations will be repeated. The loop may not start from the first simulation, but a loop will exist eventually, the loop cannot be longer than 1000 entries. So to calculate the answer you break it into 3 parts. 1) Simulate until loop discovered. 2) Calculate the sum of the loop and determine how many more times it needs to be run to get up to R (using integer division). Calculate that product. 3) Calculate the modulo to determine the final partial loop and sum those steps. Those 3 numbers are summed to give the answer. Of course if R is too small you may not need step 2 or 3.