Round 1 Recap
Round 1 Recap
Statistics
109 competitors in total
- The first task was attempted by 78 (72%) of the competitors, 70 (89%) of which were correct solutions
- The second task was attempted by 59 (54%) of the competitors, 54 (92%) of which were correct solutions
- The third task was attempted by 42 (38%) of the competitors, 20 (48%) of which were correct solutions
- The fourth task was attempted by 12 (11%) of the competitors, only 3 (27%) of which were correct solutions
- The fifth task was attempted by 24 (22%) of the competitors, only 5 (21%) 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
Problem 100: Misterious letter
The first task was an easy, implementation based one. Apart from one corner case (getting ouf of bounds when traversing the array) the rest of the task is literally coding what the description says.
Example solution by despotovski01 in Java.
Problem 200: Endless Run
Taking the really small constraints into account, this task is a very straightforward simulation one. Since time complexity is not an issue, we can calculate each of the different rows described (making sure we cover the corner cases of calculating a cell on the very edges of the grid) and simply implement a deterministic finite automaton suitable with the requirements of the task.
Example solution by Dekacc in Java.
Problem 300: The Perfect Build
In this task we are required to maximize the power of a given character based on some rules with regards to their attributes as well as items purchased with an initial amount of gold. It should be immediately obvious why we cannot brute-force the solution (there is a large amount of combinations of items whose computations will never pass the time constraints), however we can notice that there are many subproblems of equal nature that emerge whenever we try to solve one of the recursive iterations, which should associate us with dynamic programming. In fact, this is a very simple rendition of the Knapsack Algorithm with a modified calculation of the power of a character in a certain state of items bought. Afterwards it becomes a textbook DP problem.
Example solution by despotovski01 in Java.
Problem 400: Let There Be Light
This is a relatively difficult implementation task that involves space traversal. Since we have a number of switches that are supposed to be switched, it should be fairly obvious that we will make the use of bitmasks to cover all of the states and easily switch between them. Afterwards we can use a multi-state BFS traversal with the extra state being the value of the mask. This will easily pass the time constraints and give us a correct solution to the problem.
Example solution by despotovski01 in Java.
Problem 500: Stairs to Razor Tower
This task is a difficult, mathematics based task that revolves around the idea of finding a recurrence relation between each of the elements. The sequence in question is the Narayana's Cow Sequence. Despite its humorous name, this sequence covers the needs of our problem and provides us with the recurrence relation for the problem. However, we may also notice that simply applying combinbatorics will not be good enough since calculating huge factorials is too slow (even with using tree factorials as a data structure). Instead, we can transform the recurrence in a state matrix and by simple induction we can conclude that the relation between each value of the sequence for N and N - 1 is exactly the state matrix. Or in other words, we simply need to calculate the state matrix to the power of the input and this will provide us with the result.
