As is typical for GCJ – qualifying round had a large turn out, ~22000 people made a successful submission, of those 17059 qualified (at the moment at least).
63 perfect scores – 2 of which were Australian, and I don’t recognize either handle. Radeye gets the unfortunate distinction of 64th place, having managed to solve all of the hardest problems, but having the large input on the trivial first question fail… (I have to wonder if he was trying the different language for small/large input thing, as his small input in perl looks fine at first glance… but it is perl, so yeah…)
Q1) Do some simple analysis of a board from a 4×4 equivalent of tic-tac-toe where there is a special piece which counts as both X and O. Determine winner/draw/incomplete.
A1) This problem was so trivial they had to point out not to make it harder on yourself by attempting to determine inevitable winner/draw. Small and large input, but the only difference was the number of test cases. (Importantly, solving this problem completely is not enough to advance to round 1.)
The problem also specifies that the board will be from a valid game, so you don’t have to handle cases where both X and O have won. Check each row/column/diagonal for either winner – return if found. Otherwise return draw if board is full, incomplete if not.
Q2) Given a rectangular array of ‘heights’ and a device which reduces all heights in a row, or column above an adjustable setting, determine whether the given heights could be obtained if everything started with equal height (which is greater than or equal to anything in the given heights). Adjustable setting can only be changed in between usages, not as it performs a row/column ‘trim’.
A2) The important thing to notice here is that for any given square, it doesn’t matter what order the device interacts with it, it only matters what the minimum setting was across all interactions. So if we can determine what height was used for each row/column – we can just run a simulation and check whether the input matches expectation.
For each row/column – the device cannot have been set any lower than the highest member of that row/column. And if it was set any higher, the usage definitely could have been ignored entirely. Therefore you can just determine the maximum value for each row/column – perform that simulation, and check result versus input. This runs in O(nm) time and additional space.
A slower alternative (which I thought of first – and have not verified is actually correct…) is for each cell, check to ensure that it is the highest value of either the row, or column (or both). If it is not the highest value of either the row or the column, it cannot possibly work. Trivial implementation here is O(nm*max(n,m)) – which would still be fast enough (and requires no additional space, if you cared for some reason). This can also be done in O(nm) by painting cells which are equal to max of row, or max of column in two passes over each row/column. If all cells are painted, you have succeeded. But the boolean for each cell has to be stored somewhere.
Q3) Determine the number of palindromic squares of palindromic numbers there are in the range A to B. Maximum value of B either 1000, 10^14 or 10^100 depending on problem tier.
A3) This is the first time there has been a problem with 2 large inputs, one harder than the other. This problem was correspondingly worth a very large number of points.
The small input is trivial. In fact you can do it in your head, since the number of palindromes less than sqrt(1000) is about 12, and of those only 5 are still palindromic when squared. So just search the set 1, 4, 9, 121, 484 against each given A, B pair to return a count. I wonder if go-hero.net has a category for the null programming language… There was only 100 test cases, if you type fast and pre filled the form a bit, it shouldn’t be too hard to do that in 4 minutes.
The first large input poses a bit more of a challenge. The first thing to realise is that these numbers are very rare, so we can solve all 10000 test cases by generating the list once and performing binary search to find indexes to take difference to get the count. Indeed we could even pre-calculate the list and hard code it in this case, there aren’t that many less than 10^14. An approach which works for this case is generating all palindromes less than 10^7, squaring each one and checking whether its a palindrome. We can even generate all palindromes less than 10^7 by brute force, checking every number to see if it is a palindrome – it should still run in time.
The second large input is where it gets tricky. The numbers are still rare enough that you can calculate them all before running any test and keep them all in memory, but generating them all becomes a bit more time consuming. First off, we can’t possibly brute force 10^50 numbers to find palindromes to square, so instead we build the palindromes by taking the 10^25 numbers and either reflecting after or through the last digit to create our palindromes. 2*10^25 however is still way way way too many. But if you look at the output of such a program for up to 10^8, you can get a pretty confident grasp on some ways to speed things up. The only case where a digit greater than 2 is used in a palindrome which when squared still gives a palindrome – is 3 itself, giving 9. So you can special case that and this means you are down to 2*3^25 cases. This is still too many, but it is a big improvement. A closer look will show that the digit 2 is only used in very rare circumstances. If it is the first digit, all other digits are zero, or the last digit is 1 and is reflected through rather than after. Otherwise it can be the last digit that is reflected through. The former gives 1.5 cases per power of 10, a tiny number. The other reduces us down to 3*2^25 cases. This is 100 million cases, each of which is worst case performing a 50 digit by 50 digit multiplication. This may take minutes even with a good BigInteger implementation – so advisable to test before hand to see if it will be fast enough, or even better – pre-compute and store/load it.
However, we can do better. A closer look shows that every palindrome which is still a palindrome when squared, the sum of the squares of its digits is at most 9. This is why 3 only appears once, and why 2 is so rare. But it does help us beyond that. Out of the 2^25 scenarios from creating patterns of 0s and 1s – we can skip everything which has more than 5 1s, or more specifically 4 1s in the reflected section and optionally a 1 in the middle. This gets us closer to 3*25^4 which is clearly going to run in time. But the complexity of walking permutations like this might be a little bit annoying…
Q4) There are a set of boxes, which each take a specific kind of key to open. They break the key in the process. Inside the boxes there may be more keys. You start with a set of keys and a description of all the boxes, return the canonical opening order to open them all, if possible at all.
A4) Small input wasn’t too bad here, 20 boxes. For a given subset of the boxes being open the number of keys you have left doesn’t depend on what order you opened them, so you can do a depth first search on the canonical order, ignoring any states you find twice. This is O(n*2^n) which for 20 is perfectly fine – especially with only 25 test cases to perform.
Large input however was 200 boxes. The previous algorithm is no longer any good. I spent some time thinking about this, but couldn’t come up with a convincing idea. My best thought was that maybe if you did a reverse depth first search, from the answer back to the start, it might be self-pruning to the point where your search space ends up being much smaller than 2^200.
Looking at other peoples code, it appears that the solution is that there exists a much faster method to determine whether it is still possible to get to the final state from any given state, compared to finding a solution. This method is then just applied iteratively every time you try to make a move in the depth first search on canonical order, and back track immediately if the ‘can still finish’ function returns false.
There appears to be two parts to this approach. One is that you first check that there are enough keys in the given situation to open every chest. So you just add up the contents of every chest with the starting scenario and ensure it is higher than the count of the number of chests for each key type. Somehow, having checked this then makes the following seemingly nonsensical ‘can still finish’ function valid. Create a directed graph connecting each key type of a chest not yet opened, to the key types contained in those unopened chests. Then for each key type you have (ignoring count) start traversing the graph using a simultaneous breadth first search. If you can reach every key type used by an unopened chest – the problem is still solvable.
I actually wonder if some of the solutions I am reading are actually correct, or whether the fact that there was only 25 test cases meant it was easy to fake a truly correct answer.