2025 Canadian Computing Olympiad

Day 1, Problem 1: Asteroid Mining

Time Limit: 3 seconds

Problem Description

It is the year \(2217\) and Ryan is an asteroid miner. He makes a living by mining asteroids and selling them at the CCO (Celestial Cargo Outpost).

On his latest mining expedition, he has mined \(N\) mineral chunks where the \(i\)-th chunk has a value \(v_i\) and a mass \(m_i\). Ryan plans to transport a set of chunks to the CCO with his rocket, but he only has enough fuel to last one more trip. He calculated that the maximum total mass he can safely carry on his rocket is \(M\). Due to Ryan's mining technique, the chunks exhibit a special property: for any two mineral chunks, one's mass is divisible by the other chunk's mass.

Help Ryan find the maximum total value he can ship to CCO while adhering to his rocket's constraints.

Input Specification

The first line will contain two space-separated integers \(N~(1 \le N \le 500\,000)\) and \(M~(1 \le M \le 10^{12})\).

The next \(N\) lines will each contain two space-separated integers \(v_i ~(1 \le v_i \le 10^{12})\) and \(m_i ~(1 \le m_i \le 10^{12})\), representing the value and mass of the \(i\)-th mineral chunk respectively. Additionally, for any two mineral chunks \(i, j ~(1 \le i, j \le N)\), either \(m_i \mid m_j\) or \(m_j \mid m_i\), where \(a \mid b\) means that \(a\) is a divisor of \(b\) (i.e., \(\frac{b}{a}\) is an integer).

The following table shows how the available \(25\) marks are distributed:

Output Specification

On one line, output one integer, the maximum total value Ryan can ship to CCO.

Sample Input

6 10 
1 1
5 2
200 6
9 2
6 2
100 1

Output for Sample Input

310

Explanation of Output for Sample Input

Ryan can take all the chucks except the second and fifth chucks to achieve a total value of \(1 + 200 + 9 + 100 = 310\). Note that the total mass of the chunks is \(1 + 6 + 2 + 1 = 10\). We can show that this is optimal.

Day 1, Problem 2: Tree Decorations

Time Limit: 2 seconds

Problem Description

Mateo recently found the perfect decorations for his Christmas tree — more trees!

Specifically, his Christmas tree is a rooted tree \(T\) initially with \(M\) nodes, all painted green. He has another rooted tree \(D\) that he uses as a reference for his decorations. Mateo uses the following process to put on all of his decorations:

• For each node \(i\) in \(D\), he creates a copy of the subtree rooted at \(i\). Let this copy be \(C_i\). Then, he paints the nodes of \(C_i\) red. Finally, he chooses some green node in \(T\) to be the parent of the root of \(C_i\) by connecting them with an edge.

After applying all the decorations, \(T\) ends up containing \(N\) nodes. Unfortunately, he realized that he had forgotten to record what \(D\) is! To make things worse, he accidentally spilled water on \(T\), washing off all the colour from the nodes. After all that, he labels the root of \(T\) as \(1\), and then labels the rest of the nodes from \(2\) to \(N\).

The only information he currently has is the final state of \(T\), as well as \(M\). Help him find the number of possible \(D\) that he could have started with, where two possibilities are considered different if they are structurally distinct.

Rooted trees \(A\) and \(B\) are said to be structurally identical if and only if they have the same number of nodes \(S\), and there is a way to label \(A\)'s nodes from \(1\) to \(S\) and \(B\)'s nodes from \(1\) to \(S\) such that:

• Their roots are labeled the same.

• Nodes labeled \(x\) and \(y\) in \(A\) are connected by an edge if and only if nodes labeled \(x\) and \(y\) in \(B\) are connected by an edge.

Otherwise, \(A\) and \(B\) are considered structurally distinct.

Input Specification

The first line of input contains two space-separated integers \(N\) and \(M\).

The next \(N - 1\) lines each contain two space-separated integers \(u_i\) and \(v_i\) \((1 \leq u_i, v_i \leq N, u_i \neq v_i)\), describing an edge in \(T\) connecting nodes \(u_i\) and \(v_i\). Note that \(T\) is rooted at node 1.

The following table shows how the available \(25\) marks are distributed:

Output Specification

Output the number of possible \(D\) that he could have started with, where two possibilities are considered different if they are structurally distinct.

Sample Input 1

8 3
1 2
1 3
1 4
2 5
2 6
3 7
3 8

