Round 2 Recap
Round 2 Recap
Statistics
74 competitors in total
- The first task was attempted by 51 (68%) of the competitors, 35 (70%) of which were correct solutions
- The second task was attempted by 41 (55%) of the competitors, 37 (91%) of which were correct solutions
- The third task was attempted by 28 (37%) of the competitors, 13 (47%) of which were correct solutions
- The fourth task was attempted by 6 (8%) of the competitors, only 3 (54%) of which were correct solutions
- The fifth task was attempted by 4 (5%) of the competitors, only 0 (0%) of which were correct solutions
Full problem editorial
The full problem editorial with a detailed explanation of all the tasks can be found here.
Technical insights
Task 1: Self-replicating Nanobots:
As usual, the first task was an easy one that only requires basic programming knowledge to implement. Since the constraints of the problem were relatively low, a simple simulation of the string transformations would pass the constraints and yield a correct solution.
Example solution by iletavcioski in C++.
Task 2: Learning Chess:
The second problem is again a simple one that requires simulating the movement of a knight in a chess game. Obvious edge cases include not moving out of the chessboard as well as not moving to a position that has a piece of the same color as the knight we are controlling. Apart from proper string parsing, having an easier time solving this problem also includes using movement arrays to automate the movement of the knight instead of chaining conditionals for every move.
Example solution by fdespotovski in Java.
Task 3: Endless Run - The Sequel:
This problem is a more difficult version to the 200 problem of the previous round. Since brute forcing is no option (there are way too many calculations that need to take place), we may notice that in the mapping the only relevant values are the first and third ones and the result will always be an XOR of these two. At this point, we can either use clever bit shifting to perform all of the operations while avoiding to go through each row individually. This is the slower suggested solution that is fast enough to pass the time constraints.
A more clever solution involves noticing that the elementary cellular automaton that describes the task is a Rule 90 one, more commonly known as the Sierpinski Automaton. This automaton generates the Sierpinski Triangle when iterated through, which in turn has a property which states that the number of "active" cells in the nth row of the triangle equals 2 to the power of the number of 1s in the binary representation of n. This solution is both very short to code up and has a time complexity of O(1).
Example solution by Mtrajk in Java.
Task 4: The Maintenance Team:
The fourth problem in this round was once again a complicated maze traversal one. Although conceptually similar, there are multiple things we need to take into account that involve fitting the states into two separate bitmasks (since the number of covers/holes is no greater than 8 this would fit our constraints) which are related to each other (you cannot cover a hole if there is no 1 at the given position in the cover bitmask). Additionally we have to make sure we check the number of 1s we have in the cover bitmask as we are not allowed to carry more than 3 covers at a time. Other than that, this is just another simple BFS type problem with multiple states.
Example solution by despotovski01 in Java.
Task 5: Beautiful Numbers:
The fifth task was a relatively easy mathematical problem. The tricky part was to cover all edge cases. For each beautiful number the following must be true:
- The last digit has to be 0 (in order to be divisible by 5 and 2).
- The sum of all digits has to be divisible by three (in order to be divisible by 3).
- The last two digits can be {00,40, 80} preceded by an even digit, or {20, 60} preceded with an odd digit (in order to be divisible by 8).
The next step is for each possible ending to choose the rest of the digits in such way that the sum of all digits is divisible by 3. So, if the sum of all digits % 3 is 1, either the smallest digit d such that d % 3 is 1 or the two smallest digits whose modulo 3 is 2 should be removed. Correspondingly, if the sum of all digit % 3 is 2, either the smallest digit d such that d % 3 = 2, or the two smallest digits whose modulo 3 is 1 should be removed. Because the beautiful number must be maximized, the remaining digits are simply taken in a decreasing order. The previously described algorithm finds the maximal beautiful number given the ending (the last three digits). So the last step is to choose the ending that leads to the largest beautiful number. One final thing to consider is the fact that if 0 is not in the digits a beautiful number cannot be formed.
