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.
The first problem is designed to be accessible with some insight required to obtain full marks.
The first subtask can be hard-coded. That is, the following table can be calculated by hand and a solution can mimic looking up the correct output in the table.
| \(N\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Output | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
For the second and third subtasks, we can notice that we need \(N=4a+5b\) for non-negative integers \(a\) and \(b\) where \(a \leq \frac{n}{4}\) and \(b \leq \frac{n}{5}\) . This means we can try all possible values for \(a\) and \(b\) using two nested loops.
For a full solution, we can loop through only all possible values of \(a\) to determine if there is a corresponding value of \(b\). For each of these values \(i\), this is equivalent to checking if \(N-4i\) is divisible by 5. Alternatively, we take a similar approach but loop through only all possible values of \(b\).
There is also a clever extremely quick solution that involves extending the table listed above for the first subtask to \(N=20\) and considering the quotient and remainder when \(N\) is divided by 20.
The second problem in this year’s competition requires 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++).
For the first subtask, it suffices to run a brute-force check of all possible outputs to determine if there is a piece that will satisfy the clarinet players.
For the second subtask, note that no sequence of length 3 is good. Also, all sequences of length 1 are good. Thus, we should try to find a piece with \(K-N\) good samples of length 2. We can build it as we go. From the left, if we still need good samples, we can swap to the other pitch, otherwise, we can keep the same pitch. Note that all values between \(N\) and \(2N - 1\) inclusive are possible and no others are.
For the third subtask, we can build on our solution to the second subtask. As before, suppose we are building a piece, our current sequence is \(S\), and our required count is \(K - N\). Depending on how many more good samples we need, we can decide what to append to our sequence \(S\). For instance, if we no longer need any good samples, we can simply add a value equal to the current last value of the sequence. If we need 3 more, we can add the note 4 notes back. That way, there are 3 additional good samples. We can also pick a new number if we want even more good samples. It suffices to greedily choose the number that gives us the most samples up to the remaining amount. When implementing this idea, it’s a good idea to keep track of the longest suffix of your sequence \(S\) that is good.
The last subtask involves the same idea but when adding a new number to the end, we have to instead do a proper check to see if the new number is too large.
For the first subtask, it suffices to follow the definition of a good
triplet. Firstly, there are \(O(N^3)\)
ways to select \((a, b, c)\). Secondly,
consider the condition that the origin is strictly inside the triangle.
This is equivalent to saying that \(P_a\), \(P_b\), and \(P_c\) divide the circle into 3 arcs, and
each arc is strictly shorter than \(\frac{C}{2}\). This leads to the following
approach. Sort the positions so that \(P_a
\leq P_b \leq P_c\), then check that \[P_b-P_a < \frac{C}{2}, P_c-P_b <
\frac{C}{2}, \text{ and } (P_a+C)-P_c < \frac{C}{2}.\] For
example, the first of these checks can be implemented in code as
P[b]-P[a] < (C+1)/2 in C++ or Java, or
P[b]-P[a] < (C+1)//2 in Python 3.
For the second subtask, the goal is to find a solution that works well when \(C\) is small. Let \(L_x\) be the number of points drawn at location \(x\). If three locations \(i\), \(j\), \(k\) satisfy the second condition, we want to add \(L_i \times L_j \times L_k\) to the answer. This approach is \(O(N+C^3)\) and is too slow. However, we can improve from three nested loops to two nested loops. If \(i\) and \(j\) are chosen already, either \(k\) does not exist, or \(k\) is in an interval. It is possible to replace the third loop with a prefix sum array. This algorithm’s time complexity is \(O(N+C^2)\).
It is possible to optimize this approach to \(O(N+C)\) and earn 15 marks. The idea is to eliminate both the \(j\) and \(k\) loop. Start at \(i = 0\) and compute \(L_j \times L_k\) in \(O(C)\) time. The next step is to transition from \(i = 0\) to \(i = 1\), and to maintain \(L_j \times L_k\) in \(O(1)\) time. This requires strong familiarity with prefix sum arrays. Care with overflow and off-by-one errors is required.
In the first subtask, the students and their friendships form a line.
One approach to this subtask involves dynamic programming. Let \(DP[i]\) be the minimum cost required for the first \(i\) students to end up intending to write the CCC (ignoring any later students). Note that \(DP[0] = 0\), and our answer will be \(DP[N]\).
For each value of \(i\) from \(0\) to \(N-1\), we’ll consider transitions onwards
from that state, with the subarray of students from \(i+1\) to \(j\) (for each possible \(j\) such that \(i
< j \le N\)) ending up intending to write the CCC. If at least
one of those students has a \(P\) value
of Y, then it’s possible to perform this
transition by choosing a Y student and
“expanding their influence” to all others, updating \(DP[j]\) accordingly.
For each \(i\), we can consider all possible values of \(j\) while computing their transitions’ minimum costs in a total of \(O(N)\) time, resulting in an overall time complexity of \(O(N^2)\).
To solve the remaining subtasks, we’ll use a different dynamic programming formulation, this time on the tree structure formed by the students and their friendships. We’ll consider the tree to be rooted at an arbitrary node (student), such as node 1.
Let \(DP[i][j]\) (defined for \(1 \le i \le N\) and \(0 \le j \le 2\)) be the minimum cost required for all students in \(i\)’s subtree to end up intending to write the CCC, such that:
if \(j = 0\), \(i\) will be influenced by its parent
if \(j = 1\), i will have no particular interaction with its parent
if \(j = 2\), i will influence its parent
Our answer will then be \(DP[1][1]\).
As is typical for DP on trees, we’ll recurse through the tree, and for each node i, we’ll compute \(DP[i][0..2]\) based on the DP values of \(i\)’s children. Each value \(DP[i][j]\) must be computed carefully, with different logic depending on the values of \(P[i]\) and \(j\).
An implementation of this algorithm may take \(O(N^2)\) time (with some DP transitions taking \(O(N)\) time each to compute), but optimizations can be applied to reduce it to an overall time complexity of \(O(N)\) and have it earn full marks.