2023 CCC Senior Problems

Bocchi the Builder just finished constructing her latest project: a laneway consisting of two rows of white equilateral triangular tiles. However, at the last moment, disaster struck! She accidentally spilled black paint on some of the tiles. Now, some of the tiles are wet and the other tiles are dry. Bocchi must place warning tape around the perimeters of all wet areas. Can you help her determine how many metres of tape she needs?

The first triangular tile will point upwards. Each pair of adjacent tiles (that is, tiles that share a common side) will point in opposite directions. Each tile has a side length of 1 metre.

Input Specification

The first line of input will consist of one positive integer

C

, representing the number of columns.

The next two lines will each consist of

C

integers separated by spaces. Each integer represents the colour of a tile along the laneway, with 1 indicating that the tile is black (wet) and 0 indicating that the tile is white (dry).

Marks	Description	Bound
3	The laneway is not very long, black tiles are never adjacent and the second row is fully white.	$C \leq 2 000$
3	The laneway is not very long, black tiles may be adjacent and the second row is fully white.	$C \leq 2 000$
5	The laneway is not very long, black tiles may be adjacent and may appear in the second row.	$C \leq 2 000$
4	The laneway may be very long, black tiles may be adjacent and may appear in the second row.	$C \leq 200 000$

Output Specification

Output a single integer representing the length of tape Bocchi needs, in metres.

Sample Input 1

Output for Sample Input 1

Explanation of Output for Sample Input 1

The tiles are painted as follows, creating three wet areas. Bocchi will need 9 metres of warning tape as shown in yellow.

Sample Input 2

Output for Sample Input 2

Explanation of Output for Sample Input 2

The tiles are painted as follows, creating three wet areas. Bocchi will need 5 metres of warning tape to surround one area and 3 metres of warning tape to surround each of the other two areas as shown in yellow.

Problem S2: Symmetric Mountains

Problem Description

Rebecca is a tour guide and is trying to market the Rocky Mountains for her magazine. She recently took a beautiful picture consisting of

N

mountains where the

i

-th mountain from the left has a height

h_{i}

. She will crop this picture for her magazine, by possibly removing some mountains from the left side of the picture and possibly removing some mountains from the right side of the picture. That is, a crop consists of consecutive mountains starting from the

l

-th to the

r

-th mountain where

l \leq r

. To please her magazine readers, Rebecca will try to find the most symmetric crop.

We will measure the asymmetric value of a crop as the sum of the absolute difference for every pair of mountains equidistant from the midpoint of the crop. To help understand that definition, note that the absolute value of a number

v

, written as

| v |

, is the non-negative value of

v

: for example

| - 6 | = 6

and

| 14 | = 14

. The asymmetric value of a crop is the sum of all

| h_{l + i} - h_{r - i} |

for

0 \leq i \leq \frac{r - l}{2}

. To put that formula in a different way, we pair up the mountains working from the outside in toward the centre, calculate the absolute difference in height of each of these pairs, and sum them up.

Because Rebecca does not know how wide the picture needs to be, for all possible crop lengths, find the asymmetric value of the most symmetric crop (the crop with the minimum asymmetric value).

Input Specification

The first line consists of an integer

N

, representing the number of mountains in the picture.
The second line consists of

N

space-separated integers, where the

i

-th integer from the left represents

h_{i}

Output Specification

Marks	Bounds on $N$	Bounds on $h_{i}$	Additional Constraints
5	$1 \leq N \leq 300$	$0 \leq h_{i} \leq 10^{5}$	None
5	$1 \leq N \leq 5000$	$0 \leq h_{i} \leq 10^{5}$	Height of mountains are in non-decreasing order from left to right.
5	$1 \leq N \leq 5000$	$0 \leq h_{i} \leq 10^{5}$	None

Output on one line

N

space-separated integers, where the

i

-th integer from the left is the asymmetric value of the most symmetric picture of crops of length

i

Sample Input 1

Output for Sample Input 1

Explanation of Output for Sample Input 1

