Creation of this commentary is a new initiative for the Canadian
Computing Competition. Our goal is to give a brief outline of what is
required to solve each problem and what challenges may be involved. The
notes below can be used to guide anyone interested in trying to solve
these problems, but are 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.
Solving this problem involves correctly reading the input and performing some arithmetic. The provided samples illustrate how to compute the number of cupcakes. Then, 28 must be subtracted from this value to determine the number of cupcakes left over.
Loops and if statements are required for this problem. A clean approach is to loop \(N\) times and read two lines of input per loop. This allows you to process one player at a time. A calculation can be performed to determine the player’s star rating, and we can also maintain a count of the number of players with a star rating greater than 40. Care may be needed to produce only one line of output exactly as specified.
There is a lot to consider when attempting to solve this problem. The biggest challenge is to break the input into pieces. This is known as tokenizing the input and the pieces are typically called tokens.
Specifically, the first subtask requires breaking a single
instruction into a sequence of letters, the character
+ or -, and the
number of turns. The focus of the second subtask is to break the input
into different instructions, but each instruction has a simpler form.
The third subtask combines these two objectives. The final subtask adds
an extra layer of difficulty by allowing the number of turns to be a
multi-digit number.
One elegant way to tokenize the input is to iterate through the input character by character while also remembering the last character read. This allows you to recognize when and where one token begins and another token ends. An alternative is to keep track of the current “state” which is an indication of which of the three types of token is currently under consideration.
Outputting the translation of each instruction as it is tokenized, rather than storing up all the translations until the end, removes the need for any extra data structures.
The fourth problem in this year’s competition is the first that requires a collection of input to be stored together in a data structure. Because the assignment of students to groups is not given until the end of the input, the constraints cannot be fully considered as they are encountered, and so must be stored in memory. It is helpful to also store the student groups in memory.
Once both types of input are in memory, a solution can be obtained by considering each constraint individually and maintaining a count of how many are violated.
Likely pitfalls include incorrectly assuming something about the order in which student names appear, and erroneously thinking that a group can only violate one constraint.
Care must be taken with the Boolean logic required to test if a given
constraint is violated. This will require determining if a given student
is in a given group. Doing this inefficiently by looping through all the
groups or looping through all the students should have allowed a
submission to earn 14 of the available 15 marks. To earn the final mark,
this look-up must be made more efficient. This can be accomplished using
a data structure built-in to the language designed for this very purpose
(e.g. a dictionary in Python, a HashMap in
Java, or an unordered_map in C++).
Any participant who was able to make any progress on this problem (or the previous problem, J4) is strongly encouraged to attempt the Senior Contest next year if they remain eligible. Earning more than 8 marks on J5 was especially difficult and intended to provide a significant challenge.
The first subtask can be solved by recognizing that when there is only one tree, a largest square pool must sit at one of the “corners” of the tree. An example of this is drawn in the explanation for the first sample input where a largest pool can sit at the “bottom-left corner” of the tree. As a result, the first three marks can be earned by considering the four possible cases and taking the maximum value.
Once there is more than one tree, a lot more work must be performed. For the second subtask, an approach that uses brute-force will earn full marks. There are different ways to accomplish this but they all amount to essentially testing all possible locations and sizes of a square pool and for each possibility, determining whether or not it contains a tree. Doing this successfully is done most naturally using several nested loops.
Allowing yards to be as large as 500 000-by-500 000 prevents a brute-force approach from finishing within the time limit. However, an important observation for the third subtask is that the number of trees is still guaranteed to be quite small. This is a clue that we might want a solution which depends only on the number of trees and not on the size of the yard. Recursion can be used to do just this. The key idea of the first subtask can be reused here. By inspecting one tree, we can limit our further search for an optimal placement of the pool to above, below, to the left, or to the right of this tree. This reduces the problem to a smaller (now possibly rectangular) yard.
Recursion will fail once the number of trees climbs much higher than 10 because the runtime will grow exponentially as the number of trees increases. Therefore, we require a solution which still depends only on the number of trees, but to a lesser extent. A very clever idea allows us to accomplish this. A square pool that is as large as possible can be moved up until it hits a tree or the upper boundary of the yard. Similarly, a square pool that is as large as possible can be moved left until it hits a tree or the left boundary of the yard. If we imagine adding coordinates to the yard, this means that each tree and the upper boundary provide \(T+1\) candidates for the topmost position of an optimally placed pool. Similarly, there are \(T+1\) candidates for the leftmost position of an optimally placed pool. By considering all pairs consisting of a candidate for the leftmost position and a candidate for the topmost position, we considerably limit the number of possible locations for an optimally placed pool. Moreover, we can figure out the size of the largest possible pool at one of these possible locations by only considering the remaining trees and boundaries. This approach yields a solution with a runtime that computer scientists characterize as cubic in \(T\).