2025 Canadian Computing Competition
Senior Problems

Problem S1: Positioning Peter's Paintings

Problem Description

Peter the painter just finished painting two rectangular paintings and would like to display both on a rectangular wall which has the smallest perimeter possible. The first painting has a base of length \(A\) units and a height of length \(B\) units. The second painting has a base of length \(X\) units and a height of length \(Y\) units.

Peter has a few conditions on how to arrange his paintings on the rectangular wall. The first condition is that the paintings must be upright, meaning that the bases of the paintings are parallel to the floor. The second condition is that he would like to display both paintings in full, meaning that they cannot overlap each other. Please help determine the rectangular wall of minimum perimeter such that the paintings can be displayed without violating his conditions.

Input Specification

The one line of input will consist of four space-separated positive integers, \(A\), \(B\), \(X\), \(Y\) \((1 \le A, B, X, Y \le 10^8)\).

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

Output Specification

Output a single integer representing the minimum perimeter of a rectangular wall without violating Peter's conditions.

Sample Input 1

3 3 3 3

Output for Sample Input 1

18

Explanation of Output for Sample Input 1

This test case satisfies all subtasks. An optimal arrangement using a 6-by-3 wall is shown below.

Sample Input 2

2 2 4 4

Output for Sample Input 2

20

Explanation of Output for Sample Input 2

This test case satisfies the second and third subtasks. An optimal arrangement using a 6-by-4 wall is shown below.

Sample Input 3

1 2 3 1

Output for Sample Input 3

12

Explanation of Output for Sample Input 3

This test case satisfies the last subtask. An optimal arrangement using a 3-by-3 wall is shown below.

Problem S2: Cryptogram Cracking Club

Problem Description

Cyrene, the captain of the Cryptogram Cracking Club (CCC), came across a concerningly long cipher. Conveniently, this cipher is composed of lower-case characters (a-z). Comfortingly, the cipher is composed of a pattern that repeats infinitely.

Cyrene wishes to locate the \(c\)-th character of the cipher. To make your job easier, the CCC members have extracted the repeated pattern and compressed it using the Run-Length Encoding (RLE) algorithm, which replaces consecutive repeated characters with a single occurrence of the character followed by a count of how many times it was repeated. For example, for the pattern aaaabccdddd, the RLE algorithm outputs a4b1c2d4.

You are given the output of the RLE algorithm for a certain pattern. Can you determine the \(c\)-th character of the long cipher that is formed by repeating this pattern infinitely?

Input Specification

The first line of input will consist of a string \(S\), representing a pattern produced by the RLE algorithm. The length of \(S\) will be at least \(2\) and at most \(2\cdot 10^5\). Additionally, all numbers appearing in \(S\) are between \(1\) and \(10^{12}\).

The next line of input contains a single integer \(c\), representing the index of the character you wish to locate, starting from index \(0\).

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

Output Specification

Output the \(c\)-th character of the long cipher.

Sample Input 1

r2d2
8

Output for Sample Input 1

r

Explanation of Output for Sample Input 1

The output of the RLE algorithm r2d2 corresponds to the pattern rrdd, which creates the infinitely long cipher rrddrrddrrddrrdd..., where the \(c = 8\)th character is r.

Sample Input 2

a4b1c2d10
100

Output for Sample Input 2

d

Explanation of Output for Sample Input 2

The output of the RLE algorithm a4b1c2d10 corresponds to the pattern aaaabccdddddddddd. When repeated infinitely, the \(c = 100\)th character is d.

Problem S3: Pretty Pens

Problem Description

You are taking an art class, and your current art assignment is very algorithmic.

You have \(N\) pens, each of which has a single colour, represented by an integer from \(1\) to \(M\). Initially, the colour of the \(i\)-th pen is given by \(C_i\). In addition, your pens are pretty, with the \(i\)-th pen having a prettiness of \(P_i\).

For your assignment, you need to create a picture using \(M\) strokes, each from a pen of a different colour. The prettiness of your picture is the sum of the prettiness of the pens used to create the picture.

Your teacher has given you some room for artistic expression: before you create this pretty picture, you are allowed to change at most one pen to any other colour. After this picture is drawn, the pen will revert back to its original colour.

Your teacher will give you \(\frac{1}{3}\) of the marks (\(5\) of \(15\) total marks) for the art assignment based on creating the prettiest picture you can.

To push your creative limits, your teacher also has \(Q\) more pictures for you to create, which compose the remaining \(\frac{2}{3}\) of the marks (\(10\) of \(15\) total marks) for your art assignment. Before each picture, there will be one of two possible changes to the set of pens available:

