2022 Canadian Computing Olympiad

Day 1, Problem 1: Alternating Heights

Time Limit: 2 seconds

Problem Description

Troy is planning to take a group photo of the students at CCO and has asked you for help.

There are $K$ students, numbered from $1$ to $K$. Troy has forgotten the students’ heights, but remembers that no two students have the same height.

Troy has prepared a sequence $A_1,A_2,\dots ,A_N$ representing the order of students in the group photo, from left to right. It is possible for a student to appear multiple times in $A$. You aren’t sure how this group photo would be taken, but you’re unwilling to assume that Troy made a mistake.

Troy will ask you $Q$ queries of the form $x$ $y$, which is a compact way of asking "Given the sequence of students $A_x,A_{x+1},\dots ,A_y$, can their heights form an alternating sequence?" More precisely, we denote the height of the $i$th student as $h[i]$. If there exists an assignment of heights $h[1],h[2],\dots ,h[K]$ such that $h[A_x]>h[A_{x+1}]<h[A_{x+2}]>h[A_{x+3}]<\dots h[A_y]$, answer YES; otherwise answer NO.

Note that each of the $Q$ queries will be independent: that is, the assignment of heights for query $i$ is independent of the assignment of heights for query $j$ so long as $i\ne j$.

Input Specification

The first line of input will contain three space-separated integers $N$, $K$, and $Q$.

The second line of input will contain the array $A_1,A_2,\dots ,A_N$ $(1\le A_i\le K)$.

The next $Q$ lines will each contain a query of the form of two space-separated integers $x$ and $y$ $(1\le x<y\le N)$.

Output Specification

Output $Q$ lines. On the $i$th line, output the answer to Troy’s $i$th query. Note that the answer will be either YES or NO.

Sample Input

6 3 3
1 1 2 3 1 2
1 2
2 5
2 6

Output for Sample Input

NO
YES
NO

Explanation of Output for Sample Input

For the first query, we will never have $h[1]>h[1]$ so the answer is no.

For the second query, one solution to $h[1]>h[2]<h[3]>h[1]$ is $h[1]=160$cm, $h[2]=140$cm, $h[3]=180$cm. Another solution could be $h[1]=1.55$m, $h[2]=1.473$m, $h[3]=1.81$m.

For the third query, we cannot have both $h[1]>h[2]$ and $h[1]<h[2]$.

Day 1, Problem 2: Rainy Markets

Time Limit: 1.5 seconds

Problem Description

There are $N$ covered bus shelters, labelled $1,\dots ,N$. The $i$th bus shelter can fit $B_i$ people inside.

For each $i\in \{1,\dots ,N-1\}$, there is a sidewalk connecting bus shelter $i$ to bus shelter $i+1$, with an open-air market in the middle. The $i$th market has $U_i$ umbrellas for sale, each costing $1.

Right now, the $i$th market has $P_i$ people inside, and every person is in a market so all the bus shelters are empty.

Suddenly, it starts raining, and everyone at market $i$ has to decide between three possibilities:

• to go to bus shelter $i$;

• to go to bus shelter $i+1$; or

• to stay and buy an umbrella.

If a person is unable to find a place in a bus shelter or buy an umbrella, they will get wet.

If everyone coordinates optimally, can they all stay dry? If so, what is the least amount of money they need to spend, and which bus shelter should each person move to?

Input Specification

The first line of input contains $N$.

The second line of input contains $N$ space-separated integers $B_i$ ($1\le i\le N$), the capacity of bus shelter $i$.

The third line of input contains $N-1$ space-separated integers $P_i$ ($1\le i\le N-1$), the number of people at market $i$.

The fourth line of input contains $N-1$ space-separated integers $U_i$ ($1\le i\le N-1$), the number of umbrellas for sale at market $i$.

Output Specification

If every person can stay dry either under an umbrella or at a bus shelter, the output will be $N+1$ lines:

• the first line will contain the word YES.

• the second line will contain the least amount of money necessary to spend on umbrellas

