As previously mentioned I didn’t have to get up at 4am to do this round, but a quick look at the final scoreboard it appears the questions were significantly easier. Almost half of the advancers solved the 1000pt question correctly. The 600th place cut-off required solving the 250pt problem in decent time and a successful challenge as well.
In this competitive environment only 1 Australian advanced, 2 more falling just below the cut-off having solved the 250pt quickly.
Q1) Given an even number of integers, the need to be made into pairs. These pairs can have each member added together to create a value of that pair. Determine the minimum difference between the lowest and highest values in such a set of pairs. Between 2 and 50 starting integers and numbers are all in the range 1 to 1000.
A1) Without justification – the simple approach is to sort the inputs and pair them from outside to inside. Then just return the difference between the largest and smallest pairs created this way. This is also correct, but proving it appears not so trivial. (Certainly in the competition this would have put me at risk, not being able to prove it usually delays my submission.)
Q2) Given a rectangular array which is partially populated, and the ability to clear up to R consecutive rows at a time or C consecutive columns at a time, determine the minimum number of ‘clears’ required to clear the array completely. Rectangular array is maximum 15×15.
A2) So the first key point to this problem is that the maximum size is 15. This means a brute force on every subset of rows, or columns (but not both) is plausible. The next key point is that the order in which you perform your clears does not matter, if 2 clears overlap the common cells will be cleared regardless of order. So you can do all your row clears before your cell clears, without loss of generality.
This leads to a fairly simple approach – try every subset of rows (including empty) and then use a greedy clearing to determine the minimum number of moves by columns to clear what remains, and also to determine the minimum number of moves to implement the original subset of rows selected. (Don’t worry if your greedy approach clears excess to the selected subset, taking the minimum number of moves is more important. The actual subset that you erase is a better solution anyway.)
Simple runtime is O(2^(Min(w,h)) * w*h) – each subset requires 2 greedy clearing passes, which cost proportional to the size of the full array in the worst case. This runtime chooses the smallest dimension, but in practice the code is simpler if you just standardise on rows or columns, it will run fast enough regardless. An ideal solution might be to implement it faster by using a sparse array representation much like the one used in the Dancing Links algorithm. But that certainly wasn’t required here.
Q3) Given a dictionary of distinct words and the following rules, determine the minimum number of remaining words you can end up with. There are 2 rules. First rule is that if any time you get the same word duplicated, the duplicate and the word are removed. Second rule is that you can replace any word with the same word with an even length prefix reversed.
A3) The key point for this problem is that the even length prefix reversal lets you create almost any anagram out of an even length word. For odd length words you get almost any anagram where the last character hasn’t moved. Secondly it doesn’t matter what order you remove pairs that match along the way, because there are no dead ends in the reordering and if a can be made to match with b and c, b and c can be made to match.
Almost any anagram isn’t every anagram. Specifically it is any anagram of the original pairs, where each letter in a pair itself can be in any order. The pairs never get split up in the process, so you can’t reorder 1234 into 1324. We can create a canonical form for matchable groups in this subset of anagrams by sorting each pair of letters, then sorting the resultant pairs. For example the word ‘word’ would first be rearranged to ‘owdr’ then secondly to ‘drow’ to given the canonical order. (FIFO is its own canonical ordering under these rules…)
So for each word, if it is even length, replace it with the word with its characters in canonical order. If it is odd length, do the same but leave the last character in place. Then do a unique count of the result words. If the count for a unique word is even, all pairs can be removed, if the unique count is odd, you have to keep 1 copy of that word. So simply count those odd ones up and you have your answer.
This was pretty easy for a 1000pt problem (certainly it seems easier than the 500pt problem) – but identifying the way to canonicalise the available subset of anagrams isn’t totally trivial, so it might stump a few people.