• 1 i c indicates that the colour of the \(i\)-th pen changes to \(c\).

• 2 i p indicates that the prettiness of the \(i\)-th pen changes to \(p\).

The changes are executed sequentially (so the first change modifies the initial setup, the second change modifies the result of applying the first change, and so on).

As in the first picture you created, you are allowed to change the colour of at most one pen before the picture is created. Note that if you do change the colour of one pen, it affects only the next picture you draw, and the pen will revert to its previous colour before the next change is applied (if any).

What is the prettiness of the prettiest \(Q+1\) pictures you can create?

Input Specification

The first line of input contains three space-separated integers \(N\), \(M\), \(Q\) \((1 \leq M \leq N \leq 200\ 000\), \(0 \leq Q \leq 200\ 000)\).

The next \(N\) lines each contain two space-separated integers, \(C_i\) and \(P_i\) \((1 \le C_i \le M, 1 \le P_i \le 10^9)\), indicating the colour and prettiness of the \(i\)-th pen.

The next \(Q\) lines each contain three space-separated integers, beginning with \(1\) or \(2\). If the first integer is \(1\), it is followed by two integers \(i_j\) and \(c_j\) \((1 \le i_j \le N, 1 \le c_j \le M)\), representing a change of the colour of the \(i_j\)-th pen to \(c_j\). If the first integer is \(2\), it is followed by two integers \(i_j\) and \(p_j\) \((1 \le i_j \le N, 1 \le p_j \le 10^9)\), representing a change of the prettiness of the \(i_j\)-th pen to \(p_j\).

It is guaranteed that initially and after each change, there is at least one pen with each of the \(M\) colours.

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

Output Specification

The output is \(Q+1\) lines, with the \(j\)-th line containing one integer, the largest possible prettiness value obtainable after the first \(j-1\) changes have been performed.

Sample Input 1

6 3 0
1 6
2 9
3 4
2 7
3 9
1 3

Output for Sample Input 1

25

Explanation of Output for Sample Input 1

There are six pens available in three different colours. The set of pens is:

• two pens of colour \(1\), with prettiness \(6\) and \(3\),

• two pens of colour \(2\), with prettiness \(9\) and \(7\),

• two pens of colour \(3\), with prettiness \(4\) and \(9\).

If we do not change the colour of any pens, the prettiest picture has prettiness \(6+9+9=24\). However, if we change the colour of pen \(4\) from colour \(2\) to colour \(1\), we can create a picture with prettiness \(7+9+9=25\), which is the prettiest picture that can be created.

Sample Input 2

3 2 2
1 20
2 30
1 10
1 3 2
2 3 25

Output for Sample Input 2

50
50
55

Explanation of Output for Sample Input 2

There are three pens with two different colours available.

Before the first change, using pen \(1\) and pen \(2\), with colours \(1\) and \(2\), respectively, achieves a prettiness of \(20+30=50\).

After the first change, pen \(3\) has colour \(2\). There is no alteration in the maximum prettiness, even if we could switch one pen: picking pens \(1\) and \(2\) will yield the maximum prettiness.

After the second change, pen \(3\) will have colour \(2\) and prettiness \(25\). Before the final picture is created, we can change the colour of pen \(2\) to colour \(1\), and use pens \(2\) and \(3\) to achieve the maximum prettiness of \(30+25=55\).

Problem S4: Floor is Lava

Problem Description

You're trapped in a scorching dungeon with \(N\) rooms numbered from \(1\) to \(N\) connected by \(M\) tunnels. The \(i\)-th tunnel connects rooms \(a_i\) and \(b_i\) in both directions, but the floor of the tunnel is covered in lava with temperature \(c_i\).

To help you navigate the lavatic tunnels, you are wearing a pair of heat-resistant boots that initially have a chilling level of \(0\). In order to step through lava with temperature \(\ell\), your boots must have the same chilling level \(\ell\); if the chilling level is too low then the lava will melt your boots, and if it's too high then your feet will freeze as you cross the tunnel.

Luckily, when you're standing in a room, you can increase or decrease the chilling level of your boots by \(d\) for a cost of \(d\) coins. You start in room \(1\) and would like to reach the exit which you know is located in room \(N\). What is the minimum cost to do so?

Input Specification

The first line of input contains two integers \(N\) and \(M\) \((1 \le N, M \le 200\,000)\).

