So, the 25 hours are up, and at final count about 230 people submitted all the problems (including myself).\u00a0 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.<\/p>\n
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.<\/p>\n
Q1) Given an input string, perform letter substitution to generate another string. (Letter substitution is a bijection and some examples provided.)<\/strong><\/p>\n A1) So, wow… simplest question description ever?\u00a0 No large input, since well, what could they do?\u00a0 The small difficulty of this question was that the provided samples were missing 2 letters.\u00a0 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.\u00a0 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.\u00a0 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.<\/p>\n Best part of this problem?\u00a0 The answers.\u00a0 I have to wonder how many people submit their outputs without actually checking them.\u00a0 Because if you did, then you missed out!\u00a0 After decoding many of the answers were amusing or interestingly absurd.<\/p>\n 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.\u00a0 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.<\/strong><\/p>\n A2) The small input limit was that there was at most 3 numbers.\u00a0 This meant that you could brute force every allocation of the difference of 2 and just return whatever was the best answer.\u00a0 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…<\/p>\n 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. \u00a0 If the sum is 0 modulo 3, they are all the first, otherwise there is one of one kind and two of the other.\u00a0 So we can go through the list determining the triplet for difference limit of 1.\u00a0 If the resultant triplet already has a highest value equal to k or higher, then add it to the result.\u00a0 Otherwise, if the highest is equal to k-1, then maybe we can use a difference of 2 to reach the limit.<\/p>\n Specifically the sum must be at least 2 (as each integer is non-negative) and the modulo must not be 1.\u00a0 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.\u00a0 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.\u00a0 Add the result to the total and you are done.<\/p>\n 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.\u00a0 A and B are also guaranteed to have the same number of digits and A is less than or equal to B.<\/strong><\/p>\n A3)\u00a0 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.\u00a0 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.<\/p>\n 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.\u00a0 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.<\/p>\n 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.)\u00a0 To generate a rotation simply store the mod 10, then divide by 10 and add the modulo times 10^length.\u00a0 Repeatedly execute until you are back at the same number you started with.\u00a0 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.<\/p>\n 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.\u00a0 The outer edge of the grid is guaranteed to all be set.\u00a0 Light bounces mostly as you would expect, but there are two specific cases of interest.\u00a0 Firstly, if light exactly hits an inner corner, where 3 wall cells meet, the light completely reverses direction.\u00a0 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.\u00a0 Light can glance a corner just fine, even two diagonally touching corners, it just passes straight on.\u00a0 Grid size is at most 30×30 and D is at most 50.<\/strong><\/p>\n A4) So, here it is.\u00a0 The question to see if you have some spare time (or are really really good…).\u00a0 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.\u00a0 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.\u00a0 (Looking back, at least 1 sample from each question with a large input violated the small input conditions.\u00a0 I’m not sure if this is new this year, but it is actually kind of good…)\u00a0 This restriction is actually quite powerful and would allow for a much simpler solution as I will explain in a minute.<\/p>\n So, how do we determine the solution?\u00a0 Even a simple case like the 3rd sample which is a 2×1 open space with a maximum distance of 8 has 68 reflections.\u00a0 One thing to think about is where the light starts and ends up.\u00a0 It is in the middle of a cell on both occasions.\u00a0 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.\u00a0 A mirrored puzzle with a mirrored starting position.\u00a0 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.\u00a0 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.\u00a0 A simple implementation just considers every cell in the +\/-D square.<\/p>\n Now we have to follow the light.\u00a0 This is where the small input becomes much easier.\u00a0 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.\u00a0 Then simply count how many starting points are within distance D of the original starting point.\u00a0 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.\u00a0 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.<\/p>\n Oh, except that doesn’t quite work.\u00a0 This approach counts the same angle multiple times.\u00a0 Think of the 1×1 room with a maximum D of 4.\u00a0 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.\u00a0 The solution to this is to instead count the distinct angles.\u00a0 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).<\/p>\n Now the large input, that is a whole different scenario…\u00a0 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.\u00a0 So, we really need to actually simulate the light path.\u00a0 At this point I grew concerned at how much work was involved in writing the solution.\u00a0 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.\u00a0 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.<\/p>\n But I wanted to solve this problem, so I dived in.\u00a0 First up, I realised that the cardinal directions needed to be handled separately.\u00a0 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.\u00a0 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.<\/p>\n So all we have to do now is simulate the non-90 degree angles.\u00a0 First problem to consider is the accuracy problem.\u00a0 My solution to this was to use the fraction class from TMD.Algo.\u00a0 By doing this I ensured perfect accuracy, so long as the numerator and denominator never overflowed.\u00a0 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.\u00a0 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.\u00a0 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.\u00a0 Since D is at most 50, thats about 25million.\u00a0 Numerators shouldn’t get above D +2 times the denominator so long as we abort the simulation sooner rather than later.\u00a0 So numerator should cap out around 1.3billion, easily handled by the 64bit numbers my Fraction class uses internally.<\/p>\n Next problem… This one is kind of subtle, but even with fractions how do we ensure our distance check is perfect?\u00a0 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.\u00a0 The solution comes from remembering that we can pretend the light goes in a straight line with the world reflecting about as needed.\u00a0 The length of this line is defined by two numbers, the cumulative absolute dx and dy.\u00a0 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.\u00a0 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).<\/p>\n So, all that remains is to perform the simulation.\u00a0 Given a point and a direction, we need to determine the next possible half integer coordinate.\u00a0 First step is to determine the half-integer coordinate.\u00a0 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.\u00a0 Now we have 2 possible coordinates to move to next, one for x and one for y.\u00a0 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.\u00a0 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.\u00a0 Whichever it is, that is the new current location.\u00a0 Update the accumulators at this point.\u00a0 Once the accumulators are updated, verify that we haven’t travelled too far, fail if we are in excess of D.\u00a0 Now check if we’re back where we started.\u00a0 If yes, return success.\u00a0 Finally check if we are at an integral boundary, is denominator 1 for either x or y coordinates.\u00a0 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…)\u00a0 If yes for both x and y coordinates, we’ve hit a corner.\u00a0 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.\u00a0 We need to look at the other 2 cells adjacent to the corner.\u00a0 If 1 of these is filled, we’ve got a normal wall and reflect (making sure you reflect the right way… Fiddly!).\u00a0 If both are filled, double reflect.\u00a0 If neither are filled return fail for this angle.<\/p>\n 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…)\u00a0 When I ran the small input I ran it in debug mode with the debugger attached.\u00a0 It took 2 minutes, which given the 4 minute time frame for submission was kind of nerve racking.\u00a0 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.\u00a0 But to be sure I changed to run in release mode.\u00a0 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.\u00a0 But that left plenty of time…\u00a0 Still, considering how many corner cases there were I was sceptical that it would pass tests.\u00a0 But it did, so I am happy.<\/p>\n","protected":false},"excerpt":{"rendered":" So, the 25 hours are up, and at final count about 230 people submitted all the problems (including myself).\u00a0 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 … Continue reading GCJ 12 Qualifying Round<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-510","post","type-post","status-publish","format-standard","hentry","category-code-competitions"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/510","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=510"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/510\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=510"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=510"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=510"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}