This commentary is meant to give a brief outline of what is required to solve each problem and what challenges may be involved. It can be used to guide anyone interested in trying to solve these problems, but is not intended to describe all the details of a correct solution. We encourage everyone to try and implement these details on their own using their programming language of choice.
Attempts to solve past problems can be submitted on the CCC Online Grader. Also, after a contest is complete, official test data is available by clicking the corresponding “Download” button on our Past Contests webpage.
A small calculation involving the input values is needed to calculate the number of points gained based on the number of packages delivered and the number of points lost based on the number of collisions with obstacles. An if statement is also needed to possibly apply bonus points.
This problem can be solved by using a variable to accumulate the total spiciness of Ron’s chili. This value can be updated for each pepper name read from the input using a loop which iterates N times. One way to perform this update in the body of the loop is to use an if statement with a test for each possible pepper name. An alternative approach is to effectively place the table given in the problem statement in memory and then use the table to look up the SHU value given the name of a pepper. Different programming languages provide different ways of storing this table.
Each of the subtasks for this problem requires us to keep a count for each day of the number of people able to attend the event on that day. These can be kept in five separate variables because there are only five days. However, it is cleaner and probably less error-prone to store these counts in a list or array.
For the first subtask, we can simply search for a day with a count of N. We are told that there will only be one such day.
For the second subtask, we have to calculate the maximum of these five counts and then find the day corresponding to this maximum value. We are told there will only be one such day.
For the third and final subtask, we need to handle "ties". That is, there could be more than one day with the same maximum count value. It is a bit tricky to output the right answer in this case. It is important to avoid printing a comma after the final day number.
To help Bocchi determine how much tape she needs, we need to do some careful counting.
For the first subtask, we can count \(B\), the number of black triangles, which is the number of times \(1\) appears in the input. The correct answer will be \(3 \times B\). Note that we can ignore the second line of input which is also true for the second subtask. However, for this second subtask, there could be adjacent black triangles and Bocchi does not need to place warning tape on the common side in these cases. Notice that each of these common sides contributes two to the value of \(3 \times B\). This means we obtain the correct final answer by subtracting two from \(3 \times B\) for each pair of adjacent black triangles.
The same principle applies to the third subtask but we also have to look for black triangles that are adjacent but in different rows. These can only occur at even-numbered positions (assuming we start counting at zero).
It is possible to solve this problem without making the observation that you can subtract from \(3 \times B\). This approach involves looking for all the places where warning tape needs to be placed. An algorithm is needed which includes sides of triangles on the perimeter of the pathway as well as sides between adjacent triangles which are not the same colour.
Regardless of which approach is taken, many solutions to the first three subtasks will be quite efficient. However, the fourth subtask is meant to ensure this by disallowing overly slow solutions. It specifically requires that not too many passes are made over either row. More formally, only a constant number of passes of each row is allowed. Solutions that miss this requirement are probably too slow because they use a built-in function within a loop which itself loops through a row of triangles.
The intended challenge of the final problem in this year’s competition was different in nature than the last few years. Here, systematically considering each possible placement of the word in the grid will earn full marks if implemented correctly. In fact, it is not possible to solve this problem more efficiently. What some participants may have found difficult is coding this algorithm or approach so that it works correctly in all cases.
We need to carefully consider all possible starting locations of the word and each possible direction from each of these locations. The number of possibilities increases from subtask to later subtask.
Other than for the first subtask, the grid must be stored in memory. It is a two-dimensional structure so a data structure such as a list of lists (or array of arrays) is needed. It is easy to make errors "around the edge of the grid". Care must be taken to only access valid locations within the data structure of choice.
For this last subtask, the possibility of perpendicular bends in the hidden word presents a significant additional challenge because the number of possible locations for the hidden word is quite large. This can result in long repetitive code with lots of cases which is very error-prone. Carefully designed functions with well-chosen parameters can help remove lots of the redundancy reducing the likelihood of errors and simplifying the process of debugging if errors do occur.