We will show why the fifth value from the left is 2. Let us try to compute all the asymmetric values of crops with length 5.

The height of the mountains in the first crop is

[3, 1, 4, 1, 5]

. The asymmetric value of this crop is

| 3 - 5 | + | 1 - 1 | + | 4 - 4 | = 2

The height of the mountains in the second crop is

[1, 4, 1, 5, 9]

. The asymmetric value of this crop is

| 1 - 9 | + | 4 - 5 | + | 1 - 1 | = 9

The height of the mountains in the last crop is

[4, 1, 5, 9, 2]

. The asymmetric value of this crop is

| 4 - 2 | + | 1 - 9 | + | 5 - 5 | = 10

Sample Input 2

Output for Sample Input 2

Explanation of Output for Sample Input 2

This sample satisfies the second subtask. Note that the only crop of length 4 is

[1, 3, 5, 6]

which has asymmetric value of

| 1 - 6 | + | 3 - 5 | = 7

Problem S3: Palindromic Poster

Problem Description

Ryo and Kita are designing a new poster for Kessoku Band. After some furious brainstorming, they came to the conclusion that the poster should come in the form of a 2-D grid of lowercase English letters (i.e. a to z), with

N

rows and

M

columns.

Furthermore, it is known that Ryo and Kita both have peculiar tastes in palindromes. Ryo will only be satisfied with the poster if exactly

R

of its rows are palindromes, and Kita will only be satisfied with the poster if exactly

C

of its columns are palindromes. Can you design a poster that will satisfy both Ryo and Kita, or determine that it is impossible to do so?

Note: A string is considered a palindrome if it is the same when read forwards and backwards. For example, kayak and bb are palindromes, whereas guitar and live are not.

Input Specification

The first and only line of input consists of

4

space-separated integers

N

M

R

, and

C

Marks	Bounds on $N$	Bounds on $M$	Bounds on $R$	Bounds on $C$
2 marks	$2 \leq N \leq 2 000$	$2 \leq M \leq 2 000$	$R = 1$	$C = 1$
2 marks	$N = 2$	$M = 2$	$0 \leq R \leq N$	$0 \leq C \leq M$
4 marks	$N = 2$	$2 \leq M \leq 2 000$	$0 \leq R \leq N$	$0 \leq C \leq M$
7 marks	$2 \leq N \leq 2 000$	$2 \leq M \leq 2 000$	$0 \leq R \leq N$	$0 \leq C \leq M$

Output Specification

If it is impossible to design a poster that will satisfy both Ryo and Kita, output IMPOSSIBLE on a single line.

Otherwise, your output should contain

N

lines, each consisting of

M

lowercase English letters, representing your poster design. If there are multiple possible designs, output any of them.

Sample Input 1

Output for Sample Input 1

Explanation of Output for Sample Input 1

In the given design, only the second row (namely radar) and the second and third columns (namely naan and iddi) are palindromes. Since exactly

R = 1

of the rows and

C = 2

of the columns are palindromes, this is an acceptable design.

Sample Input 2

Output for Sample Input 2

Explanation of Output for Sample Input 2

In this case, it can be proven that it is impossible to satisfy both Ryo and Kita.

Problem S4: Minimum Cost Roads

Problem Description

As the newly elected mayor of Kitchener, Alanna’s first job is to improve the city’s road plan.

Kitchener’s current road plan can be represented as a collection of

N

intersections with

M

roads, where the

i

-th road has length

l_{i}

meters, costs

c_{i}

dollars per year to maintain, and connects intersections

u_{i}

and

v_{i}

. To create a plan, Alanna must select some subset of the

M

roads to keep and maintain, and that plan’s cost is the sum of maintenance costs of all roads in that subset.

To lower the city’s annual spending, Alanna would like to minimize the plan’s cost. However, the city also requires that she minimizes travel distances between intersections and will reject any plan that does not conform to those rules. Formally, for any pair of intersections

(i, j)

, if there exists a path from

i

j

taking

l

