2026 Canadian Computing Competition
Senior Problems

Problem S1: Baby Hop, Giant Hop

Problem Description

Samantha the Frog is hopping between lily pads arranged in a straight line, evenly spaced. There are an infinite number of lily pads. The lily pads are numbered, in order, using integers. For every integer, there is also a lily pad.

Samantha starts on a lily pad numbered \(A\) and would like to hop onto a lily pad numbered \(B\). She can take a giant hop of length \(K\), or a baby hop of length \(1\). Each hop can be either forwards or backwards.

Samantha would like to know the fewest number of hops needed to get from \(A\) to \(B\). But sometimes, she would like to know the second fewest number of hops needed.

Input Specification

The first line of input contains a single integer, \(A\), the starting lily pad \((-10^{18} \leq A \leq 10^{18})\).

The second line of input contains a single integer, \(B\), the ending lily pad \((-10^{18} \leq B \leq 10^{18})\).

The third line of input contains a single integer, \(K\), the distance of a giant hop \((2 \leq K \leq 10^{18})\).

The fourth line of input contains the integer, \(T\), which is either \(1\) or \(2\), indicating if the fewest (when \(T=1\)) or second fewest (when \(T=2\)) number of steps should be found.

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

Note that for full marks, solutions will need to handle 64-bit integers. For example:

• in C/C++, the type long long should be used;

• in Java, the type long should be used.

Output Specification

On a single line, output:

• the fewest number of hops, if \(T=1\)

• the second fewest number of hops, if \(T=2\)

required to move from lily pad \(A\) to lily pad \(B\).

Sample Input 1

0
10
3
1

Output for Sample Input 1

4

Explanation of Output for Sample Input 1

Samantha hops to lily pads labeled \(3\), \(6\), and \(9\), with three giant hops, and then hops to the lily pad labeled \(10\) with one baby hop.

Sample Input 2

0
11
4
1

Output for Sample Input 2

4

Explanation of Output for Sample Input 2

Samantha hops to lily pads labeled \(4\), \(8\), and \(12\), with three giant hops, and then hops to the lily pad labeled \(11\) with one (backwards) baby hop.

Sample Input 3

0
11
4
2

Output for Sample Input 3

5

Explanation of Output for Sample Input 3

The fewest number of hops needed \((4)\) was found in Sample 2. In this input, the second fewest number of steps is to be found, since \(T=2\). Samantha hops to lily pads labeled \(4\) and \(8\) with two giant hops, and then hops to the lily pad labeled \(11\) with three baby hops.

Sample Input 4

0
0
3
1

Output for Sample Input 4

0

Problem J5/S2: Beams of Light

Problem Description

Along one wall of a parking garage there are identical parking spots numbered from \(1\) to \(N\). A collection of lights illuminates the parking garage. Each light shines on some number of adjacent parking spots.

You will be questioned about the parking spots. For each parking spot you are questioned about, your job is to determine whether or not it is illuminated by at least one light.

Input Specification

The first line of input contains a positive integer, \(N\), representing the number of parking spots. The second line contains a non-negative integer, \(L\), representing the number of lights. The third line contains a positive integer, \(Q\), representing the number of parking spots you will be questioned about.

The next \(L\) lines provide information about the \(L\) lights. Line \(i\) will contain two integers, \(P_i\) and \(S_i\), separated by a single space. The first integer, \(1 \leq P_i \leq N\), represents the number of the parking spot above which a light is hung. The second integer, \(0 \leq S_i \leq N\), represents the spread of the light's beam. Light \(i\) shines on the parking spot that is directly below it. It also shines on the \(S_i\) parking spots located on either side, unless there are fewer than \(S_i\) spots on a side, in which case all the spots on that side will be illuminated. There could be more than one light directly above a parking spot.

The next \(Q\) lines of input each contain a positive integer between \(1\) and \(N\) inclusive, representing the number of the parking spot you are questioned about.

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

Output Specification

There will be one line of output for each of the \(Q\) parking spots you are questioned about.

On each of these lines, output Y if the corresponding parking spot is illuminated by at least one light, or N if the corresponding parking spot is not illuminated by any light.

Sample Input

10
3
4
8 0
1 1
4 2
4
10
7
1

Output for Sample Input

Y
N
N
Y

Explanation of Output for Sample Input

The input describes the following picture of the parking garage.

Parking spots \(4\) and \(1\) are illuminated by at least one light.

Parking spots \(10\) and \(7\) are not illuminated by any light.

Problem S3: Common Card Choice

Problem Description

