2020 Canadian Computing Competition
Senior Problems

Problem S1: Surmising a Sprinter’s Speed

Problem Description

Trick E. Dingo is trying, as usual, to catch his nemesis the Street Sprinter. His past attempts using magnets, traps and explosives have failed miserably, so he’s catching his breath to gather observational data and learn more about how fast Street Sprinter is.

Trick E. Dingo and Street Sprinter both inhabit a single straight west-east road with a particularly famous rock on it known affectionately as The Origin. Positions on this straight road are measured numerically according to the distance from The Origin, and using negative numbers for positions west of The Origin and positive numbers for positions east of The Origin.

The observations by Trick E. Dingo each contain two numbers: a time, and the value of Street Sprinter’s position on the road at that time. Given this information, what speed must Street Sprinter must be capable of?

Input Specification

The first line contains a number $2\le N\le 100000$, the number of observations that follow. The next $N$ lines each contain an integer $0\le T\le 1000000000$ indicating the time, in seconds, of when a measurement was made, and an integer $-1000000000\le X\le 1000000000$ indicating the position, in metres, of the Street Sprinter at that time. No two lines will have the same value of $T$.

For 7 of the 15 available marks, $N\le 1000$.

Output Specification

Output a single number $X$, such that we can conclude that Street Sprinter’s speed was at least $X$ metres/second at some point in time, and such that $X$ is as large as possible. If the correct answer is $C$, the grader will view $X$ as correct if $|X-C|/C<{10}^{-5}$.

Sample Input 1

3
0 100
20 50
10 120

Output for Sample Input 1

7.0

Explanation of Output for Sample Input 1

Since the Street Sprinter ran from position 100 to position 120 between time 0 and time 10, we know its speed must have been at least $2$ at some point in time: if it was always less than $2$, then the distance of 20 could not be covered in 10 seconds. Likewise, the speed must have been at least 7 in order to travel between position 120 and 50 in 10 seconds.

Sample Input 2

5
20 -5
0 -17
10 31
5 -3
30 11

Output for Sample Input 2

6.8

Problem J5/S2: Escape Room

Problem Description

You have to determine if it is possible to escape from a room. The room is an $M$-by-$N$ grid with each position (cell) containing a positive integer. The rows are numbered $1,2,\dots ,M$ and the columns are numbered $1,2,\dots ,N$. We use $(r,c)$ to refer to the cell in row $r$ and column $c$.

You start in the top-left corner at $(1,1)$ and exit from the bottom-right corner at $(M,N)$. If you are in a cell containing the value $x$, then you can jump to any cell $(a,b)$ satisfying $a\times b=x$. For example, if you are in a cell containing a $6$, you can jump to cell $(2,3)$.

Note that from a cell containing a $6$, there are up to four cells you can jump to: $(2,3)$, $(3,2)$, $(1,6)$, or $(6,1)$. If the room is a $5$-by-$6$ grid, there isn’t a row $6$ so only the first three jumps would be possible.

Input Specification

The first line of the input will be an integer $M$ $(1\le M\le 1000)$. The second line of the input will be an integer $N$ $(1\le N\le 1000)$. The remaining input gives the positive integers in the cells of the room with $M$ rows and $N$ columns. It consists of $M$ lines where each line contains $N$ positive integers, each less than or equal to $1000000$, separated by single spaces.

For 1 of the 15 available marks, $M=2$ and $N=2$.

For an additional 2 of the 15 available marks, $M=1$.

For an additional 4 of the 15 available marks, all of the integers in the cells will be unique.

For an additional 4 of the 15 available marks, $M\le 200$ and $N\le 200$.

Output Specification

Output yes if it is possible to escape from the room. Otherwise, output no.

Sample Input

3
4
3 10 8 14
1 11 12 12
6 2 3 9

Output for Sample Input

yes

Explanation of Output for Sample Input

Starting in the cell at $(1,1)$ which contains a $3$, one possibility is to jump to the cell at $(1,3)$. This cell contains an $8$ so from it, you could jump to the cell at $(2,4)$. This brings you to a cell containing $12$ from which you can jump to the exit at $(3,4)$. Note that another way to escape is to jump from the starting cell to the cell at $(3,1)$ to the cell at $(2,3)$ to the exit.

Notes

• The online grader begins by testing submissions using the sample input. All other tests are skipped if the sample test is not passed. If you are only attempting the first three subtasks (the first 7 marks), then you might want to handle the specific values of the sample input as a special case.

