The problems in this round were just a tiny bit easier and it showed – qualifying required 2 whole problems, or a good time on 1 whole and 2 smalls.
Q1) Given a rectangular array where some tiles are marked with a hash, replace it with a new array where the same tiles which were marked with a hash are marked with 2×2 arrangements of ‘\’ and ‘/’ which look like diamonds. This may not be possible, if not then return as much.
A1) Pretty straight forward question, the key is to identify that if a hash mark has nothing to its left or above, it has to be the top left corner of a 2×2. So replace the whole 2×2 immediately. If this overlaps with the edge of the array, or any of the 2×2 aren’t marked, fail immediately. Once done, repeat until complete or fail. A simple left to right, top to bottom walk solves the problem quickly and efficiently enough.
Q2) Given a sequence of stars, and a distance between each you want to travel from the first star, to the final star in as short of time as possible while stopping at every star in the exact order given. To slightly complicate things your engineers can build up to L speed boosters on stars. These speed boosters take a time t to be built, but once built all travel between the star it was built on, and the next star in the chain is performed at double speed. This even applies if the space craft is between those stars when the building completes.
A2) With the large input claiming up to 1million stars, this problem looks a bit scary at first. However a quick think and you should realize that a greedy algorithm applies.
The answer is (sum of the distances)/speed – (sum of speed boost benefits). Since the first part is a constant, and the second part has a constant number of components – the minimal time comes from maximising each component in the sum of speed boost benefits.
So, simply calculate the speed boost benefit for each star, if a speed boost was built there, and then sort the array descending (no problem for 1 million entries using merge sort), and sum the first L elements.
Only things to watch out for are using 64bit integers and ensuring that your speed boost benefit formula correctly uses t and covers all 3 scenarios – ‘useless’, ‘full benefit’, ‘space craft in mid-flight when building completes’.
Q3) Given a list of N integers, determine the smallest integer in the range L to H which either divides or is a multiple of each integer in the list, if such an integer exists.
A3) I solved this one on my own for a change, but the implementation for the large input is a bit hairy – so high risk I would have failed during competition. The small input constraints allowed a trivial brute force so many people submitted that on its own.
The key is to sort the integers, then the answer is either smaller than the smallest, or larger than the largest, or part of one of the segments now described by each consecutive pair.
Lets treat each case separately for now. Less than the smallest, determine the GCD of all numbers, and find the smallest divisor of that GCD which is in the range L-H. If L>GCD – nothing, otherwise can generate all divisor pairs by walking the integers 1 to Sqrt(GCD). Larger than the largest, determine the LCM of all numbers, and if less than L use a quick division to determine the first multiple of the LCM which is in the L-H range. If greater than H, obviously no answer.
This leaves the gaps. Based on these two cases above it should become apparent what is required. Determine the LCM of the first numbers, and the GCD of the rest. Then the answer is a multiple of the LCM which also divides the GCD. Obviously this won’t work if the LCM doesn’t divide the GCD, so that is a quick check. Next L<->H must overlap with the LCM<->GCD range or there is no point trying. If LCM is in the L<->H range, obviously we are done. Otherwise we walk the integers 1 to Sqrt(GCD) again, checking to see if any divisor pairs contain a multiple of the LCM in the L-H range. Choosing the smallest if there are multiple options.
So putting it all together, generate the LCMs starting from the left, and the GCDs starting from the right, try the less than smallest, then walk each consecutive pair of the sorted order, and finally the greater then largest and if at any time a solution is found in any of these parts, return it.
So I mentioned that the large input was a bit hairy and this is because of the LCM calculations involving numbers which are up to 10^16. Using BigInteger saves you from overflow risk, but unless you realize that there is no need to continue calculating LCMs once they exceed 10^16 (since they are greater than the maximum H value) you run the risk of performance being a problem as BigInteger becomes slower as the size of the data increases. Using a 64bit integer is okay, but you need to hand code or otherwise check for overflow in multiplication, and you need to apply the GCD division before the multiplication!
Performance wise the biggest cost is the walk from 1 to Sqrt(GCD) as this can be up to 10^8 modulo operations. Luckily this can only happen for at most 1 segment, but in case 100million modulo operations is too scary, an improvement to the average case is to divide the L<->H range and the GCD by the LCM. With the L<->H range round inwards, the GCD will divide cleanly. Then you can start with ceil(L/GCD), walking up wards to Sqrt(GCD/LCM), then jump back to just below ceil(L/GCD) and walk down to the first divisor for which the other side of the pair exceeds H/LCM. This doesn’t improve the worst case, but does give you early out and reduced calculation space in the average case.