2018 Canadian Computing Competition
Senior Problems

Problem S1: Voronoi Villages

Problem Description

In the country of Voronoi, there are $N$ villages, located at distinct points on a straight road. Each of these villages will be represented by an integer position along this road.

Each village defines its neighbourhood as all points along the road which are closer to it than to any other village. A point which is equally close to two distinct villages $A$ and $B$ is in the neighbourhood of $A$ and also in the neighbourhood of $B$.

Each neighbourhood has a size which is the difference between the minimum (leftmost) point in its neighbourhood and the maximum (rightmost) point in its neighbourhood.

The neighbourhoods of the leftmost and rightmost villages are defined to be of infinite size, while all other neighbourhoods are finite in size.

Determine the smallest size of any of the neighbourhoods (with exactly 1 digit after the decimal point).

Input Specification

The first line will contain the number $N$ $(3\le N\le 100)$, the number of villages. On the next $N$ lines there will be one integer per line, where the $i$th line contains the integer $V_i$, the position of the $i$th village $(-1000000000\le V_i\le 1000000000)$. All villages are at distinct positions.

Output Specification

Output the smallest neighbourhood size with exactly one digit after the decimal point.

Sample Input

5
16
0
10
4
15

Output for Sample Input

3.0

Explanation for Output for Sample Input

The neighbourhoods around $0$ and $16$ are infinite. The neighbourhood around 4 is $5$ units ($2$ to the left, and $3$ to the right). The neighbourhood around 10 is $5.5$ units ($3$ to the left and $2.5$ to the right). The neighbourhood around 15 is $3.0$ units ($2.5$ to the left and $0.5$ to the right).

Problem S2: Sunflowers

Problem Description

Barbara plants $N$ different sunflowers, each with a unique height, ordered from smallest to largest, and records their heights for $N$ consecutive days. Each day, all of her flowers grow taller than they were the day before.

She records each of these measurements in a table, with one row for each plant, with the first row recording the shortest sunflower’s growth and the last row recording the tallest sunflower’s growth. The leftmost column is the first measurement for each sunflower, and the rightmost column is the last measurement for each sunflower.

If a sunflower was smaller than another when initially planted, it remains smaller for every measurement.

Unfortunately, her children may have altered her measurements by rotating her table by a multiple of 90 degrees.

Your job is to help Barbara determine her original data.

Input Specification

The first line of input contains the number $N$ $(2\le N\le 100)$. The next $N$ lines each contain $N$ positive integers, each of which is at most ${10}^9$. It is guaranteed that the input grid represents a rotated version of Barbara’s grid.

Output Specification

Output Barbara’s original data, consisting of $N$ lines, each of which contain $N$ positive integers.

Sample Input 1

2
1 3
2 9

Output for Sample Input 1

1 3
2 9

Explanation of Output for Sample Input 1

The data has been rotated a multiple of 360 degrees, meaning that the input arrangement is the original arrangement.

Sample Input 2

3
4 3 1
6 5 2
9 7 3

Output for Sample Input 2

1 2 3
3 5 7
4 6 9

Explanation of Output for Sample Input 2

The original data was rotated 90 degrees to the right/clockwise.

Sample Input 3

3
3 7 9
2 5 6
1 3 4

Output for Sample Input 3

1 2 3
3 5 7
4 6 9

Explanation of Output for Sample Input 3

The original data was rotated 90 degrees to the left/counter-clockwise.

Problem S3: RoboThieves

Problem Description

A robot has stolen treasure from a factory and needs to escape without getting caught. The factory can be modelled by an $N$ by $M$ grid, where the robot can move up, down, left, or right.

Each cell of the grid is either empty, a wall, a camera, a conveyor, or the robot’s initial position. The robot can only walk on empty cells (denoted by .) or conveyors. The first row, last row, first column and last column of the grid consists of walls (denoted by W), and there may be walls in other cells.

Conveyors cause the robot to move in a specific direction, denoted by L, R, U, D for left, right, up, down respectively. The robot is unable to move on its own while on a conveyor. It is possible that the robot can become stuck forever on conveyors.

Cameras (denoted by C) can see in all four directions up, down, left, and right, but cannot see through walls. The robot will be caught if it is in the same cell as a camera or is seen by a camera while on an empty cell. Conveyors are slightly elevated, so the robot cannot be caught while on a conveyor, but cameras can see empty cells on the other side of conveyors.

The robot is initially at the cell denoted by S. The exit could be at any of the empty cells. For each empty cell, determine the minimum number of steps needed for the robot to move there without being caught, or determine that it is impossible to move there. A step consists of moving once up, down, left or right. Being moved by a conveyor does not count as a step.

Input Specification

The first line of input contains two integers $N$ and $M$ $(4\le N,M\le 100)$. The next $N$ lines of input will each contain $M$ characters, each of which is one of the eight characters W, ., C, S, L, R, U, or D.

There will be exactly one S character and at least one . character. The first and last character of every row and column will be W.

For 5 of the 15 marks available, there are no cameras or conveyors.

For an additional 5 of the 15 marks available, there are no conveyors.

Output Specification

For each empty cell, print one line with one integer, the minimum number of steps for the robot to move to this empty cell without being caught or $-1$ if it is impossible to move to this empty cell.

The output should be in row major order; the order of empty cells seen if the input is scanned line by line top-to-bottom and then left-to-right on each line. See the sample outputs for examples of row major order output.

