2026 Canadian Informatics Workshop

Day 1, Problem 1: Shopping Mall

Time Limit: 3 seconds

Problem Description

It's Black Friday! Linx is at the mall with her friends, hoping to get some good deals. Linx has a shopping list of \(K\) items, labeled \(1\) to \(K\) that she wants to buy.

The mall contains \(N\) locations, each labeled with a number \(L_i\) from \(-1\) to \(K\).

• A location labeled \(i\) with \(1 \leq i \leq K\) is a shop that sells item \(i\).

• A location labeled \(0\) denotes an entrance to the mall.

• A location labeled \(-1\) is a shop that does not sell any of the \(K\) items that Linx wants.

The locations are connected by \(M\) bidirectional paths, each taking \(1\) unit of time to traverse, and it is guaranteed that there is a route between any two locations.

Since Linx is a bit of a perfectionist, she wants to purchase all \(K\) items in ascending order, from item \(1\) to item \(K\). The mall may have multiple entrances, which are all equally accessible from the bus stop, so Linx can start her shopping spree at any entrance (denoted by \(L_i = 0\)). She also doesn't mind visiting a shop more than once.

Input Specification

The first line of input contains three space-separated integers \(N\), \(M\), and \(K\) \((1 \leq N, M \leq 2 \times 10^5,\; 1 \leq K \leq 5)\).

The next line contains \(N\) space-separated integers, \(L_i\) \((-1 \leq L_i \leq K)\), indicating the label for each location. It is guaranteed that each number from \(0\) to \(K\) appears at least once.

The next \(M\) lines each contain two space-separated integers, \(A_i\) and \(B_i\) \((1 \leq A_i, B_i \leq 2 \times 10^5)\), indicating that there is a path between the \(A_i\)-th and \(B_i\)-th location, which takes 1 unit of time to traverse.

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

Output Specification

On a single line, output the least amount of time Linx must take to purchase all \(K\) items on her shopping list. It can be shown that this is always possible.

Sample Input 1

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

Output for Sample Input 1

4

Explanation of Output for Sample Input 1

Linx starts at the entrance at location \(1\). She then travels to location \(2\) and purchases item \(1\) there. Next, she travels to location \(3\) but does not purchase anything. Then, she travels to location \(4\) and purchases item \(2\) there. Finally, Linx returns to location \(3\) to purchase item \(3\). The total time taken is \(4\) units, following the location path \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 3\).

Sample Input 2

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

Output for Sample Input 2

4

Explanation of Output for Sample Input 2

An example of the shortest path that Linx can take is \(3 \rightarrow 7 \rightarrow 6 \rightarrow 7 \rightarrow 1\).
That is, Linx starts at the entrance at location \(3\). She then travels to location \(7\) and purchases item \(1\). Next, she travels to location \(6\) and purchases item \(2\). Then, she returns to location \(7\) but does not purchase anything. Finally, Linx travels to location \(1\) and purchases item \(3\).

Day 1, Problem 2: Number Shuffle

Time Limit: 2 seconds

Problem Description

For her sixteenth birthday, Beryl received a lovely gift from her grandmother: an \(N \times M\) grid of numbers. As per family tradition, she must now perform a sequence of \(Q\) operations on the grid. Each operation is one of the following:

1. Transpose the grid; i.e., swap its rows and columns so that the number in row \(i\), column \(j\) ends up in row \(j\), column \(i\). If the grid had \(n\) rows and \(m\) columns before this operation, it now has \(m\) rows and \(n\) columns.

2. Given an integer \(k\) that divides \(NM\), reshape the grid so that it has \(k\) rows and \(NM/k\) columns. The numbers in the grid are unchanged, and they stay in the same order when read row by row.

What does the grid look like after performing the sequence of operations?

Input Specification

The first line of input contains two space-separated integers, \(N\) and \(M\): the number of rows and columns of the grid, respectively.

The next \(N\) lines each contain \(M\) space-separated integers between \(1\) and \(10^9\) (inclusive); the \(i\)^th line represents the numbers in row \(i\) of the grid.

The next line contains a single integer, \(Q\).

