CCC 2021 Senior Solutions

Solutions (in C++) and explanations for problems S1-S5 on the 2021 Canadian Computing Competition.

S1

Problem Statement
Solution

Area of each fence piece is the area of the triangle on top + the area of the rectangle below. Sum up for the final answer.

Time Complexity: $O(N)$

S2

Problem Statement
Solution

Notice that repeating an instruction twice cancels it out. Use a set to collect all unique instructions. Count all of the instructions on rows ($r$) vs. columns ($c$). The answer is going to be $r(n-c) + c(m-r)$.

($n \times m$ cells)

Time Complexity: $O(K\log K)$

S3

Problem Statement
Solution

Let $f(x)$ be the sum of the required times for all $N$ friends to gather at location $x$. Notice $f(x)$ is a convex function (I figured this out by simply observing the outputs). This means we can apply binary search to find the minimum of $f(x)$. On each iteration, test 3 points to determine the bounds for the next iteration. Refer to my solution for specific details.

Time Complexity: $O(N)$, something like $O(N\log(2^{20}))$

S4

Problem Statement
Solution

First notice that it is always going to be optimal to take some portion of the subway only at the beginning. If you get off the subway and take it again at some other station, it would be the same as staying on the subway.

Do a breadth-first-search to find the shortest distances from the final station ($N$) to every other station using only walking paths. Next, add the time for the subway to reach station $x$ to the walking time from $x$ to $N$. The answer for each day is going to be the minimum among all stations.

To answer the queries efficiently, notice that exactly two stations will be affected each day. So, on the beginning of the day where station $a$ and station $b$ are swapped, subtract the time for the train to reach station $a$ from the total time (calculated earlier) for station $a$. Do the same for $b$, and then just add the train times again. This will allow the swaps to be done in $O(\log n)$ and minimum queries to be done in $O(\log n)$ if something like std::multiset is used.

Time Complexity: $O(D\log N + N + W)$

S5

Problem Statement
Solution

Notice that it is optimal for $A_i$ (in the answer array $A$) to be the least common multiple (LCM) of all $z$ of constraints that pass over it $(l, r, z)$ $l \leq i \leq r$. Afterwards, we can check if all the constraints are satisfied.

Notice that $1 \leq z \leq 16$. We can maintain 16 difference arrays to keep track of which ranges are a constraint for all $z$.

Afterwards, we can build a segment tree in $O(n)$ time using the information from the difference arrays, and simply do $O(\log n)$ range GCD queries with the segment tree to verify that all constraints are satisfied.