There are \(N\) cards with positive integers written on them. Alice takes some of the cards, then Bob takes some of the remaining cards. Both need to take at least one card; Alice is not allowed to take all of the cards. Then Alice and Bob compute the sum of numbers on the cards that they have taken. If these sums have a common divisor greater than one, Alice and Bob get a bag of sweets; otherwise they don’t. Given the cards on the table, determine if it is possible for Alice and Bob to get the sweets, and if so, how.

To make it even more challenging, in some cases, neither Alice nor Bob knows any of the values on the cards.

Note that an integer \(d\) is a divisor of an integer \(q\) if there is no remainder when \(q\) is divided by \(d\). An integer \(z\) is a common divisor of integers \(x\) and \(y\) if \(z\) is a divisor of both \(x\) and \(y\).

Input Specification

The first line of input contains \(N~(2 \le N \le 10^{5})\).

The second line contains \(N\) integers, \(c_i~(1 \le c_i \le 10^{12})\).

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

Note: For the last subtask, you will be given \(N\), but all \(N\) card values will be labelled with -1, indicating that those card values are unknown to you. In this last subtask, there will always be a selection of cards that Alice and Bob can pick to obtain a bag of sweets.

Output Specification

On the first line of output, print YES if it is possible to get the sweets, otherwise, print NO.

If the answer is YES, on the second line of output, produce \(A\), the number of cards that Alice should take, followed by one space, followed by \(B\), the number of cards that Bob should take. On the third line of output, print out \(A\) space-separated numbers corresponding to the indices of the cards that Alice should take. On the fourth line of output, print out \(B\) space-separated numbers corresponding to the indices of the cards that Bob should take. If there are several ways to select cards, print any of them.

If the input is for the last subtask, output an integer \(K\leq 100\) on the first line, followed by \(K\) possible combinations of output as specified for all other subtasks. That is, each combination will be the same sequence of three lines as stated above: one line containing \(A\) and \(B\); one line containing \(A\) indices of cards; and one line containing \(B\) indices of cards. All guesses of indices of cards must be disjoint: that is, no card index can appear in more than one guess. Your output will be judged correct if any of the combinations would result in Alice and Bob obtaining a bag of sweets. Note that you will not receive any feedback between guesses.

Sample Input 1

7
19 7 11 31 99 13 17

Output for Sample Input 1

YES
3 3
2 3 7
4 6 1

Explanation of Output for Sample Input 1

The sum of Alice’s cards is \(7+11+17=35\) and the sum of Bob’s cards is \(31+13+19=63\), and both \(35\) and \(63\) are divisible by \(7\).

Sample Input 2

3
3 11 17

Output for Sample Input 2

NO

Explanation of Output for Sample Input 2

Notice that \(3\), \(11\), and \(17\) have no common divisors, and all possible sums of two of these numbers (\(14\), \(20\), \(28\)) do not have a common factor with the remaining third number.

Sample Input 3

100000
-1 -1 -1 ...

(The input has been truncated for space. There are a total of \(10^5\) -1s on the second line.)

Output for Sample Input 3

2
1 2
1
3 5
3 2
100 101 102
201 200

Explanation of Output for Sample Input 3

There are a total of two guesses. The first guess consists of indices \(\{1\}\) and \(\{3,5\}\). The second guess consists of indices \(\{100,101,102\}\) and \(\{201,200\}\).

Note that all sets of indices are disjoint.

Although the output is formatted correctly, the output will receive Wrong answer because the two guesses are not enough for Alice and Bob to obtain a bag of sweets.

Problem S4: Minecarts

Problem Description

Steve has \(N\) minecarts labelled from \(1\) to \(N\) lined up on a track in a row from left to right. Initially, there are \(a_i\) gems in the \(i\)-th minecart.

Steve wants the minecarts to be arranged in a row such that the number of gems in each minecart is non-decreasing from left to right. To do this, he plans to build a side track to the right of all of the minecarts that splits off from the main track. Steve can move minecarts that are on the left of the side track into the side track, allowing other minecarts on its left to move past it on the main track. Minecarts moved into the side track can be moved back into the main track one at a time: a minecart on the side track will move back to the left of the side track and to the right of all other minecarts which are on the left of the side track. The last minecart moved into the side track must be the first minecart to be moved back out: that is, the side track follows a last-in, first-out method. The side track can be used any number of times. Finally, once a minecart is moved to the right of the side track, it can no longer be moved to the left. Below is an example sequence of moves that can be made with \(5\) minecarts beginning from the initial position:

