2024 Canadian Computing Competition
Senior Problems

Problem S1: Hat Circle

Problem Description

At a recent social gathering, $N$ people sit around a circular table, where $N$ is even. The seats are numbered clockwise from $1$ to $N$. Each person is wearing a hat with a number on it. Specifically, the person at seat $i$ is wearing a hat with the number $H_i$ on it.

Each person looks at the person who is directly across (diametrically opposite) them in the circle.

Determine the number of people who see someone with a hat with the same number as their own.

Input Specification

The first line of input will consist of one even positive integer $N$, representing the number of people at the social gathering.

The next $N$ lines each contain a single non-negative integer $H_i$, representing the hat number of person $i$.

The following table shows how the available $15$ marks are distributed:

Output Specification

Output a single integer representing the number of people who see their hat number on the person directly across from them.

Sample Input 1

4
0
1
0
1 

Output for Sample Input 1

4

Explanation of Output for Sample Input 1

The four seats around the table are shown below. Hat numbers are shown inside each seat and seat numbers are shown beside each seat.

Notice that every person sees their hat number. The people in seats $1$ and $3$ both see hat number $0$, and the people in seats $2$ and $4$ both see hat number $1$.

Sample Input 2

4
1
0
0
1 

Output for Sample Input 2

0

Explanation of Output for Sample Input 2

The four seats around the table are shown below. Hat numbers are shown inside each seat and seat numbers are shown beside each seat.

Notice that no person sees their hat number. The people in seats $1$ and $4$ both see hat number $0$, and the people in seats $2$ and $3$ both see hat number $1$.

Problem S2: Heavy-Light Composition

Problem Description

In a string containing only lowercase letters of the alphabet ("a" through "z"), we say a letter is heavy if it appears more than once in the string, and light otherwise.

We will be given a number of strings. For each string, we would like to determine whether the letters of the string alternate between light and heavy.

Input Specification

The first line of input will consist of two positive integers $T$ and $N$, representing the number of strings and the length of each string.

The next $T$ lines each contain a sequence of $N$ lowercase letters of the alphabet.

The following table shows how the available $15$ marks are distributed:

Output Specification

Output $T$ lines, where each line will be either T or F. If the $i$-th input string does alternate between light and heavy letters, the $i$-th line of output should be T; and otherwise, the $i$-th line of output should be F.

Sample Input 1

3 4
abcb
bcbb
babc 

Output for Sample Input 1

T
F
T 

Explanation of Output for Sample Input 1

The first string is composed of a light letter, then a heavy letter, then a light letter, and then a heavy letter.

The second string ends in two consecutive heavy letters.

The third string is composed of a heavy letter, then a light letter, then a heavy letter, and then a light letter.

Sample Input 2

2 3
abc
bcb 

Output for Sample Input 2

F
T 

Explanation of Output for Sample Input 2

The first string is composed of all light letters.

The second string is composed of a heavy letter, then a light letter, and then a heavy letter.

Problem S3: Swipe

Problem Description

Swipe is a new mobile game that has recently exploded in popularity. In each level of Swipe, you are given $2$ rows of integers that can be represented as arrays $A$ and $B$ of size $N$. The objective of Swipe is to beat each level by turning array $A$ into array $B$.

There are two swipe operations you can perform on array $A$.

• Swipe right: Select the subarray $[\ell ,r]$ and set $A_i=A_{\ell }$ for all $\ell \le i\le r$.

• Swipe left: Select the subarray $[\ell ,r]$ and set $A_i=A_r$ for all $\ell \le i\le r$.

For example, starting with array $A=[0,1,2,3,4,5]$, if we swipe right on $[2,4]$, we would obtain the array $[0,1,2,2,2,5]$. If instead, we started with the same array $A$, and swiped left on $[3,5]$, we would obtain the array $[0,1,2,5,5,5]$. Note that these arrays are $0$-indexed.

Unfortunately, the game is bugged and contains levels that are impossible to beat. Determine if it is possible to transform array $A$ into array $B$. If it is possible, determine a sequence of swipe operations that transforms array $A$ into array $B$.

Input Specification

The first line of input will consist of one positive integer $N$, representing the length of each of the two arrays of integers.

The second line of input contains $N$ space separated integers contained in array $A$.

The third line of input contains $N$ space separated integers contained in array $B$.

The following table shows how the available $15$ marks are distributed:

Note that for a subtask worth $M$ marks, you will receive $\lfloor \frac{M}{2}\rfloor$ marks for a solution that only correctly outputs the first line of output.

Output Specification

The first line of output will contain YES if there is a sequence of swipes that can transform array $A$ into array $B$; otherwise, the first line of output will contain NO.

If the first line of output is YES, the next line contains a non-negative integer $K$ ($K\le N$), indicating the number of swipes.

Each of the next $K$ lines contain three space-separated values: $D_j$, ${\ell }_j$, and $r_j$. The value $D_j$ will be either R or L, indicating that the $j$th swipe is either a right or left swipe, respectively. The values ${\ell }_j$ and $r_j$ indicate the left-end and right-end of the swipe where $0\le {\ell }_j\le r_j<N$.

