2022 Canadian Computing Competition
Senior Problems

Problem S1: Good Fours and Good Fives

Problem Description

Finn loves Fours and Fives. In fact, he loves them so much that he wants to know the number of ways a number can be formed by using a sum of fours and fives, where the order of the fours and fives does not matter. If Finn wants to form the number $14$, there is one way to do this which is $14=4+5+5$. As another example, if Finn wants to form the number $20$, this can be done two ways, which are $20=4+4+4+4+4$ and $20=5+5+5+5$. As a final example, Finn can form the number 40 in three ways: $40=4+4+4+4+4+4+4+4+4+4$, $40=4+4+4+4+4+5+5+5+5$, and $40=5+5+5+5+5+5+5+5$.

Your task is to help Finn determine the number of ways that a number can be written as a sum of fours and fives.

Input Specification

The input consists of one line containing a number $N$.

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

Output Specification

Output the number of unordered sums of fours and fives which form the number $N$. Output 0 if there are no such sums of fours and fives.

Sample Input 1

14

Output for Sample Input 1

1

Explanation of Output for Sample Input 1

This is one of the examples in the problem description.

Sample Input 2

40

Output for Sample Input 2

3

Explanation of Output for Sample Input 2

This is one of the examples in the problem description.

Sample Input 3

6

Output for Sample Input 3

0

Explanation of Output for Sample Input 3

There is no way to use a sum of fours and fives to get $6$.

Problem J4/S2: Group Work

Problem Description

A class has been divided into groups of three. This division into groups might violate two types of constraints: some students must work together in the same group, and some students must work in separate groups.

Your job is to determine how many of the constraints are violated.

Input Specification

The first line will contain an integer $X$ with $X\ge 0$. The next $X$ lines will each consist of two different names, separated by a single space. These two students must be in the same group.

The next line will contain an integer $Y$ with $Y\ge 0$. The next $Y$ lines will each consist of two different names, separated by a single space. These two students must not be in the same group.

Among these $X+Y$ lines representing constraints, each possible pair of students appears at most once.

The next line will contain an integer $G$ with $G\ge 1$. The last $G$ lines will each consist of three different names, separated by single spaces. These three students have been placed in the same group.

Each name will consist of between 1 and 10 uppercase letters. No two students will have the same name and each name appearing in a constraint will appear in exactly one of the $G$ groups.

The following table shows how the available 15 marks are distributed at the Junior level.

The following table shows how the available 15 marks are distributed at the Senior level.

Output Specification

Output an integer between $0$ and $X+Y$ which is the number of constraints that are violated.

Sample Input 1

1
ELODIE CHI
0
2
DWAYNE BEN ANJALI
CHI FRANCOIS ELODIE

Output for Sample Input 1

0

Explanation of Output for Sample Input 1

There is only one constraint and it is not violated: ELODIE and CHI are in the same group.

Sample Input 2

3
A B
G L
J K
2
D F
D G
4
A C G
B D F
E H I
J K L

Output for Sample Input 2

3

Explanation of Output for Sample Input 2

The first constraint is that A and B must be in the same group. This is violated.

The second constraint is that G and L must be in the same group. This is violated.

The third constraint is that J and K must be in the same group. This is not violated.

The fourth constraint is that D and F must not be in the same group. This is violated.

The fifth constraint is that D and G must not be in the same group. This is not violated.

Of the five constraints, three are violated.

Problem S3: Good Samples

Problem Description

You are composing music for the Cool Clarinet Competition (CCC). You have been instructed to make a piece of music with exactly $N$ notes. A note is represented as a positive integer, indicating the pitch of the note.

We call a non-empty sequence of consecutive notes in the piece a sample. For instance, $(3,4,2)$, $(1,2,3,4,2)$ and $(4)$ are samples of $1,2,3,4,2$. Note that $(1,3)$ is not a sample of $1,2,3,4,2$. We call two samples different if they start or end at a different position in the piece.

We call a sample good if no two notes in the sample have the same pitch.

The clarinet players are picky in two ways. First, they will not play any note with pitch higher than $M$. Second, they want a piece with exactly $K$ good samples.

Can you construct a piece to satisfy the clarinet players?

Input Specification

The first and only line of input will contain $3$ space-separated integers, $N$, $M$ and $K$.

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

Output Specification

If there is a piece of music that satisfies the given constraints, output $N$ integers between $1$ and $M$, representing the pitches of the notes of the piece of music. If there is more than one such piece of music, any such piece of music may be outputted.

Otherwise, output $-1$.

Sample Input 1

3 2 5

Output for Sample Input 1

1 2 1

Explanation of Output for Sample Input 1

Notice that the piece is composed of $N=3$ notes, each of which is one of $M=2$ possible pitches, 1 and 2. That piece of music has a total of 6 samples, but only $K=5$ good samples: $(1)$, $(1,2)$, $(2)$, $(2,1)$, $(1)$. Notice that the two good samples of $(1)$ are different since they start at two different positions.

Note that the piece 2 1 2 is the only other valid output for this input.