• the next $N-1$ lines will each contain three space-separated integers:

  • the number of people at market $i$ moving to bus shelter $i$

  • the number of people at market $i$ buying an umbrella

  • the number of people at market $i$ moving to bus shelter $i+1$

  where $1\le i\le N-1$.

If not every person can stay dry, the output will be one line containing the word NO.

If there are multiple possible correct outputs, any correct output will be accepted.

Sample Input 1

3
10 15 10
20 20
0 0

Output for Sample Input 1

NO

Explanation of Output for Sample Input 1

There are 35 spots available at bus shelters and no umbrellas available, but there are 40 people in the markets.

Sample Input 2

3
10 15 10
20 20
0 11

Possible Output for Sample Input 2

YES
5
10 0 10
5 5 10

Explanation of Output for Sample Input 2

Looking at market 1, 10 people will go to bus shelter 1, no one will buy an umbrella, and 10 people will go to bus shelter 2.

Looking at market 2, 5 people will go to bus shelter 2, 5 people will stay and buy an umbrella, and 10 people will move to bus shelter 3.

In total, 5 umbrellas were purchased, which costs $5.

Day 1, Problem 3: Double Attendance

Time Limit: 3 seconds

Problem Description

Due to a rather ambitious school schedule, two of your classes are about to be held starting at exactly the same time, in two different classrooms! You can only be in one place at a time, so the best you can hope for is catching the important bits of both, even if that means sneaking back and forth between the two.

The two classrooms are numbered $1$ and $2$. In classroom $i$, the teacher will show $N_i$ different slides during the class, with the $j$th slide shown throughout the exclusive time interval $(A_{i,j},B_{i,j})$ ($0\le A_{i,j}<B_{i,j}$) where $A_{i,j}$ and $B_{i,j}$ are times elapsed since the start of class measured in seconds. In both classes, there does not exist a point in time at which multiple slides are simultaneously being shown. For example, a class may have slides spanning the pair of intervals $(1,2)$ and $(5,6)$, or the pair $(10,20)$ and $(20,30)$, but not the pair $(10,20)$ and $(19,30)$.

You begin the day in classroom 1 with both classes starting at time 0. Following that, at any point in time (not necessarily after an integral number of seconds), you may move from your current classroom to the other one in $K$ seconds. You consider yourself to have seen a slide if you spend a positive amount of time in its classroom strictly within the time interval during which it’s being shown. When moving between the two classrooms, you’re not considered to be inside either of them for $K$ seconds, and are thus unable to see any slides.

For example, if classroom $1$ has a slide being shown for the time interval $(10,20)$, classroom $2$ has a slide being shown for the time interval $(15,25)$, and $K=8$, then you’ll get to see both slides if you move from classroom $1$ to classroom $2$ at time $11.5$ seconds (arriving at time $19.5$ seconds). On the other hand, if you leave classroom $1$ at time $17$ seconds (arriving at time $25$ seconds), then you’ll enter classroom $2$ just after its slide stops being shown and will therefore miss it.

What’s the maximum number of distinct slides which you can see at least once?

Input Specification

The first line contains three space-separated integers, $N_1$, $N_2$, and $K$.

The next $N_1$ lines each contain two space-separated integers $A_{1,i}$ and $B_{1,i}$ ($1\le i\le N_1$).

The next $N_2$ lines each contain two space-separated integers, $A_{2,i}$ and $B_{2,i}$ ($1\le i\le N_2$).

Output Specification

Output one integer which is the maximum number of distinct slides which you can see.

Sample Input 1

3 1 8 
10 20 
100 101 
20 21 
15 25

Output for Sample Input 1

3

Explanation of Output for Sample Input 1

One possible optimal strategy is to remain in classroom $1$ until time $11.5$, then move to classroom $2$ (arriving at time $19.5$), remain there until time $19.6$, and finally return to classroom $1$ (arriving at time $27.6$). In the process, you’ll see all but the 3rd slide. It’s impossible for you to see all 4 slides.

