So, the 25 hours are up, and at final count about 230 people submitted all the problems (including myself). After the elimination of incorrect ‘large input’ solutions I managed to remain part of the 163 people who got a perfect score in this round.
Over 18000 people got a positive score, so I imagine that the number of competitors was pretty high. 15692 people qualified, so lots of competitors for R1A.
Q1) Given an input string, perform letter substitution to generate another string. (Letter substitution is a bijection and some examples provided.)
A1) So, wow… simplest question description ever? No large input, since well, what could they do? The small difficulty of this question was that the provided samples were missing 2 letters. The first of these letters was provided in the question text, but it was provided as a forward mapping and the actual question asked for a reverse mapping. The final letter can be deduced by the fact that the substitution is a bijection, and hence if you know all but one path, the final path is between the only unused input and output. So, you could have copied the samples into your code and written some moderately smart code to work out the substitution for you … or you could just do what I did and work it out by hand and hard code the mapping, using indexes into a handcrafted string.
Best part of this problem? The answers. I have to wonder how many people submit their outputs without actually checking them. Because if you did, then you missed out! After decoding many of the answers were amusing or interestingly absurd.
Q2) Given a set of numbers which are known to each be the sum of 3 non-negative integers, determine how many of these triplets can have a largest number of at least k. The triplets are further limited that difference between the lowest and highest values of the triplet is at most 2 for ‘n’ of them, and at most 1 for the rest.
A2) The small input limit was that there was at most 3 numbers. This meant that you could brute force every allocation of the difference of 2 and just return whatever was the best answer. The large input was not feasible using this approach, but I doubt that there were many people who would have used the brute force approach anyway…
So, if we look at each triplet, if the difference limit is 1, then the triplet consists only of Floor(sum/3) or Floor(sum/3) + 1. If the sum is 0 modulo 3, they are all the first, otherwise there is one of one kind and two of the other. So we can go through the list determining the triplet for difference limit of 1. If the resultant triplet already has a highest value equal to k or higher, then add it to the result. Otherwise, if the highest is equal to k-1, then maybe we can use a difference of 2 to reach the limit.
Specifically the sum must be at least 2 (as each integer is non-negative) and the modulo must not be 1. If the modulo is 1 then changing to a difference of 2, doesn’t actually increase the highest value, it just increase the number of numbers at the highest value. Accumulate all the cases where switching to 2 would make a difference, then limit it by n, since only at most n of these can be used. Add the result to the total and you are done.
Q3) Determine the number of pairs of numbers n and m where n is less than m, n is greater than or equal to A and m is less than or equal to B, such that n and m have the same number of digits and are rotations of each other. A and B are also guaranteed to have the same number of digits and A is less than or equal to B.
A3) Small input limits B to be at most 1000, which in practice means 3 digits since if B has 4 digits, so does A and hence A equals B and there are no pairs. Large input limits B to be at most 2million, which gives us some cases with 6 digits and a maximum range of 1million numbers to check.
It might seem that the large input will need some fancy tricks to deal with how large it is, but, that is not really the case, brute force approach will run in time unless the implementation is particularly slow. For each number in the range A to B, generate all rotations, if the rotation is greater than the starting number and less than or equal to B, add one to your total.
Generating rotations is not hard, first count the number of digits in A, by dividing by 10 until the answer is 0. (A is guaranteed not to be 0, so you don’t have to worry about that corner case.) To generate a rotation simply store the mod 10, then divide by 10 and add the modulo times 10^length. Repeatedly execute until you are back at the same number you started with. The fact that many rotations may end up starting with 0 is not relevant, since you are going to compare the value against the original number which does not start with 0, and hence all of these will be skipped.
Q4) Given a rectangular grid of square cells where cells are either part of a wall or not, and all edges of a wall are mirrored and you are a 0 size object at the centre of a specific cell which is not a wall, determine how many reflections of yourself can be seen where the light travels at most a distance D and can’t pass through yourself. The outer edge of the grid is guaranteed to all be set. Light bounces mostly as you would expect, but there are two specific cases of interest. Firstly, if light exactly hits an inner corner, where 3 wall cells meet, the light completely reverses direction. Finally if the light hits an outer corner with the light heading towards the 1 filled cell adjacent to that intersection, the light is destroyed. Light can glance a corner just fine, even two diagonally touching corners, it just passes straight on. Grid size is at most 30×30 and D is at most 50.
A4) So, here it is. The question to see if you have some spare time (or are really really good…). The small input had a strange limitation which was that the number of walls would be at most double the width plus double height, minus 4. It took me a while to realise that this meant that only the edges would be filled in, since half the samples violated this condition. (Looking back, at least 1 sample from each question with a large input violated the small input conditions. I’m not sure if this is new this year, but it is actually kind of good…) This restriction is actually quite powerful and would allow for a much simpler solution as I will explain in a minute.
So, how do we determine the solution? Even a simple case like the 3rd sample which is a 2×1 open space with a maximum distance of 8 has 68 reflections. One thing to think about is where the light starts and ends up. It is in the middle of a cell on both occasions. If you think about what happens each time the light reflects off an edge, its like the light keeps travelling but into a mirrored version of the puzzle about that edge. A mirrored puzzle with a mirrored starting position. This mirroring is always aligned at cell edges, so the resultant grid remains aligned with the starting grid and hence in order for the light to travel from start to start through multiple reflections, the initial angle must be one which passes through the centre of two cells in the infinite grid plane. That is an infinite number of scenarios to check, but lucky for us we have a maximum distance D, so we can easily limit this to angles which connect the centre of two cells at most a distance D from the starting position. A simple implementation just considers every cell in the +/-D square.
Now we have to follow the light. This is where the small input becomes much easier. Because it is a simple rectangular room, you can expand it out to cover the entire +/-D square through reflection, populating each square with either nothing or a reflected position of the original starting point. Then simply count how many starting points are within distance D of the original starting point. The double reflection in an inner corner thing plays along nicely with this, and the outer corner light destroy never happens in a simple rectangular room. You don’t even have to actually create the large grid, you can use some tricky divs and modulo to map each potential square straight back to the input data.
Oh, except that doesn’t quite work. This approach counts the same angle multiple times. Think of the 1×1 room with a maximum D of 4. The reflected grid contains a starting point in every cell, but obviously walking a multiple of 45 degree angles passes through an intermediary reflected starting point before it reaches the outermost one, which is disallowed. The solution to this is to instead count the distinct angles. Use a lookup table to check whether you’ve already counted an angle, where the lookup reduces the dx and dy by their gcd (or reduces them to 1 if the other is 0).
Now the large input, that is a whole different scenario… If we try to reflect through each wall and overlay the maps, we get inconsistencies depending on order of reflection, and the outer corner light destroy is a pain. So, we really need to actually simulate the light path. At this point I grew concerned at how much work was involved in writing the solution. I once a very long time a go wrote a wolfenstein engine clone, which involves a technique called raycasting, specifically raycasting onto a square grid. I remembered that being kind of painful to get right, and here we are not just doing raycasting, but having to recast the rays at each reflection – and finally we need to be absolutely perfect in calculating distance or we’ll fail test cases involving angles based off of 3/4/5 triangles.
But I wanted to solve this problem, so I dived in. First up, I realised that the cardinal directions needed to be handled separately. Back when I was implementing my wolfenstein engine clone, I had hacks in place to ensure pure 90 degree angles never actually occurred as you got divide by 0 bugs, this time said hacks would cause the question to fail. Luckily these 90 degree angles are quite easy, just walk cells in the specific direction until you find a wall, determine the number of in between cells, double it, and add 1 (for the 2 halves exiting and entering the first cell) and check if that is too far or not.
So all we have to do now is simulate the non-90 degree angles. First problem to consider is the accuracy problem. My solution to this was to use the fraction class from TMD.Algo. By doing this I ensured perfect accuracy, so long as the numerator and denominator never overflowed. There would be a lot of calculations, but the fraction class repeatedly reduces to minimal form after each operation, so it really depended on what kind of fractions could be found. We were going to be looking at the positions of intersections with grid lines (for walls) and half grid lines (for the starting location), and a slope of dx/dy. Some handwaving and I convinced myself that the fractions would never have a denominator greater than 2*dx*dy after reduction, and square that for pre-reduction. Since D is at most 50, thats about 25million. Numerators shouldn’t get above D +2 times the denominator so long as we abort the simulation sooner rather than later. So numerator should cap out around 1.3billion, easily handled by the 64bit numbers my Fraction class uses internally.
Next problem… This one is kind of subtle, but even with fractions how do we ensure our distance check is perfect? If we calculate the distance to each reflection and sum these, we have to calculate the square root of a fraction, which is not actually very likely to be another fraction, so we’ll be adding together doubles and we’ll lose our perfect accuracy. The solution comes from remembering that we can pretend the light goes in a straight line with the world reflecting about as needed. The length of this line is defined by two numbers, the cumulative absolute dx and dy. After each simulation step we can add how far we’ve moved dx and dy to an accumulator for each, taking the absolute value so it continues to accumulate after each reflection. We can then compare the sum of squares of these accumulators with D^2, an exact comparison (this comparison might actually have triggered the need for 64bit integers in the fraction type now that I think about it).
So, all that remains is to perform the simulation. Given a point and a direction, we need to determine the next possible half integer coordinate. First step is to determine the half-integer coordinate. If we aren’t already on a half-integer (check denominator 1 or 2) then calculate the floor of double the value, and add 1 if we are moving in the positive direction then halve. If we are on a half-integer, we simply add or subtract half depending on whether direction of motion is positive in that dimension. Now we have 2 possible coordinates to move to next, one for x and one for y. We calculate the delta between current and new location for the coordinate calculated then multiply by dx/dy or dy/dx to calculate the movement in the other coordinate. Add this to the current position of that other coordinate and we have the ‘projected’ coordinates. Compare the projected x coordinate for the next y to the next x, and determine which is closer in the direction of motion. Whichever it is, that is the new current location. Update the accumulators at this point. Once the accumulators are updated, verify that we haven’t travelled too far, fail if we are in excess of D. Now check if we’re back where we started. If yes, return success. Finally check if we are at an integral boundary, is denominator 1 for either x or y coordinates. If yes for only 1 of x or y, check to see if we’ve hit a wall by calculating the floor of the coordinates and subtracting 1 from one of those coordinates if we’re heading into a wall in the negative direction. (Fiddly…) If yes for both x and y coordinates, we’ve hit a corner. If the far side of the corner is occupied (similar algorithm to before, but we might have to subtract 1 from both x and y – extra fidly) then we need to work out what happened. We need to look at the other 2 cells adjacent to the corner. If 1 of these is filled, we’ve got a normal wall and reflect (making sure you reflect the right way… Fiddly!). If both are filled, double reflect. If neither are filled return fail for this angle.
Stick the above complicated fiddly code in a loop and presto you are done… (No, I didn’t get it right first time, but it did at least fail on the samples, so I didn’t have to find out by running the small input…) When I ran the small input I ran it in debug mode with the debugger attached. It took 2 minutes, which given the 4 minute time frame for submission was kind of nerve racking. I thought about the large input for a bit and decided it couldn’t be much slower, since I was simulating every half integral coordinate intersection regardless, and whether it reflected or not was a negligible contribution to the processing time, so given that there was 8 minutes for that, I should have been fine. But to be sure I changed to run in release mode. I think the problems for the large input were actually a bit larger D on average, so even in release mode it still took 2 minutes. But that left plenty of time… Still, considering how many corner cases there were I was sceptical that it would pass tests. But it did, so I am happy.