Output for Sample Input 1

1

Explanation of Output for Sample Input 1

It is provable that the only possible \(D\) is:

We can get \(T\) the following way:

In the diagram above, the red parts are added as decorations, while the green, filled-in part represents the initial state of \(T\). The dotted lines represent the edges connecting the decorations to the tree.

Sample Input 2

14 5
1 2
1 3
3 4
3 5
1 6
6 7
7 8
7 9
2 10
10 11
10 12
10 13
10 14

Output for Sample Input 2

2

Explanation of Output for Sample Input 2

The first possibility for \(D\) is:

Using this, we can get \(T\) the following way:

The second possibility for \(D\) is:

Using this, we can get \(T\) the following way:

Day 1, Problem 3: Balanced Integer

Time Limit: 30 seconds

Problem Description

Since the CCO often uses integers, Alice needs to learn about the integers! A positive integer \(n\) can be written in base \(b\) as the sequence \(d_{m-1} d_{m-2} \dots d_1 d_0\) if the following hold:

• Each digit \(d_i\) is between \(0\) and \(b-1\), inclusive.

• \(d_{m-1} > 0\).

• \(n = d_{m-1} \times b^{m-1} + d_{m-2} \times b^{m-2} + \dots + d_1 \times b^1 + d_0 \times b^0\).

For example, the integer \(2025\) in base \(19\) is the sequence \((5, 11, 11)\) because \(2025 = 5 \times 19^2 + 11 \times 19^1 + 11 \times 19^0\).

An integer \(n\) is \(b\)-balanced if, when \(n\) is written in base \(b\), the average of the digits is \(\dfrac{b-1}{2}\). For example, \(2025\) is \(19\)-balanced because \(\dfrac{5+11+11}{3} = 9 = \dfrac{19-1}{2}\).

Alice can easily find integers that are \(19\)-balanced. However, she has trouble finding integers that are balanced in multiple ways. Given \(B\) and \(N\), please help Alice find the minimum integer \(x\) such that:

• \(x\) is \(b\)-balanced, for all \(2 \le b \le B\).

• \(x \ge N\).

Input Specification

The first line of input contains two space-separated integers \(B\) and \(N\) \((N \ge 1)\).

It is guaranteed that the answer does not exceed \(10^{18}\).

The following table shows how the available \(25\) marks are distributed:

Output Specification

Output the minimum integer \(x\) from the problem statement.

Sample Input 1

4 100

Output for Sample Input 1

141

Explanation of Output for Sample Input 1

\(141\) in base \(2\) is \(10001101\). The average digit is \[\dfrac{1+0+0+0+1+1+0+1}{8} = 0.5 = \dfrac{2-1}{2}.\] Therefore, \(141\) is \(2\)-balanced.

\(141\) in base \(3\) is \(12020\). The average digit is \[\dfrac{1+2+0+2+0}{5} = 1 = \dfrac{3-1}{2}.\] Therefore, \(141\) is \(3\)-balanced.

\(141\) in base \(4\) is \(2031\). The average digit is \[\dfrac{2+0+3+1}{4} = 1.5 = \dfrac{4-1}{2}.\] Therefore, \(141\) is \(4\)-balanced.

Lastly, \(141 \ge 100\).

Sample Input 2

7 10000000000

Output for Sample Input 2

16926961207710

Hint

Feel free to use these code snippets as part of your solution.

// Important: If x is 0, the result is undefined.
int base_2_length(unsigned long long x) {
  return 64-__builtin_clzll(x);
}

int base_2_sum(unsigned long long x) {
  return __builtin_popcountll(x);
}

Day 2, Problem 1: Restaurant Recommendation Rescue

Time Limit: 2 seconds

Problem Description

A certain aspiring musician K loves going for shabu-shabu! Recently, she's been to \(N\) shabu-shabu restaurants, numbered \(1, 2, \ldots, N\), following the following algorithm:

1. K keeps an ordered list of recommendations, starting with restaurant 1.

2. On the \(i\)-th day, she visits the next recommended restaurant on her list, which recommends her restaurants \(R_i = \{r_{i,1},\ldots,r_{i,\ell_i}\}\).

3. K appends \(R_i\) to her list of restaurants to visit.

4. K repeats steps 2-4 until she runs out of recommended restaurants.

5. K writes down the array \(A_0, \ldots, A_{N-1}\), where \(A_i\) equals the number of restaurants she was recommended on the \((i+1)\)-th day. That is, \(A_i = |R_{i+1}|\).