Sample Input 1

3
3 1 2
3 1 1

Output for Sample Input 1

YES
1
R 1 2

Sample Input 2

4
1 2 4 3
1 4 2 3 

Output for Sample Input 2

NO

Sample Input 3

4
2 1 4 3
2 1 4 3 

Output for Sample Input 3

YES
0

Problem S4: Painting Roads

Problem Description

Alanna, the mayor of Kitchener, has successfully improved the city’s road plan. However, a travelling salesperson from the city of RedBlue complained that the roads are not colourful enough. Alanna’s second job is to paint some of the roads.

Kitchener’s road plan can be represented as a collection of $N$ intersections with $M$ roads, where the $i$-th road connects intersections $u_i$ and $v_i$. All roads are initially grey. Alanna would like to paint some of the roads in red or blue such that the following condition is satisfied:

• Whenever there is a grey road that connects $u_i$ and $v_i$, there is also a path of roads from $u_i$ to $v_i$ such that the roads on the path alternate between red and blue, without any of the roads on this path being grey.

To lower the city’s annual spending, Alanna would like to minimize the number of painted roads. Can you help Alanna design a plan that meets all the requirements?

Input Specification

The first line contains two integers $N$ and $M$ $(1\le N,M\le 2\cdot {10}^5)$.

The $i$-th of the next $M$ lines contains two integers $u_i$ and $v_i$, meaning that there exists a road from intersection $u_i$ to intersection $v_i$ $(1\le u_i,v_i\le N,u_i\ne v_i)$.

There is at most one road between any unordered pair of intersections.

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

Definition: if we denote a road between intersections $u$ and $v$ as $u\leftrightarrow v$, then a simple cycle is a sequence $w_1\leftrightarrow w_2\leftrightarrow \dots \leftrightarrow w_k\leftrightarrow w_1$ where $k\ge 3$ and all $w_i$ are distinct.

Output Specification

Output a string of $M$ characters, representing the paint plan. The $i$-th character should be R if the $i$-th road is to be painted red, B if $i$-th road is to be painted blue, or G (for "grey") if the $i$-th road is to be left unpainted.

Remember that you must minimize the number of painted roads while satisfying the condition. If there are multiple possible such plans, output any of them.

Sample Input 1

5 7
1 2
2 4
5 2
4 5
4 3
1 3
1 4

Output for Sample Input 1

RGGRGRB

Explanation of Output for Sample Input 1

A diagram of the intersections along with a valid paint plan that minimizes the number of painted roads is shown below. Note that the colours are shown on each road as R (red), B (blue), or G (grey).

All the unpainted roads satisfy the condition:

• The $2$nd road, labelled G₂, connects intersection $2$ with intersection $4$. The path through intersections $2,1,4$ alternates red, blue.

• The $3$rd road, labelled G₃, connects intersection $5$ with intersection $2$. The path through intersections $5,4,1,2$ alternates red, blue, red.

• The $5$th road, labelled G₅, connects intersection $4$ with intersection $3$. The path through intersections $4,1,3$ alternates blue, red.

Sample Input 2

4 2
1 2
3 4

Output for Sample Input 2

BB

Explanation of Output for Sample Input 2

Note that it is possible for Kitchener to be disconnected.

Problem S5: Chocolate Bar Partition

Problem Description

Maxwell has a chocolate bar that he wants to share with his friends. The chocolate bar can be represented as a $2$ by $N$ array of integers $T_{i,j}$, the tastiness of each square. Maxwell would like to split the entire chocolate bar into connected parts such that the average (mean) tastiness of the chocolate bar is the same for each part. Maxwell would like to know what is the maximum number of connected parts he can split his chocolate bar into as described above.

A part is considered connected if you can visit every cell by moving up, down, left or right.

Input Specification

The first line of input will consist of one positive integer $N$, representing the length of the chocolate bar.

The second line of input contains $N$ spaced integers representing the top row of the chocolate bar where the $j$-th integer from the left represents $T_{1,j}$.

Similarly, the third line of input contains $N$ spaced integers representing the bottom row of the chocolate bar where the $j$-th integer from the left represents $T_{2,j}$.

The following table shows how the available $15$ marks are distributed:

Output Specification

Output a single integer, representing the maximum number of connected parts Maxwell can split his chocolate bar into.

Sample Input 1

2
5 4
6 5

Output for Sample Input 1

2

Explanation of Output for Sample Input 1

An example of how to split this chocolate bar optimally into $2$ parts is to have the bottom right corner as its own part and the rest of the chocolate as the second part, as shown below.

Each piece will have an average tastiness of $5$.

Sample Input 2

5
1 0 1 2 0
0 2 0 3 1  

Output for Sample Input 2

5

Explanation of Output for Sample Input 2

One way to get the optimal split is shown in the following picture:

Note that each piece has an average tastiness of $1$.