Sample Input 2

1 5 3 
1 100 
1 2 
2 3 
3 4 
4 5 
5 6

Output for Sample Input 2

4

Explanation of Output for Sample Input 2

Even if you begin moving to classroom $2$ immediately at the start of the classes, (e.g., at time $0.0001$), you’ll miss the first 2 slides shown there. As such, it is possible to see a total of at most four slides.

Day 2, Problem 1: Bi-ing Lottery Treekets

Time Limit: 1 second

Problem Description

In a parallel universe, everyone scored perfect on the CCO. As a result, Troy needs to pick the winner based on a lottery. Each contestant will choose numbers to create a ticket. A ticket is an array of size $N$ indexed from $1$ to $N$ where each entry is a number from $0$ to $K$.

The winning ticket is determined by dropping $K$ balls (numbered from $1$ to $K$) in a random sequence into a rooted binary tree. The tree has $N$ nodes (numbered from $1$ to $N$) and is rooted at node 1.

Each ball has a designated drop node that it will drop at. When a ball is dropped at an unoccupied node or enters an unoccupied node, one of three things happens:

1. If all of the current node’s children are occupied by balls (or if a node has no children), the current ball rests at the current node. That is, it remains there and does not move again.

2. If the current node only has one unoccupied child, the current ball will move to this child.

3. If the current node has two unoccupied children, and if the current ball was just dropped, it could go either left or right. Otherwise, it will continue in the direction of its previous movement.

If all $K$ balls cannot be dropped, a winning ticket is not determined. This happens when a ball is dropped and its drop node is occupied by another ball.

If all $K$ balls have been dropped, the balls’ resting positions determine the winning lottery ticket. The $i$th entry of the winning lottery ticket is the number of the ball that rests at node $i$ or $0$ if no ball rests at node $i$.

Troy would like to know the number of possible winning tickets (which could be zero).

Input Specification

The first line contains two space-separated integers $N$ and $K$, denoting the number of nodes in the binary tree and the number of balls, respectively.

The next line contains $K$ space-separated integers, where the $i$th integer denotes the designated drop node of the ball numbered $i$.

The last $N$ lines each contain two space-separated integers. The $i$th line contains $L_i$ and $R_i$ denoting the $i$th node’s left and right child, respectively, where $0$ means no such child exists.

Output Specification

Output the remainder of the number of winning lottery tickets divided by ${10}^9+7$.

Sample Input 1

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

Output for Sample Input 1

4

Explanation of Output for Sample Input 1

The tree looks like this:

Consider when ball 1 is dropped first. If ball 1 goes left, then it will rest at node 2. Afterward, ball 2 is dropped and can rest at node 4 or 5. If ball 1 goes right, it will rest at node 5. Then, ball 2 will rest at node 4.

Consider when ball 2 is dropped first. Ball 2 can go left or right, resting at nodes 4 or 5, respectively. Then if ball 1 moves left after being dropped, it will rest at node 2. However, if ball 1 moves right, it will rest at either node 4 or 5, whichever place ball 2 does not occupy.

The possible winning tickets are $[0,1,0,2,0]$, $[0,1,0,0,2]$, $[0,0,0,1,2]$, and $[0,0,0,2,1]$.

Sample Input 2

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

Output for Sample Input 2

2

Explanation of Output for Sample Input 2

The tree looks like this:

This test case satisfies the second subtask.

Ball 3 must be dropped first because if either ball 1 or ball 2 are dropped before ball 3, it would rest at node 4, which wouldn’t allow ball 3 to be dropped.

Thus, we can either first drop ball 3, then ball 2 and finally ball 1 or we can first drop ball 3, then ball 1 and finally ball 2.

The possible winning tickets are $[0,1,2,3]$ and $[0,2,1,3]$.

Formal Definitions

A binary tree is a set of nodes that is either empty, or a root node with a left subtree and a right subtree both of which are binary trees. Given a node $x$, if its left subtree is not empty, then the root of that subtree is called the left child of $x$. Similarly, given a node $x$, if its right subtree is not empty, then the root of that subtree is called the right child of $x$.