It is guaranteed that \(\bigcup_{i=1}^N R_i = \{2, \ldots, N\}\) and \(R_i\cap R_j = \varnothing\) for \(i\neq j\), that is, every restaurant, other than the first, will be recommended by exactly one other restaurant.

Once K finishes her list, K's delinquent friend H decides to play a prank on her! She replaces the array \(A_0,\ldots,A_{N-1}\) with another array \(B_0, \ldots, B_{N-1}\)! K thinks that this new array \(B_i\) might just be a cyclic shift of her array, so she asks you to determine all possible \(0\leq k < N\) such that \(A_i = B_{(i + k)\bmod N}\), for all \(0\leq i< N\) and any valid output of her algorithm \(A_0, \ldots, A_{N-1}\).

Furthermore, K will then perform \(Q\) operations, where for the \(i\)-th operation, she swaps \(B_{x_i}, B_{y_i}\) and asks you to do the same on the new array. Can you help K see through her friend's prank?

Input Specification

The first line of input will contain two integers, \(N~(1\leq N\leq 500\,000)\) and \(Q~(0\leq Q\leq 300\,000)\).

The next line of input will contain \(N\) space-separated non-negative integers, \(B_0, B_1, \ldots, B_{N-1}~(0\leq B_i < N)\), the initial sequence.

The \(i\)-th of the next \(Q\) lines of input will contain two integers each, \(x_i\) and \(y_i\) \((0\leq x_i,y_i < N \text{ and } x_i\neq y_i)\), indicating you are to swap \(B_{x_i}\) with \(B_{y_i}\).

The following table shows how the available \(25\) marks are distributed:

Output Specification

For each of the \(Q+1\) arrays (including the initial array \(B_0, \ldots, B_{N-1}\)), let \(S = \{k_1, \ldots, k_m\}\) denote the set of integers \(0\leq k_j < N\) such that there exists a valid output \(A_0, \ldots, A_{N-1}\) of K's algorithm such that \(A_i = B_{(i+k_j)\bmod N}\) for all \(0\leq i < N\). Output, on a single line, the integers \(m\) and \(\sum_{i=1}^m k_i\pmod {998\,244\,353}\), separated by a space.

In particular, if \(S = \varnothing\), your output should be 0 0.

Sample Input

5 3
1 2 0 0 1
0 2
1 3
3 2

Output for Sample Input

1 4
1 1
1 2
1 2

Explanation of Output for Sample Input

The array \(A\) is \([1, 1, 2, 0, 0]\); it can be shown this is the only valid output of K's algorithm that corresponds to the array \(B = [1, 2, 0, 0, 1]\). One input for K's algorithm that yields this array \(A\) is: \[\begin{align*} R_1 &= \{2\} \\ R_2 &= \{3\} \\ R_3 &= \{4,5\} \\ R_4 &= \varnothing \\ R_5 &= \varnothing.\end{align*}\]

After swapping \(B_0\) and \(B_2\), we get the array \[B = [0, 2, 1, 0, 1].\] It can be shown the only valid output of K's algorithm that corresponds to this is \[A = [2, 1, 0, 1, 0].\] One possible input to K's algorithm that yields this array \(A\) is \[\begin{align*} R_1 &= \{2, 3\} \\ R_2 &= \{4\} \\ R_3 &= \varnothing \\ R_4 &= \{5\} \\ R_5 &= \varnothing.\end{align*}\]

Day 2, Problem 2: Patrol Robot

Time Limit: 3 seconds

Problem Description

The Coordinate Control Organization has developed an autonomous robot to patrol \(N\) distinct important locations on a two-dimensional plane. The \(i\)-th location has coordinates \((x_i,y_i)\), and it is guaranteed that no three locations lie on a common line.

To help guide the robot, you may paint some line segments on the ground. Each segment must directly connect two important locations, and no two segments may intersect, except possibly at their endpoints.

The robot will begin its patrol at the midpoint of an arbitrary segment, facing towards one of its endpoints. It will move indefinitely according to the following procedure:

• As long as the robot is in the interior of a segment, it will move forward, towards a segment endpoint.

• When the robot reaches an important location, it will initially be facing directly away from the segment it just traversed. The robot will turn right/clockwise until its line of vision is aligned with a segment that leads away from the current location. The robot will then begin moving along this new segment.