The final \(Q\) lines each contain either the integer 1, denoting a transpose operation, or two space-separated integers 2 k, denoting a reshape operation.

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

Output Specification

Output two space-separated integers \(N'\) and \(M'\), the grid dimensions after performing all \(Q\) operations. Then output \(N'\) lines each containing \(M'\) space-separated integers; the \(i\)^th line should contain the numbers in row \(i\) of the final grid, in order.

Sample Input

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

Output for Sample Input

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

Explanation of Output for Sample Input

After the first operation (a transpose), the grid looks like this:

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

After the second operation (a reshape with \(6\) rows), it looks like this:

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

After the final operation (a transpose), it looks like this:

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

Day 2, Problem 1: Gumball Machine

Time Limit: 1 second

Problem Description

Morgan found a mysterious gumball machine under an old tarp in their attic. The machine has two buttons—one on the left and one on the right—and two counters labelled \(A\) and \(B\). Both counters start at zero. If Morgan presses the left button, counter \(A\) increases by one, and the machine dispenses \(B\) gumballs. If Morgan presses the right button, counter \(B\) increases by one, and the machine dispenses \(A\) gumballs. The machine may look small, but it contains a seemingly infinite number of gumballs and will never run out.

Using the fewest button presses, Morgan wants to get exactly \(N\) gumballs from the machine in total. Can you help them achieve this?

Input Specification

The first and only line of input contains a single integer, \(N~(0 \le N \le 10^9)\), the number of gumballs Morgan wants to get from the machine.

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

Output Specification

Output a single integer: the minimum number of button presses Morgan must perform to dispense exactly \(N\) gumballs from the machine, or \(-1\) if it is impossible to do so.

Sample Input

6

Output for Sample Input

5

Explanation of Output for Sample Input

Morgan presses the left button twice, setting \(A\) to \(2\) and dispensing no gumballs. Then they press the right button twice, setting \(B\) to \(2\) and dispensing \(4\) gumballs (\(2\) on each press). Finally, they press the left button once, setting \(A\) to \(3\) and dispensing \(2\) more gumballs for a total of \(6\). It is impossible to dispense exactly \(6\) gumballs in fewer than \(5\) presses.

Day 2, Problem 2: Videostore

Time Limit: 1 second

Problem Description

There will be \(N\) customers coming to visit your video store. Customer \(i\) will arrive at the start of the \(l_i\)-th minute and leave at the end of the \(r_i\)-th minute. You can also do \(M\) store tasks, labeled from \(1\) to \(M\). To complete any task, you must have already completed each task with a lower label. Each task takes \(K\) seconds to complete, must be worked on in one continuous interval, and can be completed at most once. You cannot serve customers when working on these tasks, and you cannot work on these tasks when serving customers.

By serving customer \(i\) during the entire duration of their visit, you get \(v_i\) coins. Note that multiple customers may visit the store at any time, and you can serve any number of customers simultaneously. By completing task \(i\), you get \(w_i\) coins.

You begin operating the store at the start of the 1st minute. Maximize the number of coins you can get by the end of the \(T\)-th minute.

Input Specification

The first line contains four integers \(N\), \(M\), \(T\), and \(K\) \((1 \le K \le T)\).

Each of the next \(N\) lines contains three integers \(l_i\), \(r_i\), and \(v_i\) \((1 \le l_i \le r_i \le T, 1 \le v_i \le 10^9)\).

The next line contains \(M\) integers \(w_1,\ldots,w_M\) \((1 \le w_i \le 10^9)\).

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

Output Specification

Output a single integer representing the maximum number of coins you can get by the end of the \(T\)-th minute.

Sample Input

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

Output for Sample Input

14

Explanation of Output for Sample Input

There are several possible ways to earn coins, such as serving customers \(1\) and \(2\) from the start of the 3rd minute to the end of the 5th minute for \(8+4=12\) coins or completing both tasks in \(6\) minutes for \(6+7=13\) coins. The maximum number of coins can be achieved by serving customer \(1\) from the start of the 3rd minute to the end of the 4th minute and then completing task \(1\) from the start of the 5th minute to the end of the 7th minute for \(8+6=14\) coins.