Day 2, Problem 2: Phone Plans

Time Limit: 3 seconds

Problem Description

The mayor of CCOland, Jason, wants to install telephone lines amongst $N$ households, which are numbered from $1$ to $N$. To do so, he has asked two rivalling companies, Keenan Mobile Phones and Chris Home Telephone, for their phone plans. A phone plan for a company corresponds to a certain level and every telephone line has a level and company associated with it. If you have purchased a phone plan from a company with level $l$, then you are able to use all the telephone lines whose level is less than or equal to $l$ that is associated with that company. A phone plan of level $l$ costs $\mathrm{\$}l$ and you cannot pick a phone plan of less than $\mathrm{\$}0$.

Two households can only communicate with each other if they are connected by a path of telephone lines of the same company. Jason would like to buy one phone plan from each company of minimal cost such that there are at least $K$ different pairs of households that can communicate with each other.

Input Specification

The first line contains four space-separated integers $N$, $A$, $B$ and $K$, which represent the number of households, number of telephone lines from Keenan Mobile Phones, number of telephone lines from Chris Home Telephone and the minimum pairs of homes that need to be able to communicate with each other, respectively.

The next $A$ lines each contain three space-separated integers $u$, $v$ and $l$, which represents a Keenan Mobile Phones telephone line between household $u$ and $v$ $(1\le u,v\le N)$ that has a level $l$ $(1\le l\le {10}^9)$.

The next $B$ lines have the same format as the previous $A$ lines but for Chris Home Telephone.

Output Specification

Output the cheapest cost needed to connect at least $K$ different pairs of households or $-1$ if it is not possible.

Sample Input

6 4 4 9 
1 2 1 
2 3 2 
1 4 3 
3 4 4 
5 6 40 
1 5 30 
2 6 20 
3 6 10

Output for Sample Input

33

Explanation of Output for Sample Input

For each company, consider these pictures of the way the 6 households are connected by telephone lines:

If Jason buys phone plan level $3$ from Keenan Mobile Phones and phone plan level $30$ from Chris Home Telephone, then $(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$ can communicate through Keenan Mobile Phones’s lines and $(1,5),(2,6),(3,6),(2,3)$ can communicate through Chris Home Telephone’s lines. There are no cheaper ways.

Day 2, Problem 3: Good Game

Time Limit: 1 second

Problem Description

Finn is playing a game of Twos and Threes. Twos and Threes is a one-player game played on a one-dimensional board. In the starting position, there are $N$ blocks arranged in a row, with each block labelled either $A$ or $B$. Blocks are numbered from $1$ to $N$ from left to right. Finn is allowed to make moves of the following form:

• Select $2$ or $3$ consecutive blocks that share the same label. Remove them from the board. Connect any remaining blocks together. Re-index the blocks from left to right starting with index 1.

Finn wins the game if all blocks are removed from the board. Your task is to help Finn determine a winning sequence of moves, or determine if the game cannot be won.

Input Specification

The first line of input will contain the integer $N$.

The second line of input will contain the string $S$ which is the starting position of the game. There are $N$ characters in $S$, and each of these characters in $S$ is either $A$ or $B$.

Output Specification

If there is a winning sequence of moves, output $K$, the number of moves in the winning sequence. On each of the next $K$ lines, print an index $i$, followed by one space, followed by a number $j$, denoting a move that will remove the blocks currently at indices $i$ to $i+j-1$, inclusive.

If there is no winning sequence of moves, output $-1$.

If there are multiple winning sequences, then any winning sequence will be accepted. There is no need to minimize or maximize $K$.

Sample Input

9
ABAABBBAA

Possible Output for Sample Input

4 
6 2 
3 2 
2 2 
1 3

Explanation of Output for Sample Input

The sample output denotes this winning sequence:

ABAABBBAA
ABAABAA
ABBAA
AAA