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 \(i\) is directly opposite to the person in seat \(i + \frac{N}{2}\).
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 \(i\) in a list, if both \(i\) and \(i + \frac{N}{2}\) exist in the same list.
We notice that we can do the check directly on the input as a list. For each person at seat \(i\), we check if the opposite person at seat \(i + \frac{N}{2}\) has the same hat number. Since each seat is indexed from \(1\) to \(N\), if \(i > \frac{N}{2}\) then \(i + \frac{N}{2}\) will be greater than \(N\). To ensure that we stay within bounds, there are a couple approaches we can use:
loop from \(1\) to \(N\) and compare \(i\) and \((i + \frac{N}{2}) \% N\) to count person at seat \(i\);
loop from \(1\) to \(N\) and subtract \(N\) from \(i + \frac{N}{2}\) if it is greater than \(N\) to count person at seat \(i\);
loop from \(1\) to \(\frac{N}{2}\) and count for person at seat \(i\) and seat \(i + \frac{N}{2}\).
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 \(N=2\), we can use casework
on all possible cases. Alternatively, note that the only moves that can
be made are to do nothing, swipe left on \([0,1]\), or swipe right on \([0,1]\). After \(1\) swipe, additional swipes will not
change the array \(A\), as both
elements of \(A\) will be the same.
Thus, we can try all possible moves, and check if array \(A\) becomes \(B\). Otherwise, the answer will be
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 \(A\) twice. If we are able to reach array \(B\), then we print out the sequence of swipes and return. As \(N \le 8\), with careful implementation, this should pass comfortably in time.
Let \(B'\) be the "compressed"
version of \(B\), where all adjacent
equal elements of \(B\) are removed.
Then, the answer is YES if and only if \(B'\) is a sub-sequence of \(A\).
To see why this is the case, notice that intersecting a necessary left swipe with a necessary right swipe will overwrite valuable elements. Take \(A=[1,2]\) and \(B=[2,1]\) as an example. In order to make the first element a \(2\), we must swipe left and we get \(A=[2,2]\). However, we cannot make the second element a \(1\) now, as the \(1\) has been overwritten. A similar argument follows if we first try to swipe right. Thus, it is impossible for array \(A\) to turn into \(B\). When \(B'\) is not a sub-sequence of \(A\), there will inevitably be a case where a necessary left swipe intersects a necessary right swipe, which makes it impossible.
To construct the solution, we employ a 2-pointers approach. Iterate \(i\) through each element of \(A\), and increment \(j\) while \(A_i\) is equal to \(B_j\). This will capture the range of elements that we need to swipe across. We push all left swipes into a list of swipes \(left\), and right swipes into a list of swipes \(right\). Notice that left swipes should be performed in increasing order of right endpoints, while right swipes should be performed in decreasing order of left endpoints, so that valuable elements will not get overwritten. Thus, we can push the reversed \(right\) into \(left\) to get the correct order of swipes.
This solution runs in \(\mathcal{O}(N)\) time, which is sufficient for full marks. Subtask 3 was meant for suboptimal implementations of the full solution.
We can model the intersections and roads as an undirected graph. In this subtask, the roads connecting intersection \(i\) with intersection \(i+1\) for all \(1 \le i < N\) ensure that the graph is connected and has a Hamiltonian path \(1 \leftrightarrow 2 \leftrightarrow \dots \leftrightarrow N\).
First, observe that Alanna must paint at least \(N-1\) roads. If not, then the coloured roads will not form a connected subgraph. Because the original graph is connected, there must be a grey road connecting two different components of coloured roads, and there is no coloured path connecting the endpoints of this grey road.
Because we’re guaranteed a Hamiltonian path \(1 \leftrightarrow 2 \leftrightarrow \dots \leftrightarrow N\), let’s consider choosing these \(N-1\) roads to paint. Thinking about what constraints on the colours are necessary to satisfy the condition in the problem, we can realize that it suffices to colour the roads alternating between red and blue along the path \(1 \leftrightarrow 2 \leftrightarrow \dots \leftrightarrow N\).
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 \(N-1\) roads. To achieve this bound, we can colour the edges of the cycle by alternating between red and blue, leaving exactly one cycle edge grey. The other edges should be coloured red or blue arbitrarily.
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 \(u \leftrightarrow v\) not in the spanning forest, we can colour the path (in the corresponding tree) connecting \(u\) and \(v\) by alternating between red and blue. Because the component is a cactus, these paths do not share any edges, so we don’t have to worry about these edges being involved in conflicting constraints.
An arbitrary spanning forest can be found with algorithms like BFS or DFS. To determine the correct colours, we cannot afford to spend \(O(N)\) time per path because there could be as many as \(\frac{N-1}{2}\) grey edges. Instead, we need to identify the corresponding path in \(O(\text{length of path})\) time. One way to do this is by first precomputing parents and depths of each node within a tree. Then, for each grey edge \(u \leftrightarrow v\), trace out the path by repeatedly moving the deeper node (\(u\) or \(v\)) up to its parent until \(u\) and \(v\) coincide.
The solution from subtask \(3\) no longer works because the paths induced by each grey edge are no longer disjoint, so it is possible that they cause some conflicting constraints on the colours. It is no longer enough to take an arbitrary spanning forest.
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 \(u \leftrightarrow v\), and let the LCA (lowest common ancestor) of \(u\) and \(v\) in the tree be \(l\). The constraints on the colours that this grey edge places are that (1) all edges between \(u\) and \(l\) must be different from its parent edge, (2) all edges between \(v\) and \(l\) must be different from its parent edge, and (3) if \(u \ne l\) and \(v \ne l\), then two child edges of \(l\) are different.
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 \(\mu\). Notice that the mean of each component of a valid partition must be \(\mu\). Now consider the transformation of \(A_{i,j} = T_{i,j} - \mu\). This reduces the problem to splitting array \(A\) into the maximum number of parts such that each part has a sum of 0.
Now let \(P_{j,i}\) be the prefix sum array for \(A_{j}\). That is, \[P_{j,i} = \sum_{c = 1}^i A_{j,c}\]
We will solve the new problem with dynamic programming. Let \(dp[k][i]\) represent the maximum number of parts we can split the first \(i\) columns of the array such that the sum of each part is 0 and there is a (possibly empty) component sticking out of the \(k\)-th row (row 1 or row 2). Thus, for the base case we have that \(dp[k][0] = 0\).
We can incrementally update \(dp[k][i]\) starting from the smallest \(i\). First set \(dp[k][i]\) to be the maximum of
\(dp[k][i - 1]\) (\(A_{k,i}\) is sticking out)
\(dp[3 - k][i - 1]\) (\(A_{k,i}\) and \(A_{3-k,i}\) are in one component)
\(dp[k][j] + 1\) such that \(P_{3-k,j} = P_{3-k,i}\) and \(j < i\) (Add a "line component" from \(A_{3-k,j+1}\) to \(A_{3-k,i}\))
\(dp[3 - k][j] + 1\) such that \(P_{k,i} + P_{3-k, j} = 0\) (Finish the component by cutting a chunk from the first \(i\) cells on row \(3-k\) and the first \(j\) cells on row \(k\))
Then if \(P_{1, i} + P_{2, i} = 0\), simultaneously update \(dp[1][i]\) and \(dp[2][i]\) as \(\max(dp[0][i], dp[1][i]) + 1\) to signify that we split between column \(i\) and \(i + 1\) (or we reach the end of \(i = N\)).
The final answer is \(dp[1][N]\). To help understand how this is sufficient, it is helpful to draw out the transitions with multiple cases and notice that the sum of the component that is sticking out for \(dp[k][i]\) is \(P_{k, i}\).
This results in an \(\mathcal{O}(N^2)\) algorithm as seen in cases 3 and 4. We can make it run in sub-quadratic time by maintaining maps of \(P_{k, i} \rightarrow \max dp[k][i]\) and \(P_{k, i} \rightarrow \max dp[3 - k][i]\) as we compute \(dp[k][i]\).
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.