Q1) 2 people take turns to remove powers of 4 from a number which starts with n. Where each player tries to be the last person to remove a number determine who succeeds. n is up to 1 billion.
A1) This problem seems to be one of ‘solve by inspection’. Simulate the first few thousand values of n using dp and you’ll quickly see that the results form a regular pattern. 2 out of every 5 return player 2, the rest return player 1. Mathematical induction can be used to prove that the pattern continues by noticing that all powers of 4 are either 1 or 4 mod 5. In the end the code boils down to k = n mod 5; return (k == 2 || k == 0) ? “player 2” : “player 1”;
Q2) Given n cards which each have a number on the front and back such that numbers 1 to n each occur exactly once on the front and exactly once on the back, determine the number of different lists of n numbers which can be formed by reordering the cards in any order, with any face up. n is up to 50 and the answer should be returned modulo 1 billion and 7.
A2) This seemed a tricky question, and inspection of round statistics showed I was not alone in finding it hard. The most important trick is to realise that if each card is consider as a link between the number on the front and the back, and each case of the same number is linked together, the full set of cards can be divided into cycles which each are independent of the others. If the cycle consists of a single card, it has no options, only possible locations in the final list. If it is longer, it both has a number of options which is dependent on the cycle length, and the number of ways that cycle can be interspersed into overall list. The answer becomes the product of the number of ways each cycle length can be chosen from n reduced by the length of cycles already considered times the number of ways a pattern can be made in the cycle itself.
The number of ways a pattern can be made in a cycle can be calculated a number of ways, dp is one option, although it seems a little tricky. An analytical approach is easier. Each number on the front of the cards which are in a cycle can either be present 1 2 or 0 times. Each 2 implies a 0, so it seems helpful to consider each case of the number of 2’s separately. The number of ways to select which numbers are available to use with k doubles is the tricky bit, once you have that can boost that to get the full answer by multiplying by the number of orderings, which is n!/2^k if there are k 2’s. While each 2 implies a 0, it doesn’t imply exactly where that 0 is, other than it is somewhere before the next 2… So we need to reserve 2k spots for the 2’s and 0’s and then we need to alternate 2’s and 0’s, which gives 2 options. So mathematically it is C(n, 2k)*2. However in the case of k=0 there is only 1 option, so we need to get rid of the multiplication by 2. Which gives C(n, 2k)*(k==0 ? 1 : 2).
And that’s all the components, all that remains is to sum things up and multiply it all out and perform a lot of modulo operations everywhere. (Pre-calculate the choose function using DP as usual.)
Q3) Consider a h x w rectangle of tiles where each tile is coloured with one of 4 colours. Determine the number of ways to make every tile a different colour from its (up to 8) neighbours, while only changing at most k tiles. Limits: h and w up to 50, k up to h*w.
A3) After problem 2, I’m surprised there was even 12 correct solutions to this one. First up there are a couple of special cases. If height or width is 1, simple dynamic programming provides the solution. In fact the rest of the approach used to solve the problem requires height and width greater than 2, so it we have to solve that first.
For height and width greater than 2 consider each possible set of 4 colours for the top left corner. Playing around with the possibilities which satisfy the different colour to neighbours requirement you discover that every second row is identical or every second column is identical, or both. So assume the rows are identical, each column after the first 2 has 2 choices for patterns. Then assume the columns are identical, each row after the first 2 has 2 choices for patterns. This gives us 2 DP (very similar, in fact you can do a diagonal flip of the input and use the same DP for each). In each DP you have number of ways to make the first n rows work (columns) using j changes. Then sum all values of j from 0 to k for the all h row case, and presto you have the number of ways for column (row) alternation for a given 2×2 top left starting point. Sum column and row together and … wait a second. As mentioned earlier there is a case where both rows and columns alternate. For a given 2×2 starting point, there is only one such case, but if it can be achieved in k changes or less, we’ve counted it twice. So check that quickly and subtract it off. Sum over all 2×2 starting points and presto you are done. Not an easy problem, but I almost wonder if it was actually easier than question 2.