Your task is to paint the segments in such a way that, no matter where the robot starts, it is guaranteed to visit every important location infinitely often. It can be proven that this is always possible.

Input Specification

The first line of input contains a single integer \(N (2 \le N \le 2\,000)\), the number of important locations.

The next \(N\) lines of input each contain two space-separated integers, \(x_i\) and \(y_i\) \((-10^9 \le x_i,y_i \le 10^9)\), the coordinates of the \(i\)-th important location.

It is guaranteed that all \(N\) important locations are distinct and no three lie on a common line.

The following table shows how the available \(25\) marks are distributed:

Output Specification

On the first line, output a positive integer \(M\), the number of line segments you paint on the ground.

The next \(M\) lines of output should each contain two space-separated integers, \(u_i\) and \(v_i\) \((1 \le u_i,v_i \le N, u_i \ne v_i)\), denoting that you paint a line segment between the \(u_i\)-th and \(v_i\)-th important locations.

If there are multiple acceptable answers, output any of them.

Sample Input 1

4
0 0
1 1
1 2
2 1

Output for Sample Input 1

3
1 2
2 3
2 4

Explanation of Output for Sample Input 1

The important locations and painted segments are shown in the following figure:

No matter where the robot starts, it will visit every important location infinitely many times. For example, if the robot starts in the middle of the segment between locations \(1\) and \(2\), facing towards location \(2\), the locations the robot will visit in order are: \[\underline{2, 4, 2, 3, 2, 1}, 2, 4, \dots,\] where the underlined portion is repeated infinitely.

Sample Input 2

8
0 0
0 3
1 1
1 2
4 1
4 2
5 0
5 3

Output for Sample Input 2

9
1 2
2 4
4 8
8 7
7 5
5 1
3 4
4 5
5 6

Explanation of Output for Sample Input 2

The important locations and painted segments are shown in the following figure:

No matter where the robot starts, it will visit every important location infinitely many times. For example, if the robot starts in the middle of the segment between locations \(4\) and \(5\), facing towards location \(5\), the locations the robot will visit in order are: \[5, \underline{7, 5, 6, 5, 1, 2, 4, 3, 4, 8}, 7, 5, \dots,\] where the underlined portion is repeated infinitely. Note that it is not necessary for every segment to be traversed infinitely many times; the solution is valid as long as every location is visited infinitely many times.

Day 2, Problem 3: Shopping Deals

Time Limit: 5 seconds

Problem Description

You are shopping from a store that sells a total of \(M\) items. The store layout can be modelled as a two-dimensional plane, where the \(i\)-th item is located at the point \((x_i,y_i)\) and has a price of \(p_i\).

The store offers \(N\) shopping deals. The \(i\)-th shopping deal is specified by a point \((a_i,b_i)\), and for a cost of \(c_i\), you can obtain one of every item within exactly one of the following four regions of your choice:

• The region of points \((x,y)\) such that \(x \le a_i\) and \(y \le b_i\).

• The region of points \((x,y)\) such that \(x \le a_i\) and \(y \ge b_i\).

• The region of points \((x,y)\) such that \(x \ge a_i\) and \(y \le b_i\).

• The region of points \((x,y)\) such that \(x \ge a_i\) and \(y \ge b_i\).

Each shopping deal can only be used at most once. Items can also be purchased individually by paying their respective price \(p_i\).

You want to obtain at least one of each item in the store. Find the minimum total cost you must pay to do so.

Input Specification

The first line of input contains two space-separated integers \(N\) and \(M\).

The next \(N\) lines of input each contain three space-separated integers, \(a_i\), \(b_i\), and \(c_i\) \((-10^9 \le a_i,b_i \le 10^9, 1 \le c_i \le 10^9)\).

The next \(M\) lines of input each contain three space-separated integers, \(x_i\), \(y_i\), and \(p_i\) \((-10^9 \le x_i,y_i \le 10^9, 1 \le p_i \le 10^9)\).

The following table shows how the available \(25\) marks are distributed:

Output Specification

On a single line, output the minimum total cost that you must pay to obtain at least one of each item.

Sample Input

2 4
1 1 3
3 3 13
0 0 2
0 2 5
2 0 4
2 2 3

Output for Sample Input

12

Explanation of Output for Sample Input

Use the first shopping deal on the region \(\{(x,y) \mid x \le 1, y \ge 1\}\) to obtain the second item. Then, purchase items \(1\), \(3\), and \(4\) individually. The total cost is \(3+(2+4+3) = 12\).