Sample Input 1

4 5
WWWWW
W.W.W
WWS.W
WWWWW

Output for Sample Input 1

-1
2
1

Explanation of Output for Sample Input 1

The robot cannot move to the top left empty cell because it is blocked by walls.

The top right empty cell can be reached in $2$ steps and the bottom right empty cell can be reached in $1$ step.

Sample Input 2

5 7
WWWWWWW
WD.L.RW
W.WCU.W
WWW.S.W
WWWWWWW

Output for Sample Input 2

2
1
3
-1
-1
1

Explanation of Output for Sample Input 2

The empty cell to immediate left of the robot is seen by the camera so the robot cannot move there.

The empty cell right below the R conveyor is also seen by the camera as conveyors do not block the the sight of cameras.

Note that the robot can use the U and L conveyors to avoid the getting caught by the camera.

If the robot moves to the R conveyor, it will become stuck forever there.

Problem S4: Balanced Trees

Trees have many fascinating properties. While this is primarily true for trees in nature, the concept of trees in math and computer science is also interesting. A particular kind of tree, a perfectly balanced tree, is defined as follows.

Every perfectly balanced tree has a positive integer weight. A perfectly balanced tree of weight $1$ always consists of a single node. Otherwise, if the weight of a perfectly balanced tree is $w$ and $w\ge 2$, then the tree consists of a root node with branches to $k$ subtrees, such that $2\le k\le w$. In this case, all $k$ subtrees must be completely identical, and be perfectly balanced themselves.

In particular, all $k$ subtrees must have the same weight. This common weight must be the maximum integer value such that the sum of the weights of all $k$ subtrees does not exceed $w$, the weight of the overall tree. For example, if a perfectly balanced tree of weight $8$ has $3$ subtrees, then each subtree would have weight $2$, since $2+2+2=6\le 8$.

Given $N$, find the number of perfectly balanced trees with weight $N$.

Input Specification

The input will be a single line containing the integer $N$ $(1\le N\le {10}^9)$.

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

For an additional $2$ of the $15$ marks available, $N\le 50000$.

For an additional $2$ of the $15$ marks available, $N\le {10}^6$.

Output Specification

Output a single integer, the number of perfectly balanced trees with weight $N$.

Sample Input 1

4

Output for Sample Input 1

3

Explanation for Output for Sample Input 1

One tree has a root with four subtrees of weight 1; a second tree has a root with two subtrees of weight 2; the third tree has a root with three subtrees of weight 1.

Sample Input 2

10

Output for Sample Input 2

13

Problem S5: Maximum Strategic Savings

Problem Description

A long time ago in a galaxy far, far away, there are $N$ planets numbered from $1$ to $N$. Each planet has $M$ cities numbered from $1$ to $M$. Let city $f$ of planet $e$ be denoted as $(e,f)$.

There are $N\times P$ two-way flights in the galaxy. For every planet $e$ $(1\le e\le N)$, there are $P$ flights numbered from $1$ to $P$. Flight $i$ connects cities $(e,a_i)$ and $(e,b_i)$ and costs $c_i$ energy daily to maintain.

There are $M\times Q$ two-way portals in the galaxy. For all cities with number $f$ $(1\le f\le M)$, there are $Q$ portals numbered from $1$ to $Q$. Portal $j$ connects cities $(x_j,f)$ and $(y_j,f)$ and costs $z_j$ energy daily to maintain.

It is possible to travel between any two cities in the galaxy using only flights and/or portals.

Hard times have fallen on the galaxy. It was decided that some flights and/or portals should be shut down to save as much energy as possible, but it should remain possible to travel between any two cities afterwards.

What is the maximum sum of energy that can be saved daily?

Input Specification

The first line contains four space-separated integers $N$, $M$, $P$, $Q$ $(1\le N,M,P,Q\le {10}^5)$.

Then $P$ lines follow; the $i$-th one contains three space-separated integers $a_i$, $b_i$, $c_i$ $(1\le a_i,b_i\le M,1\le c_i\le {10}^8)$.

Then $Q$ lines follow; the $j$-th one contains three space-separated integers $x_j$, $y_j$, $z_j$ $(1\le x_j,y_j\le N,1\le z_j\le {10}^8)$.

It is guaranteed that it will be possible to travel between any two cities using flights and/or portals. There may be multiple flights/portals between the same pair of cities or a flight/portal between a city and itself.

For 2 of the 15 available marks, $P,Q\le 100$ and $c_i=1$ for all $1\le i\le P$, and $z_j=1$ for all $1\le j\le Q$.

For an additional 2 of the 15 available marks, $P,Q\le 200$.

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

Output Specification

Output a single integer, the maximum sum of energy that can be saved daily.

Sample Input 1

2 2 1 2
1 2 1
2 1 1
2 1 1

Output for Sample Input 1

3

Sample Input 2

2 3 4 1
2 3 5
3 2 7
1 2 6
1 1 8
2 1 5

Output for Sample Input 2

41

Explanation for Output for Sample Input 2

One possible way is to shut down the flights between cities $(1,1)$ and $(1,1)$, $(2,1)$ and $(2,1)$, $(1,1)$ and $(1,2)$, $(1,3)$ and $(1,2)$, $(2,3)$ and $(2,2)$, and shut down the portal between cities $(2,3)$ and $(1,3)$ for total energy savings of $8+8+6+7+7+5=41$.