# 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

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++.

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.