2025 Canadian Computing Olympiad

Day 1, Problem 1
2025 Canadian Informatics Workshop
Day 1, Problem 3
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 vi and a mass mi . 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 ≤ N ≤ 500 000) and M (1 ≤
M ≤ 1012 ).
The next N lines will each contain two space-separated integers vi (1 ≤ vi ≤ 1012 ) and mi
(1 ≤ mi ≤ 1012 ), representing the value and mass of the i-th mineral chunk respectively.
Additionally, for any two mineral chunks i, j (1 ≤ i, j ≤ N ), either mi | mj or
mj | mi , where a | b means that a is a divisor of b (i.e., b/a is an integer).
The following table shows how the available 25 marks are distributed:

Marks Awarded Bounds on N Bounds on M Additional Constraints

2 marks N =2 1 ≤ M ≤ 104 None
2 marks 1 ≤ N ≤ 20 1 ≤ M ≤ 104 None
4 marks 1 ≤ N ≤ 1 000 1 ≤ M ≤ 104 None
6 marks 1 ≤ N ≤ 1 000 1 ≤ M ≤ 108 None
2 marks 1 ≤ N ≤ 500 000 1 ≤ M ≤ 108 All mi are equal.
3 marks 1 ≤ N ≤ 500 000 1 ≤ M ≤ 108 At most 2 distinct mi .
6 marks 1 ≤ N ≤ 500 000 1 ≤ M ≤ 1012 None
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.
 2025 Canadian Computing Olympiad
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
Ci . Then, he paints the nodes of Ci red. Finally, he chooses some green node in T to
be the parent of the root of Ci 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 ui and vi (1 ≤ ui , vi ≤
N, ui ̸= vi ), describing an edge in T connecting nodes ui and vi . Note that T is rooted
at node 1.
The following table shows how the available 25 marks are distributed:

Marks Awarded Bounds on N Bounds on M

2 marks 2 ≤ N ≤ 10 M =1
3 marks 2 ≤ N ≤ 200 M =1
2 marks 2 ≤ N ≤ 500 000 M =1
6 marks 2 ≤ N ≤ 200 1≤M <N
4 marks 2 ≤ N ≤ 2 000 1≤M <N
8 marks 2 ≤ N ≤ 500 000 1≤M <N

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:

 1

2 3 4

5 6 7 8

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:

 1

2 3 6

10 4 5 7

11 12 13 14 8 9

The second possibility for D is:

Using this, we can get T the following way:

2 3 6

10 4 5 7

11 12 13 14 8 9
 2025 Canadian Computing Olympiad
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 dm−1 dm−2 . . . d1 d0 if the following hold:

• Each digit di is between 0 and b − 1, inclusive.

• dm−1 > 0.
• n = dm−1 × bm−1 + dm−2 × bm−2 + · · · + d1 × b1 + d0 × b0 .

For example, the integer 2025 in base 19 is the sequence (5, 11, 11) because 2025 = 5 × 192 +
11 × 191 + 11 × 190 .
b−1
An integer n is b-balanced if, when n is written in base b, the average of the digits is .
2
5 + 11 + 11 19 − 1
For example, 2025 is 19-balanced because =9= .
3 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 ≤ b ≤ B.

• x ≥ N.

Input Specification
The first line of input contains two space-separated integers B and N (N ≥ 1).
It is guaranteed that the answer does not exceed 1018 .
The following table shows how the available 25 marks are distributed:

Marks Awarded Bounds on B Bounds on N

2 marks 2≤B≤7 1 ≤ N ≤ 104
6 marks 2≤B≤6 N = 1010
2 marks 2≤B≤7 None
9 marks 8 ≤ B ≤ 11 N =1
4 marks B=8 None
2 marks 9 ≤ B ≤ 11 None
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

1+0+0+0+1+1+0+1 2−1
141 in base 2 is 10001101. The average digit is = 0.5 = .
8 2
Therefore, 141 is 2-balanced.
1+2+0+2+0 3−1
141 in base 3 is 12020. The average digit is =1= . Therefore, 141
5 2
is 3-balanced.
2+0+3+1 4−1
141 in base 4 is 2031. The average digit is = 1.5 = . Therefore, 141 is
4 2
4-balanced.
Lastly, 141 ≥ 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);
}
 2025 Canadian Computing Olympiad
Day 2, Problem 1
2025 Canadian Informatics Workshop
Day 2, Problem 3
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, . . . , 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 recom-
mends her restaurants Ri = {ri,1 , . . . , ri,ℓi }.

3. K appends Ri 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 A0 , . . . , AN −1 , where Ai equals the number of restaurants she
was recommended on the (i + 1)-th day. That is, Ai = |Ri+1 |.