meters on the existing road plan, Alanna’s plan must also include a path between those intersections that is at most

l

meters.

Input Specification

Each of the next

M

lines contains the integers

u_{i}

v_{i}

l_{i}

, and

c_{i}

, meaning that there currently exists a road from intersection

u_{i}

to intersection

v_{i}

with length

l_{i}

and cost

c_{i}

(1 \leq u_{i}, v_{i} \leq N, u_{i} \neq v_{i})

Marks	Bounds on $N$ and $M$	Bounds on $l_{i}$	Bounds on $c_{i}$	Additional Constraints
$3$ marks	$1 \leq N, M \leq 2 000$	$l_{i} = 0$	$1 \leq c_{i} \leq 10^{9}$	None
$6$ marks	$1 \leq N, M \leq 2 000$	$1 \leq l_{i} \leq 10^{9}$	$1 \leq c_{i} \leq 10^{9}$	There is at most one road between any unordered pair of intersections.
$6$ marks	$1 \leq N, M \leq 2 000$	$0 \leq l_{i} \leq 10^{9}$	$1 \leq c_{i} \leq 10^{9}$	None

Output Specification

Output one integer, the minimum possible cost of a road plan that meets the requirements.

Sample Input

Output for Sample Input

Explanation of Output for Sample Input

Here is a diagram of the intersections along with a valid road plan with minimum cost.

Five circles are labelled 1, 2, 3, 4, and 5. The following pairs of circles are joined by lines, with each line labelled with a different ordered pair as indicated.

Circles 1 and 2; label $(15, 1)$
Circles 1 and 3; label $(2, 7)$
Circles 1 and 4; label $(2, 1)$
Circles 2 and 4; label $(9, 9)$
Circles 2 and 5; label $(5, 6)$
Circles 3 and 4; label $(3, 7)$
Circles 4 and 5; label $(4, 4)$

Each edge is labeled with a pair

(l, c)

denoting that it has length

l

meters and cost

c

dollars. Additionally, the roads that are part of the plan are highlighted in blue, with a total cost of

7 + 1 + 6 + 7 + 4 = 25

It can be shown that we cannot create a cheaper plan that also respects the city’s requirements.

Problem S5: The Filter

Problem Description

Alice, the mathematician, likes to study real numbers that are between 0 and 1. Her favourite tool is the filter.

A filter covers part of the number line. When a number reaches a filter, two events can happen. If a number is not covered by the filter, the number will pass through. If a number is covered, the number will be removed.

All three filters are on a number line from 0 to 1.

The first filter has two additional points marked between $0$ and $1$ creating three intervals of equal length.
The four marked points are labelled $\frac{0}{3}$ , $\frac{1}{3}$ , $\frac{2}{3}$ , and $\frac{3}{3}$ .
The filter covers one of the intervals: between $\frac{1}{3}$ and $\frac{2}{3}$ (2nd interval).

The second filter has eight points marked between $0$ and $1$ creating nine intervals of equal length.
The ten marked points are labelled $\frac{0}{9}$ , $\frac{1}{9}$ , $\frac{2}{9}$ , $\frac{3}{9}$ , $\frac{4}{9}$ , $\frac{5}{9}$ , $\frac{6}{9}$ , $\frac{7}{9}$ , $\frac{8}{9}$ , and $\frac{9}{9}$ .
The filter covers three of the intervals: between $\frac{1}{9}$ and $\frac{2}{9}$ (2nd interval), between $\frac{4}{9}$ and $\frac{5}{9}$ (5th interval), and between $\frac{7}{9}$ and $\frac{8}{9}$ (eighth interval).

The third filter has twenty-six points marked between $0$ and $1$ creating twenty-seven intervals of equal length.
The twenty-eight marked points are not labelled.
The filter covers nine of the intervals: 2nd, 5th, 8th, 11th, 14th, 17th, 20th, 23rd, and 26th intervals.

Alice has instructions for constructing the Cantor set. Start with the number line from 0 to 1. Apply all filters on the number line, and remove the numbers that are covered. The remaining numbers form the Cantor set.