Steve has \(K\) spare gems, and he can distribute any number of them into the minecarts that are empty. Steve has yet to build the side track, and he wants to limit the side track capacity to save work. A side track with a specific capacity can only store up to that many minecarts. For example, if the side track had a capacity of \(1\), we would not be able to make the moves in the diagrams above, which would require a capacity of at least \(2\). Given that Steve places his spare gems into the minecarts optimally, what is the minimum capacity of the side track that needs to be built?

Input Specification

The first line of input will consist of two space-separated integers \(N\) and \(K\) \((1 \leq N \leq 3\times10^5,~ 0 \leq K \leq 10^{12})\).

The next line contains \(N\) integers \(a_1,\dots,a_n\) \((0\leq a_i\leq 10^6)\), where the \(i\)-th integer indicates the number of gems in the \(i\)-th minecart.

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

Output Specification

Output a single integer, the minimum capacity of the side track that needs to be built given that Steve distributes up to \(K\) gems among the empty minecarts optimally.

Sample Input 1

4 14 
5 0 4 0

Output for Sample Input 1

1

Explanation of Output for Sample Input 1

One optimal distribution is to put \(6\) of the spare gems into minecart \(2\) and \(7\) of the spare gems into minecart \(4\). Note that this distribution does not use all of the spare gems.

We can then build a side track of capacity \(1\). We can then arrange the minecarts in non-decreasing order as follows:

1. Move minecart \(4\) past the side track

2. Move minecart \(3\) into the side track

3. Move minecart \(2\) past the side track

4. Move minecart \(1\) past the side track

5. Move minecart \(3\) out of the side track

6. Move minecart \(3\) past the side track

Sample Input 2

4 8
5 0 4 0

Output for Sample Input 2

2

Explanation of Output for Sample Input 2

One optimal distribution is to put all \(8\) spare gems into minecart \(4\).

Then we can build a side track of capacity \(2\). We can then arrange the minecarts in non-decreasing order as follows:

1. Move minecart \(4\) past the side track

2. Move minecart \(3\) into the side track

3. Move minecart \(2\) into the side track

4. Move minecart \(1\) past the side track

5. Move minecart \(2\) out of the side track

6. Move minecart \(3\) out of the side track

7. Move minecart \(3\) past the side track

8. Move minecart \(2\) past the side track

Sample Input 3

4 123456789 
40 30 20 10

Output for Sample Input 3

3

Explanation of Output for Sample Input 3

Since there are no empty minecarts, there is only one possible distribution of spare gems: no spare gems are used at all.

Then we can build a side track of capacity \(3\). We can then arrange the minecarts in non-decreasing order as follows:

1. Move minecart \(4\) into the side track

2. Move minecart \(3\) into the side track

3. Move minecart \(2\) into the side track

4. Move minecart \(1\) past the side track

5. Move minecart \(2\) out of the side track and then past the side track

6. Move minecart \(3\) out of the side track and then past the side track

7. Move minecart \(4\) out of the side track and then past the side track

Problem S5: On the Fence

Problem Description

You recently inherited a beautiful plot of land, which can be viewed as a grid with \(N\) rows and \(M\) columns. Now you want to protect your land from trespassers by building a giant fence on it. You will build this fence by choosing up to \(K\) grid cells and filling each of them with a concrete block; these cells are on the fence. Due to mysterious construction laws, the cell in row \(R\) and column \(C\) must be on the fence. Also, the fence cells must form a single connected component—you should be able to get between any two cells on the fence by moving vertically or horizontally (not diagonally) through fence cells only.

The cells in row \(1\), column \(1\), row \(N\), and column \(M\) are called edge cells. A cell not on the fence is outside the fence if you can get from that cell to an edge cell by moving vertically, horizontally, or diagonally, without going through any fence cells. Otherwise, the cell is inside the fence. The figure below shows some examples of valid and invalid fences.

You want to protect as much of your land as possible. Find the largest number of inside cells you can enclose within your fence.

Input Specification

The first line of input contains an integer \(T\), the number of test cases in the input.

The next \(T\) lines each contain a test case, consisting of five space-separated integers: \(N\), \(M\), \(K\), \(R\), and \(C\) \((1 \le K \le NM,~ 1 \le R \le N,~ 1 \le C \le M)\).

The table on the next page shows how the available \(15\) marks are distributed.

Output Specification

Output \(T\) lines. The \(t\)-th line should contain a single integer, the answer to test case \(t\).

Sample Input

2
5 6 12 3 4
3 6 18 2 4

Output for Sample Input

4
3

Explanation of Output for Sample Input

Below are optimal fences for the two test cases, which enclose \(4\) and \(3\) inside cells, respectively: