A quick look at how people performed in this round shows it to be a very tricky round. No perfect scores this round, but with only 25 people advancing to the finals, unless you solved question 4 large (which was worth 31 points and only had 1 person solve it correctly), you needed everything else and a decent time to advance. Representing Australia, tikitikirevenge came close in 48th place.
Q1) Given an irregular shape defined by two poly-lines with identical start and end x coordinates, and continuously increasing x coordinates in between (but each poly line itself may have a different number of points) and these poly lines do not intersect. Determine G – 1 x coordinate positions where cuts with dx=0 (vertical) divide the shape into G equal parts.
A1) First thing to do is to break the shape into trapeziums, at each x coordinate specified in the 2 poly lines, taking care for the case where the x-coordinates are identical, and otherwise having to determine the y coordinate for the other side using interpolation. Area of a each trapezium is easy, so we can then work out the total area, and the G equal sub divisions of that total area. Iteration easily finds which trapezium contains each division point, all that is left is determining where in the trapezium the appropriate point is. This could be done using a binary search, or simply derive the equation (which will be quadratic) and solve for the position given the target area (second solution will be outside the trapezium).
All in all, this question is fiddly but very doable. Not surprisingly then this was the question with the highest success rate.
Q2) Given a set of N numbers each between 1 and 10000 inclusive, with possible repetition, you want to organize them into sets of consecutive integers such that the smallest such set is maximal. What is the size of that maximal smallest set?
A2) Small input size is 10, and so a brute force approach is plausible there. Large input is up to 1000, which is much less friendly.
Firstly I think it is useful to break the problem down. If you sort the numbers, you can then break the problem into sections based on where there is a gap in the sorted sequence. The answer is then the minimum of the answer for each section.
Now all we need is the answer to a given section. Where ‘all’ is pretty much the entire problem. Obvious cases first. Same number of repetitions for every value; answer equals set size. If the repetition of a single value is greater than the sum of the repetitions of its neighbours, the answer is 1. In any case that we get an answer of 1, we can avoid looking at all other sections.
That still leaves a fair bit to consider. Anywhere that the repetition count increases has to be the start of at least a number of sequences equal to the difference. I am wondering if the greedy approach of starting no more sequences than required, and when the count decreases, stopping the oldest sequences, will produce the ideal answer. It certainly seems sound on the first glance. A quick check of the answers shows this to be the solution.
Definitely a lot more thinking than the first problem, but again doable.
Q3) There is an RxC grid where each square contains a conveyor belt which points either vertically, horizontally, or one of the 2 diagonals. Each conveyor belt has an individual direction control. Determine how many out of the 2^(R*C) possible scenarios result in the conveyor belts pointing only in loops. (I.E. No cell can have 2 cells pointing to it.) The grid wraps around on to itself ‘by the miracle of science’. Answer modulo 1000003 to avoid huge answer problems.
A3) Small input RxC is up to 4×4, so only 2^16 scenarios to investigate, and each scenario can be checked relatively quickly, simply by counting how many cells point to each cell. So, small input is trivial (and it receives a tiny number of points too). Large input is 100×100 – hence why we need that modulo.
Special cases – a cell might have nothing that can possibly point to it, causes a result of 0. Also a cell might have only one thing pointing too it, hence the direction of that conveyor is ‘defined’. A straight line loop of conveyors has 4 possibilities if length even, 2 if length odd. Any such loops can be removed from the graph as a multiple of the answer obtained otherwise. Otherwise the puzzle contains no reversible loops. Which is a bit of a pain really, because it means decomposition appears infeasible.
At this point I’m pretty sure I’m out of my league, so I shall consult the answers. Interesting! Having repeatedly forced conveyors where a cell has only one option pointing to it, and exiting if there is ever no options for a cell, an interesting thing occurs. Every remaining partially (or complete) undecided cell has either exactly 2 options for how conveyors point to it, or away from it (or both), due to conservation of edges. This implies that choosing one direction, always results in forcing a direction, which in-turn forces another until you come round in a loop, and since you come round in loops, the problem is decomposable after all. Each of these ‘loops of force’ is entirely independent and contributes exactly 2 independent ways to solve the problem. So count the loops, and keep doubling modulo 1000003 to get the answer.
In competition I doubt I would have gotten this out. The fact that the ‘loops of force’ aren’t constructed of consecutive cells makes it hard to observe by accident.
Q4) Given a binary representation of a square number, where some of the bits have been replaced with question marks (but not the highest set bit), determine the original number. (Only one answer will be possible.)
A4) Small input constraints of maximum 60 digits and at most 20 question marks made brute force an obvious and trivial course of action. This was actually answered more frequently than the easy answer to question 3.
The large input only had one person successfully solve it it, so I don’t feel too bad that nothing springs to mind. Constraints were 125 digits and up to 40 question marks. My first thoughts are, maybe fill in the highest 20 question marks with each possibility, and then get the bounds of the 64bit integer which matches the lower 20 question marks, and then try each one. Problem is, in the worst case scenario, that appears to be even worse than brute forcing all 2^40 scenarios.
A few little trivial cases to get started. If the right most digit is 0, it and the digit to its left can be removed and ’00’ appended back onto the answer afterwards. If the second right most digit is a 1, something is wrong because all squares either end in 01 or 00. If second right most digit is a question mark, it must be a 0. This leaves last 2 digits are ’01’ or ‘0?’.
The winning approach was to divide the number into half, if most of the question marks are in the top half, try each possibility for the bottom half, and use that to infer the top half (somehow). Otherwise try each possibility for the top half, and use that to determine the bottom half.
Lets look at the second option first, since it is easiest. If we calculate the square root of the maximum value which matches the specific pattern for the top half, round down and then square – we have our answer (assuming that it matches the pattern.) Only trick is to acquire the square root of a 125bit number. Binary search using BigInteger will do the trick.
This leaves the first option. Lets put aside the possibility of the answer being even. Above it was mentioned that the last 2 digits we actually work with are 01 or 0?, we can use this as justification for ignoring the possibility of the answer being even, because 0? can be broken into 00 or 01 sub cases, 00 causes recursion, 01 does not. (Since only one side of the question mark ever causes recursion, there is no exponential run time problem to worry about. Another important point is to only consider whether the low or high bits have the most question marks after ensuring the last 2 digits are 01, otherwise the algorithm can be easily tricked into running too slow.)
So, since the answer is odd, it ends in 01, but how does this help us? Well if the answer is odd, then the square root is odd, so it either ends in 01 or 11. IE it is 4A+1 or 4A+3. If it is the former than the square is 16A^2+ 8A + 1 = 8A+1 mod 16, if our input is a specific mod 16, we can determine whether A is odd or even, which gives us one more digit of the square root. Similar applies to 4A+3. In both cases, this continues. Given the right half digits of the original number, we can slowly build 2 possibilities for the same number of digits of the square root, which either ends in 01 or 11. Since the number of digits in the square root is no more than half the number of digits in the input and we’ve filled in all question marks in the right hand half we have 2 complete possibilities for the square root. Given these two possibilities we can then check which either actually matches the input.
Thinking about this problem, in hindsight I believe I’ve previously been shown this approach of determining the square root of a number given only its right hand half, but I doubt it would have helped me in the heat of competition, not even if it was the only problem I did.
Final analysis – the small inputs are generally all pretty easy to implement, the first 2 large inputs were in my doable category, this leaves my ‘feasible ideal placement’ between 160th and 90th – which matches with where I get eliminated in my best days. Would have been nice not to screw up round 2 so badly 🙂