The next \(M\) lines each contain three integers \(a_i\), \(b_i\), and \(c_i\) \((1 \le a_i, b_i \le N, a_i \neq b_i, 1 \le c_i \le 10^9)\), describing the \(i\)-th tunnel.

There is at most one tunnel connecting any pair of rooms, and it is possible to reach all other rooms from room \(1\).

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

Output Specification

Output the minimum cost (in coins) to reach room \(N\) from room \(1\).

Sample Input

5 7
1 2 3
2 3 2
1 3 6
3 4 3
4 5 7
2 4 1
2 5 10

Output for Sample Input

9

Explanation of Output for Sample Input

A diagram of the dungeon is shown below.

The optimal escape strategy is as follows:

1. Increase the chilling level to \(3\) for a cost of \(3\) coins.

2. Walk through the tunnel to room \(2\).

3. Decrease the chilling level to \(2\) for a cost of \(1\) coin.

4. Walk through the tunnel to room \(3\).

5. Increase the chilling level to \(3\) for a cost of \(1\) coin.

6. Walk through the tunnel to room \(4\).

7. Increase the chilling level to \(7\) for a cost of \(4\) coins.

8. Walk through the tunnel to room \(5\) and escape.

This has a total cost of \(9\) coins, and it can be shown that no cheaper route exists.

Problem S5: To-Do List

Problem Description

Wow, your to-do list is empty...but not for long! Over the next few seconds, you'll have to handle \(Q\) updates to your to-do list.

For the first type of update, you will have to add a new homework assignment to your to-do list. This assignment will be released at the beginning of second \(s\), and will take \(t\) seconds to complete \((1 \le s, t \le 10^6)\). For the second type of update, you will have to remove the \(i\)-th homework assignment that was added to your to-do list.

After each update, you wonder: what's the earliest time you can finish all of the homework assignments in your to-do list? You can only work on one assignment at a time, and you must finish a homework assignment once you start it without switching to another assignment.

Input Specification

The first line of input contains an integer \(Q\).

The next \(Q\) lines each contain a line starting with a character A or D. A line starting with A represents the first type of update and ends with two space-separated encrypted^* integers \(s'\) and \(t'\). A line starting with D represents the second type of update and ends with an encrypted integer \(i'\). It is guaranteed that there have been at least \(i\) assignments added and that the \(i\)-th assignment to be added has not been removed yet.

It is guaranteed that there is at least one homework assignment on your to-do list after every update.

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

*Note that the input for this problem is encrypted. To decrypt and obtain the actual values of \(s, t,\) and \(i\), you may use the following formulas: \[ \begin{align*} s & = (s' + \text{ans}) \bmod (10^6+3)\\ t & = (t' + \text{ans}) \bmod (10^6+3)\\ i & = (i' + \text{ans}) \bmod (10^6+3) \end{align*} \] Here, \(\text{ans}\) represents the answer after the previous update and is initially \(0\) before any updates. It may also be useful to note that mod corresponds to the % operator in most programming languages, indicating the remainder after division. For example, \(5\bmod 3 = 2\) and \(17\bmod 4 = 1\).

Output Specification

Output \(Q\) lines, where the \(i\)-th line contains the earliest time (in seconds) you can finish all of the homework assignments in your to-do list after the \(i\)-th update.

Sample Input 1

6
A 3 3
A 2 0
A 999996 999995
D 999991
A 1000000 999994
D 999992

Sample Input 1 (Unencrypted)

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

Output for Sample Input 1

5
11
13
11
13
9

Explanation of Output for Sample Input 1

The unencrypted sample input is provided for ease of reference.

After the first update, we can start the first assignment at the beginning of second \(3\) and finish at the end of second \(5\) (interval \([3, 5]\)).

After the second update, we can do the first assignment over the interval \([3, 5]\) and the second assignment over the interval \([7, 11]\).

After the third update, we can do the first assignment over the interval \([3, 5]\), the third assignment over the interval \([6, 8]\), and then the second assignment over the interval \([9, 13]\).

After the fourth update, we can do the third assignment over the interval \([4, 6]\) and the second assignment over the interval \([7, 11]\).

After the fifth update, we can do the third assignment over the interval \([4, 6]\), the second assignment over the interval \([7, 11]\), and the fourth assignment over the interval \([12, 13]\).

After the sixth update, we can do the third assignment over the interval \([4, 6]\) and the fourth assignment over the interval \([8, 9]\).

Sample Input 2

2
A 1000000 1000000
A 4 4

Sample Input 2 (Unencrypted)

2
A 1000000 1000000
A 1000000 1000000

Output for Sample Input 2

1999999
2999999