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.
We note that there can only be either 2 or 4 people at the table. This can be solved with conditional statements. In the case that there are only 2 people, they are seated across from each other, so we just compare the values of both hats. With 4 people, we can compare the equality of the hats at seat 1 and 3 and seat 2 and 4.
All people have the same hat number 1. This means we can simply count the number of people at the table.
Since people in even-numbered seats have hat number 1 and people in odd-numbered seats have hat number 0, they will only see matching hats if the number of people is divisible by 4.
There was no specific intended approach for this subtask. We observe
that in a circular arrangement, the person in seat
One possible solution would be to store for each hat number, a list
of the seat numbers of the people wearing that hat number. We can then
iterate over the lists for each hat number and check if for each seat
We notice that we can do the check directly on the input as a list.
For each person at seat
loop from
loop from
loop from
Hard-code every possible string containing "a" and "b" of length between 2 and 4 (there are 30 such strings) and output whether it alternates between heavy "a" and light "b" or heavy "b" and light "a".
There was no intended solution for this subtask. It was intended to allow for possibly slower full solutions.
We consider two cases for if it starts with "a" or not:
Check that every second letter is "a" and that the rest are not "a".
Check that every second letter is not "a" and that the rest are "a".
If either case is true, output T
; otherwise, output
F
.
First, create an array that will store the frequency of each letter in the string. Each element represents the count of a particular letter. Then, iterate over all letters in the string and increment the frequency of it in the array.
We realize we can extend the logic from subtask 3 with this array. If a letter has a frequency greater than 1 in the array, it is heavy; if not, it is light.
We consider two cases for if it starts with a heavy letter or not:
Check that every second letter has a frequency greater than 1 and that the rest are light.
Check that every second letter does not have a frequency greater than 1 and that the rest are heavy.
If either case is true, output T; otherwise, output F.
Since NO
.
The intended solution for this subtask is to iteratively brute force
all possible arrays by trying all possible swipes at each step. This can
be implemented similarly to BFS, with a visited map, to ensure we don’t
visit the same array
Let YES
if and only if
To see why this is the case, notice that intersecting a necessary
left swipe with a necessary right swipe will overwrite valuable
elements. Take
To construct the solution, we employ a 2-pointers approach. Iterate
This solution runs in
We can model the intersections and roads as an undirected graph. In
this subtask, the roads connecting intersection
First, observe that Alanna must paint at least
Because we’re guaranteed a Hamiltonian path
In this subtask, the graph is connected and has an equal number of edges and nodes. In other words, the graph forms a pseudotree. In particular, there is exactly one simple cycle in the graph.
Just like in subtask 1, it can be proven that Alanna must paint at
least
This cycle may be found by a carefully implemented graph-traversal algorithm like BFS or DFS.
In this subtask, the graph is no longer guaranteed to be connected. The condition of no road belonging to two or more simple cycles can be rephrased as each connected component of the graph being a cactus graph.
By generalizing the ideas from subtasks 1 and 2, the coloured edges should form a spanning forest of the graph. That would ensure that the coloured edges form the same connected components as the original graph while colouring the minimum number of edges to meet this requirement.
Let’s consider choosing an arbitrary spanning forest of the graph to
colour with red or blue. For each grey edge
An arbitrary spanning forest can be found with algorithms like BFS or
DFS. To determine the correct colours, we cannot afford to spend
The solution from subtask
Guided by these intuitions, let’s think about what conditions on the
spanning forest would be nice to have. Let’s focus on a single connected
component, where the coloured edges form a tree, and let’s root the tree
arbitrarily. Consider a grey edge
Intuitively, most constraints are from types (1) and (2). It is actually possible to satisfy all type (1) and (2) constraints by colouring each edge by the parity of its depth in the tree, but this fails to satisfy any type (3) constraints. This motivates us to consider: Is there a spanning forest where we end up with no type (3) constraints?
In other words, we want a spanning forest with no cross edges: edges that do not connect an ancestor with a descendent. For undirected graphs, the DFS tree (tree formed by a depth-first traversal) has exactly this property we’re looking for. This results in a very short solution to the full problem: For each connected component, take a DFS tree and colour the tree edges red or blue based on the parity of its depth.
The first section will go over the full solution and the last paragraph will touch upon the intended solutions for some subtasks.
Let the mean of the entire array be
Now let
We will solve the new problem with dynamic programming. Let
We can incrementally update
Then if
The final answer is
This results in an
For the first 2 subtasks, we can generate all the possible partitions by hand for Subtask 1 or by running a clever brute force for Subtask 2. The other subtasks are used to reward suboptimal dynamic programming solutions such as using the sum of the component as a state, using the prefix of the first row and the second row simultaneously as a state or with suboptimal transitions.