It is guaranteed that N
S
i=1 Ri = {2, . . . , N } and Ri ∩ Rj = ∅ for i ̸= 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 A0 , . . . , AN −1 with another array B0 , . . . , BN −1 ! K thinks that this new array Bi
might just be a cyclic shift of her array, so she asks you to determine all possible 0 ≤ k < N
such that Ai = B(i+k) mod N , for all 0 ≤ i < N and any valid output of her algorithm
A0 , . . . , AN −1 .
Furthermore, K will then perform Q operations, where for the i-th operation, she swaps
Bxi , Byi 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 ≤ N ≤ 500 000) and Q (0 ≤ Q ≤
300 000).
The next line of input will contain N space-separated non-negative integers, B0 , B1 , . . . , BN −1
(0 ≤ Bi < N ), the initial sequence.
The i-th of the next Q lines of input will contain two integers each, xi and yi (0 ≤ xi , yi < N
and xi ̸= yi ), indicating you are to swap Bxi with Byi .
The following table shows how the available 25 marks are distributed:

Marks Awarded Bounds on N Bounds on Q

3 marks 1≤N ≤8 Q=0
7 marks 1 ≤ N ≤ 5 000 Q=0
10 marks 1 ≤ N ≤ 500 000 Q=0
5 marks 1 ≤ N ≤ 500 000 0 ≤ Q ≤ 300 000

Output Specification
For each of the Q + 1 arrays (including the initial array B0 , . . . , BN −1 ), let S = {k1 , . . . , km }
denote the set of integers 0 ≤ kj < N such that there exists a valid output A0 , . . . , AN −1 of
P that Ai = B(i+kj ) mod N for all 0 ≤ i < N . Output, on a single line, the
K’s algorithm such
integers m and m i=1 ki (mod 998 244 353), separated by a space.

In particular, if S = ∅, 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:

R1 = {2}
R2 = {3}
R3 = {4, 5}
R4 =∅
R5 = ∅.
After swapping B0 and B2 , 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

R1 = {2, 3}
R2 = {4}
R3 =∅
R4 = {5}
R5 = ∅.

Tips for Python (CIW Only) You are recommended to use fast input (for example,
sys.stdin.read() and sys.stdout.write()) if you are attempting the final subtask.
 2025 Canadian Computing Olympiad
Day 2, Problem 2
Patrol Robot

Time Limit: 3 seconds

Problem Description
The Coordinate Control Organization has developed an autonomous robot to patrol N dis-
tinct important locations on a two-dimensional plane. The i-th location has coordinates
(xi , yi ), 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 ≤ N ≤ 2 000), the number of important
locations.
The next N lines of input each contain two space-separated integers, xi and yi (−109 ≤
xi , yi ≤ 109 ), 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:

Marks Awarded Additional Constraints

2 marks 2≤N ≤4
4 marks 2≤N ≤8
3 marks 3 ≤ N and the N points are the vertices
of a convex polygon in some order.
7 marks The N points form a convex polygon with N − 1
vertices plus an additional point inside the polygon.
9 marks None

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, ui and vi
(1 ≤ ui , vi ≤ N, ui ̸= vi ), denoting that you paint a line segment between the ui -th and vi -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:

4
2
1
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:
2, 4, 2, 3, 2, 1, 2, 4, . . . ,
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:

2 8

4 6

3 5

7
1

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, 7, 5, 6, 5, 1, 2, 4, 3, 4, 8, 7, 5, . . . ,

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.
 2025 Canadian Computing Olympiad
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 (xi , yi ) and has a
price of pi .
The store offers N shopping deals. The i-th shopping deal is specified by a point (ai , bi ),
and for a cost of ci , 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 ≤ ai and y ≤ bi .

• The region of points (x, y) such that x ≤ ai and y ≥ bi .

• The region of points (x, y) such that x ≥ ai and y ≤ bi .

• The region of points (x, y) such that x ≥ ai and y ≥ bi .

Each shopping deal can only be used at most once. Items can also be purchased individually
by paying their respective price pi .
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, ai , bi , and ci (−109 ≤
ai , bi ≤ 109 , 1 ≤ ci ≤ 109 ).
The next M lines of input each contain three space-separated integers, xi , yi , and pi (−109 ≤
xi , yi ≤ 109 , 1 ≤ pi ≤ 109 ).
The following table shows how the available 25 marks are distributed:
 Marks Awarded Bounds on N Bounds on M Additional Constraints
1 mark 1≤N ≤8 1 ≤ M ≤ 20 None
3 marks 1 ≤ N ≤ 70 1 ≤ M ≤ 20 None
3 marks 1 ≤ N ≤ 70 1 ≤ M ≤ 70 None
4 marks 1 ≤ N ≤ 100 1 ≤ M ≤ 100 000 No two points (ai , bi ) or (xj , yj )
have the same x or y-coordinate.
2 marks 1 ≤ N ≤ 100 1 ≤ M ≤ 100 000 None
8 marks 1 ≤ N ≤ 1 000 1 ≤ M ≤ 100 000 No two points (ai , bi ) or (xj , yj )
have the same x or y-coordinate.
4 marks 1 ≤ N ≤ 1 000 1 ≤ M ≤ 100 000 None

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) | x ≤ 1, y ≥ 1} to obtain the second item.
Then, purchase items 1, 3, and 4 individually. The total cost is 3 + (2 + 4 + 3) = 12.