One example of an output that would be incorrect is 3 2 3, since it has notes with pitches larger than 2. Another incorrect output would be 1 1 2, since it only has four good samples: $(1)$, $(1)$, $(2)$ and $(1,2)$.

Sample Input 2

5 5 14

Output for Sample Input 2

1 5 3 2 1

Explanation of Output for Sample Input 2

The 14 good samples are: $(1)$, $(1,5)$, $(1,5,3)$, $(1,5,3,2)$, $(5)$, $(5,3)$, $(5,3,2)$, $(5,3,2,1)$, $(3)$, $(3,2)$, $(3,2,1)$, $(2)$, $(2,1)$, $(1)$.

Sample Input 3

5 5 50

Output for Sample Input 3

-1

Explanation of Output for Sample Input 3

There are no pieces with 5 notes that can produce 50 different good samples.

Problem S4: Good Triplets

Problem Description

Andrew is a very curious student who drew a circle with the center at $(0,0)$ and an integer circumference of $C\ge 3$. The location of a point on the circle is the counter-clockwise arc length from the right-most point of the circle.

Andrew drew $N\ge 3$ points at integer locations. In particular, the $i$th point is drawn at location $P_i$ $(0\le P_i\le C-1)$. It is possible for Andrew to draw multiple points at the same location.

A good triplet is defined as a triplet $(a,b,c)$ that satisfies the following conditions:

• $1\le a<b<c\le N$.

• The origin $(0,0)$ lies strictly inside the triangle with vertices at $P_a$, $P_b$, and $P_c$. In particular, the origin is not on the triangle’s perimeter.

Lastly, two triplets $(a,b,c)$ and $(a^{\prime },b^{\prime },c^{\prime })$ are distinct if $a\ne a^{\prime }$, $b\ne b^{\prime }$, or $c\ne c^{\prime }$.

Andrew, being a curious student, wants to know the number of distinct good triplets. Please help him determine this number.

Input Specification

The first line contains the integers $N$ and $C$, separated by one space.

The second line contains $N$ space-separated integers. The $i$th integer is $P_i$ $(0\le P_i\le C-1)$.

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

Output Specification

Output the number of distinct good triplets.

Sample Input

8 10 
0 2 5 5 6 9 0 0

Output for Sample Input

6

Explanation of Output for Sample Input

Andrew drew the following diagram.

The origin lies strictly inside the triangle with vertices $P_1$, $P_2$, and $P_5$, so $(1,2,5)$ is a good triplet. The other five good triplets are $(2,3,6)$, $(2,4,6)$, $(2,5,6)$, $(2,5,7)$, and $(2,5,8)$.

Problem S5: Good Influencers

Problem Description

There are $N$ ($N\ge 2$) students in a computer science class, with distinct student IDs ranging from $1$ to $N$. There are $N-1$ friendships amongst the students, with the $i$th being between students $A_i$ and $B_i$ ($A_i\ne B_i$, $1\le A_i\le N$ and $1\le B_i\le N$). Each pair of students in the class are either friends or socially connected. A pair of students $a$ and $b$ are socially connected if there exists a set of students $m_1,m_2,\dots ,m_k$ such that

• $a$ and $m_1$ are friends,

• $m_i$ and $m_{i+1}$ are friends (for $1\le i\le k-1$), and

• $m_k$ and $b$ are friends.

Initially, each student $i$ either intends to write the CCC (if $P_i$ is Y) or does not intend to write the CCC (if $P_i$ is N). Initially, at least one student intends to write the CCC, and at least one student does not intend to write the CCC.

The CCC has allocated some funds to pay some students to be influencers for the CCC. The CCC will repeatedly choose one student $i$ who intends to write the CCC, pay them $C_i$ dollars, and ask them to deliver a seminar to all of their friends, and then all of their friends will intend to write the CCC.

Help the CCC determine the minimum cost required to have all of the students intend to write the CCC.

Input Specification

The first line contains the integer $N$.

The next $N-1$ lines each contain two space-separated integers, $A_i$ and $B_i$ ($1\le i\le N-1$).

The next line contains $N$ characters, $P_1\dots P_N$, each of which is either Y or N.

The next line contains $N$ space-separated integers, $C_1\dots C_N$.

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

Output Specification

Output the minimum integer number of dollars required to have all of the students to intend to write the CCC.

Sample Input 1

4 
1 2 
2 3 
3 4 
YNYN 
4 3 6 2

Output for Sample Input 1

6

Explanation of Output for Sample Input 1

The CCC should pay $6 to student 3 to deliver a seminar to their friends (students 2 and 4), after which all 4 students will intend to write the CCC.

Sample Input 2

15 
1 5 
5 2 
2 15 
15 4 
2 10 
8 3 
3 1 
1 6 
11 6 
12 6 
11 9 
11 14 
12 7 
13 7 
NNYYYNYYNNNNNNN 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Output for Sample Input 2

6

Explanation of Output for Sample Input 2

One optimal strategy is for the CCC to ask students 5, 1, 6, 11, 7, and 2 to deliver seminars, in that order, paying them $1 each.