Alice wants to research the Cantor set, and she came to you for help. Given an integer

N

, Alice would like to know which fractions

\frac{x}{N}

are in the Cantor set.

Input Specification

Output Specification

Marks	Bounds on $N$	Additional Constraints
3 marks	$3 \leq N \leq 3^{18}$	$N$ is a power of $3$
4 marks	$2 \leq N \leq 10^{5}$	None
8 marks	$2 \leq N \leq 10^{9}$	None

Output all integers

x

where

0 \leq x \leq N

and

\frac{x}{N}

is in the Cantor set.

Output the answers in increasing order. The number of answers will not exceed

10^{6}

Sample Input

Output for Sample Input

Explanation of Output for Sample Input

Here is a diagram of the fractions and the first 4 filters. In reality, there are infinitely many filters.

Thirteen equidistant points, $\frac{0}{12}$ , $\frac{1}{12}$ , $\frac{2}{12}$ , $\frac{3}{12}$ , $\frac{4}{12}$ , $\frac{5}{12}$ , $\frac{6}{12}$ , $\frac{7}{12}$ , $\frac{8}{12}$ , $\frac{9}{12}$ , $\frac{10}{12}$ , $\frac{12}{12}$ , and $\frac{11}{12}$ , are in a line at the top of the digram. A dashed vertical line is drawn down from each of these of these points. The filters are placed along four different horizontal lines, passing across these lines.

The first filter covers one interval: between $\frac{4}{12}$ and $\frac{8}{12}$ .
The second filter covers three intervals that are each one-third the length of the interval covered by the first filter. They are as follows:
- the first interval starts at a point one-third of the way from $\frac{1}{12}$ to $\frac{2}{12}$ and ends at a point two-thirds of the way from $\frac{2}{12}$ to $\frac{3}{12}$ ,
- the second interval starts at a point one-third of the way from $\frac{5}{12}$ to $\frac{6}{12}$ and ends at a point two-thirds of the way from $\frac{6}{12}$ to $\frac{7}{12}$ , and
- the third interval starts at a point one-third of the way from $\frac{9}{12}$ to $\frac{10}{12}$ and ends at a point two-thirds of the way from $\frac{10}{12}$ to $\frac{11}{12}$ .
The third filter covers nine intervals that are each one-third the length of the intervals covered by the second filter.
The fourth filter covers twenty-seven intervals that are each one-third the length of the intervals covered by the third filter.

\frac{5}{12}

\frac{6}{12}

, and

\frac{7}{12}

are not in the Cantor set because they were covered by the

1^{st}

filter.

Furthermore,

\frac{2}{12}

and

\frac{10}{12}

are not in the Cantor set because they were covered by the

2^{nd}

filter.

2023 Canadian Computing Competition Senior Problems

Problem J4/S1: Trianglane

Problem Description

Input Specification

Output Specification

Sample Input 1

Output for Sample Input 1

Explanation of Output for Sample Input 1

Sample Input 2

Output for Sample Input 2

Explanation of Output for Sample Input 2

Problem S2: Symmetric Mountains

Problem Description

Input Specification

Output Specification

Sample Input 1

Output for Sample Input 1

Explanation of Output for Sample Input 1

Sample Input 2

Output for Sample Input 2

Explanation of Output for Sample Input 2

Problem S3: Palindromic Poster

Problem Description

Input Specification

Output Specification

Sample Input 1

Output for Sample Input 1

Explanation of Output for Sample Input 1

Sample Input 2

Output for Sample Input 2

Explanation of Output for Sample Input 2

Problem S4: Minimum Cost Roads

Problem Description

Input Specification

Output Specification

Sample Input

Output for Sample Input

Explanation of Output for Sample Input

Problem S5: The Filter

Problem Description

Input Specification

Output Specification

Sample Input

Output for Sample Input

Explanation of Output for Sample Input

2023 Canadian Computing Competition
Senior Problems