• For the final subtask (worth 2 marks), if you are using Java, then Scanner will probably take too long to read in the large amount of data. A much faster alternative is BufferedReader.

Problem S3: Searching for Strings

Problem Description

You’re given a string $N$, called the needle, and a string $H$, called the haystack, both of which contain only lowercase letters “a"..“z".

Write a program to count the number of distinct permutations of $N$ which appear as a substring of $H$ at least once. Note that $N$ can have anywhere between 1 and $|N|!$ distinct permutations in total – for example, the string “aab" has 3 distinct permutations (“aab", “aba", and “baa").

Input Specification

The first line contains $N$ $(1\le |N|\le 200000)$, the needle string.

The second line contains $H$ $(1\le |H|\le 200000)$, the haystack string.

For 3 of the 15 available marks, $|N|\le 8$ and $|H|\le 200$.

For an additional 2 of the 15 available marks, $|N|\le 200$ and $|H|\le 200$.

For an additional 2 of the 15 available marks, $|N|\le 2000$ and $|H|\le 2000$.

Output Specification

Output consists of one integer, the number of distinct permutations of $N$ which appear as a substring of $H$.

Sample Input

aab
abacabaa

Output for Sample Input

2

Explanation of Output for Sample Input

The permutations “aba" and “baa" each appear as substrings of $H$ (the former appears twice), while the permutation “aab" does not appear.

Problem S4: Swapping Seats

Problem Description

There are $N$ people sitting at a circular table for a long session of negotiations. Each person belongs to one of the three groups: A, B, or C. A group is happy if all of its members are sitting contiguously in a block of consecutive seats. You would like to make all groups happy by some sequence of swap operations. In each swap operation, two people exchange seats with each other. What is the minimum number of swaps required to make all groups happy?

Input Specification

The input consists of a single line containing $N$ $(1\le N\le 1000000)$ characters, where each character is A, B, or C. The $i$-th character denotes the group of the person initially sitting at the $i$-th seat at the table, where seats are numbered in clockwise order.

For 4 of the 15 available marks, the input has no C characters and $N\le 5000$.

For an additional 4 of the 15 available marks, the input has no C characters.

For an additional 4 of the 15 available marks, $N\le 5000$.

Output Specification

Output a single integer, the minimum possible number of swaps.

Sample Input

BABCBCACCA

Output for Sample Input

2

Explanation of Output for Sample Input

In one possible sequence, the first swap results in the seating layout AABCBCBCCA. After the second swap, the layout is AABBBCCCCA.

Problem S5: Josh’s Double Bacon Deluxe

Problem Description

On their way to the contest grounds, Josh, his coach, and his $N-2$ teammates decide to stop at a burger joint that offers $M$ distinct burger menu items. After ordering their favourite burgers, the team members line up, with the coach in the first position and Josh last, to pick up their burgers. Unfortunately, the coach forgot what he ordered. He picks a burger at random and walks away. The other team members, in sequence, pick up their favourite burger if available, or a random remaining burger if there are no more of their favourite burger. What is the probability that Josh, being last in line, will get to eat his favourite burger?

Input Specification

The first line contains the number $N$ $(3\le N\le 1000000)$, the total number of people and burgers. The next line contains $N$ numbers, the $i$-th being $b_i$ $(1\le b_i\le M\le 500000)$, denoting the item number of the $i$-th person’s favourite burger. The first person in line is the coach, and the $N$-th person is Josh.

For 4 of the 15 available marks, $N\le 100000$ and $M\le 1000$.

For an additional 5 of the 15 available marks, $M\le 5000$.

Output Specification

Output a single number $P$, the probability that Josh will get to eat his favourite burger, $b_N$. If the correct answer is $C$, the grader will view $P$ correct if $|P-C|<{10}^{-6}$.

Sample Input 1

3
1 2 3

Output for Sample Input 1

0.5

Explanation of Output for Sample Input

The coach randomly chooses between the three burgers. With probability $1/3$, he chooses his favourite burger (burger 1), and Josh gets to eat his favourite burger (burger 3). With probability $1/3$, he chooses Josh’s favourite burger, and Josh fails to eat his favourite burger. With probability $1/3$, he chooses the second person’s burger, there is a $1/2$ chance that the second person chooses Josh’s burger, denying Josh the pleasure of eating his favourite burger.

Sample Input 2

7
1 2 3 1 1 2 3

Output for Sample Input 2

0.57142857