2023 Canadian Computing Competition
Senior Problem Commentary
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.
S1 Trianglane
To help Bocchi determine how much tape she needs, we need to do some
careful counting.
For the first subtask, we can count , the number of black triangles, which
is the number of times 1 appears in the input. The correct answer will
be . 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 .
This means we obtain the correct final answer by subtracting two from
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 . 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.
S2 Symmetric
Mountains
To solve this problem, we will find the asymmetric value for each
crop and compute the minimum asymmetric value for each crop’s
corresponding length. For every subtask, we find different ways to
compute the asymmetric value of each crop.
Subtask 1
Considering iterating over all crops. A crop is defined by its left
endpoint and right endpoint. Hence, we can use a nested for loop to
first fix the left endpoint and then fix the right endpoint. There are
other ways to loop through crops, such as looping through its left
endpoint and its length and vice versa. To find the asymmetric value of
a crop, we can have an accumulator and sum up the absolute difference
for every such pair by looping over defined in the problem statement. There
are such
crops, and we need about
calculations on average to to compute the asymmetric value of each crop;
hence, it runs in time that is roughly cubic in the number of
mountains.
Subtask 2
For this subtask, we note that if we were to find the asymmetric
value of each crop, then we have to do it faster than roughly time. Now consider a crop with a left
endpoint of and a right endpoint
of . We will take a closer look at
the formula to compute the asymmetric value: where . Note
that because the array is non-decreasing in this subtask, then it
follows that for mountains with indices , we have that . Hence the above formula is equivalent to Let , which represents the
midpoint of the mountains (it may not be an integer, but that does not
matter). Notice that for every term whose index is greater than , it is being added, and for every term
whose index is less than it is
being subtracted. We can then rearrange the formula to become Note that we have
simplified this problem into static range sum queries. We can compute
them quickly by building a prefix sum array of the mountains’ heights
(i.e., an array where the th
element is the sum of the first
elements of ) before iterating
through all the crops. Note that to calculate the asymmetric crop, in
this case, it will be constant time (i.e., independent of ), so this runs in quadratic time in the
number of mountains.
Subtask 3
We will now let represent
a crop where are the left
and right endpoints, respectively. Now for this subtask, let us take a
closer look at the formula for the crop : Notice that the terms in brackets are the asymmetric
value of the crop . If we
have a way to iterate through the crops so that crop comes right before , we can add directly to the accumulator
to get the asymmetric value of crop . This motivates us to cleverly iterate over the crops by
fixing the midpoint and expanding outwards while maintaining an
accumulator for each midpoint. Note that the midpoint will not be an
actual mountain for crops with even length. This runs in time which is
the square of the number of mountains. As we move from crop to , we only add a term to the
accumulator. Note that there exist dynamic programming solutions, but
these were not necessary to receive full marks.
S3 Palindromic
Poster
Subtask 1
For this subtask, since
and , we can try and make only
the first row and column a palindrome. One way to do this is to fill the
first row and column with the letter a
and fill the rest of
the grid with the letter b
.
Subtask 2
Because there are so few cases, it suffices to solve this subtask on
paper and hardcode the answers. To reduce the amount of casework, notice
that if we have a solution for , we can get a solution for by flipping the grid.
Another possible approach is to write a brute force since there are
only four important possibilities for each cell.
Subtask 3
This subtask is intended to aid students in thinking about the
problem.
Subtask 4
The solutions to subtasks 1 and 2 should give some intuition here.
From subtask 1, we propose the following general solution:
Fill the first rows and the
first columns with the letter
a
and fill the rest of the grid with the letter
b
.
We notice that this fails when , , or . We can handle these in pairs since we can flip the grid.
If , we can fill the first
columns with the letter
a
, and the last column with the letter b
, and
then increment the last
characters of the last row. For instance, for the input
4 4 0 2
we can output:
aaab
aaab
aaab
aabc
If , every row must be a
palindrome. Because of this, starting from a full grid of a
characters, we can easily reduce the number of palindromic columns by
two at a time by making matching columns of the first row b
characters. For instance, for the input 4 4 4 2
, we can
output:
baab
aaaa
aaaa
aaaa
However, this fails if is not
the same parity as , that is, if
we cannot get by subtracting
an integer number of times from
.
In this case, it depends: if
is odd, we can use the middle column. For instance, for the input
5 5 5 2
:
babab
aaaaa
aaaaa
aaaaa
aaaaa
However, the input 4 4 4 1
is impossible since there is
no middle column.
We can handle and symmetrically by flipping the
inputs, processing, and then flipping the output.
S4 Minimum Cost
Roads
Subtask 1
This subtask can be solved by running an MST (Minimum Spanning Tree)
algorithm that only considers the cost of each edge. Note that we may
have multiple components, so our final answer will be the sum of costs
of the MST of each component. Luckily, an algorithm like Kruskal’s
handles this problem without any additional complexity.
Subtask 2
The constraints of this subtask allow us to focus on an invariant
that is very useful in the long run. Consider a single edge . We get the following
cases:
If is the unique shortest
path from to , we definitely want to take ;
If there exists a path from to with length , we definitely don’t want to
take ;
If there exists another path from to with length (but no paths that are shorter),
we still don’t want to take .
However, this time the proof is much more complex:
Suppose is a path from to consisting of edges such that
Now, suppose that is
the unique shortest path between its endpoints and . If this is not the case for some
, then we can find another path
from to with length exactly and replace with that path (if that path had
length then
we would have a path from to
with length , which is a contradiction).
Observe that this process can only be repeated a finite number of
times.
In the end, we have a path from to that has length , does not take the edge , and every edge in that path is the
unique shortest path between its endpoints. We’ll call the edges on this
path .
Now consider some optimal answer that contains the edge . Clearly, must be in the answer.
However, this means that we can remove as any time we need to traverse from
to , we can take the edges instead. This violates
the optimality of the answer and is thus a contradiction.
This results in a very simple solution for this subtask: we loop over
every edge and
check whether it’s the unique shortest path between and . One way to do this is to first run
Dijkstra’s algorithm times to
find the shortest path between every pair of nodes (and store it in a
2-D array dist). Then, for each edge we check if
Remark: Notice that we don’t even care about costs
at all! In fact, the original problem didn’t have costs (), but we thought it was an
interesting extension :)
Subtask 3
Unfortunately, we lose the guarantees that allow our solution from
subtask 2 to work. Fortunately, we can restore these guarantees with
some clever reductions.
First, let’s look at the graph formed by all of the -length edges. If any pair of nodes
are connected in this graph,
then our answer must contain a path of length between and . Thus, we must choose a subset of the
-length edges that has the same
connectivity properties as the original graph (i.e. if are connected by -length edges in the original graph,
then they must be connected by -length edges in our answer). Trying to
do so while also minimizing cost is analogous to finding the minimum
spanning forest of the graph, which is the same as our solution in
subtask 1.
Unfortunately, the -length
edges are still part of our graph. In order to remove them for good, we
must make the following observation: we can treat each component in our
spanning forest as a single node as we’re able to travel between any two
nodes in that component with a path of length . This motivates us to compress our
initial graph by these components to remove all -length edges.
Note: Be careful, the compressed graph may also
contain self-edges so make sure to ignore them.
Next, to remove multiedges notice that we only ever want at most one
edge between any pair of nodes. Thus, we take the one with lowest
length, breaking ties by cost.
Finally, we run our solution from subtask 2 and sum the answer we
obtained from that solution with the one from computing the minimum
spanning forest.
Alternative Solution
There is also an alternative solution much closer to Kruskal’s
algorithm for computing MST: we loop over the edges in order of length,
breaking ties by cost and adding it to the graph if it improves the
shortest path between its endpoints. This solution also has the added
benefit of not worrying about -length edges or multi-edges
separately.
S5 The Filter
Subtask 1
The answers for are .
Suppose the answers for
are . The
answers for the first third of are
The Cantor set has copies of the same structure. In particular, the
first third of the Cantor set is identical to the last third. The
remaining answers for
are
These observations are enough to generate the answer for any power of
.
Subtask 2
Note that is
covered by the 49th filter, but not any earlier filter. This
is the maximum record for . A naive approach is expected to fail on .
This subtask requires deeper observations about Alice’s filters.
Property 1 (Filters are symmetric). If is covered by the -th filter, then is covered by the -th filter. Likewise, if the -th filter does not cover , then is not covered by the -th filter.
Property 2 (The -th
filter and -th filter are
related). Let be a
positive integer, and let . If is covered by
the -th filter, then is covered by the -th filter. Likewise, if is not covered by the -th filter, then is not covered by the -th filter.
The proof of these 2 properties is left as an exercise. From these
properties, it becomes natural to define the function . Here are a
few theorems about .
Theorem 1. If
is not covered by any filter, then is not covered by any filter.
Proof. Apply Property 1 and Property 2.
Theorem 2. Suppose is covered by the -th filter. Then either , or is covered by the -th filter.
Proof. Apply Property 1 and Property 2.
Here is the approach to solving subtask 2:
Let . Construct
this sequence:
If is in the Cantor set,
then by Theorem 1, every term in the sequence is in the Cantor set.
Since every term is a multiple of , the sequence will enter a cycle.
If is not in the Cantor
set, then is covered by a filter.
By Theorem 2, a term in the sequence will be covered by the first
filter.
There are 2 outcomes. Either the sequence will enter a cycle, or a
term will be covered by the first filter. The algorithm needs to handle
both outcomes. The intended time complexity is or slightly slower.
Alternatively, it is enough to ignore cycle detection and construct
the first terms. In the worst
case (i.e. ), the -th term is covered by the first
filter.
Subtask 3
Note that is covered by
the 130th filter, but not any earlier filter. The author
believes this is the maximum record for .
Firstly, use the first 18 filters to remove most of the numbers.
After this step, less than
numbers remain.
Next, apply the algorithm from subtask 2 on each of the remaining
numbers. It may be a good idea to use memoization to improve time
complexity. There are other tricks to improve performance.
The intended time complexity is because there are numbers to consider, and each
number takes roughly to
consider.