Problem S1: Sum Game

Time limit: 1 second

Problem Description

Annie has two favourite baseball teams: the Swifts and the Semaphores. She has followed them throughout the season, which is now over. The season lasted for $N$ days. Both teams played exactly one game on each day.

For each day, Annie recorded the number of runs scored by the Swifts on that day. She also recorded this information for the Semaphores.

She would like you to determine the largest integer $K$ such that $K\le N$ and the Swifts and the Semaphores had scored the same total number of runs $K$ days after the start of the season. The total number of runs scored by a team after $K$ days is the sum of the number of runs scored by the team in all games before or on the $K$-th day.

For example, if the Swifts and the Semaphores have the same total number of runs at the end of the season, then you should output $N$. If the Swifts and the Semaphores never had the same number of runs after $K$ games, for any value of $K\le N$, then output 0.

Input Specification

The first line of input will contain an integer $N$ $(1\le N\le 100000)$. The second line will contain $N$ space-separated non-negative integers representing the number of runs scored by the Swifts on each day, in order. The third line will contain $N$ space-separated non-negative integers representing the number of runs scored by the Semaphores on each day, in order. You may assume that each team scored at most 20 runs in any single game.

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

Output Specification

Output the largest integer $K$ such that $K\le N$ and the Swifts and the Semaphores have the same total number of runs after $K$ days.

Sample Input 1

3
1 3 3
2 2 6

Output for Sample Input 1

2

Explanation for Output for Sample Input 1

After 2 days, each team had scored a total of 4 runs.

Sample Input 2

3
1 2 3
4 5 6

Output for Sample Input 2

0

Explanation for Output for Sample Input 2

The only time when the Swifts and the Semaphores had scored the same number of runs was the beginning of the season.

Sample Input 3

4
1 2 3 4
1 3 2 4

Output for Sample Input 3

4

Explanation for Output for Sample Input 3

The Swifts and Semaphores have the same number of total runs after the first game, and after the third game, and after the fourth game. We take the largest of these values (1, 3 and 4) and output 4.

Problem S2: High Tide, Low Tide

Time limit: 1 second

Problem Description

Joe Coder is camping near the Bay of Fundy between Nova Scotia and New Brunswick. When he arrived at the bay, he was told that the difference in height between high tide and low tide at the Bay of Fundy was the largest tidal difference in the world. Ever the skeptic, Joe decided to verify this. He chose a reference point and, after learning from the radio when the tides were highest and lowest, he went with a boat to his reference point and measured the depth of the water. Unfortunately, on the last day of his trip, a strong wind scattered his measurements.

Joe has recovered all of his measurements, but they may not be in their original order. Luckily, he remembers some things about his measurements:

• He started measuring water levels at a low tide, his second measurement was of the water level at high tide, and after that the measurements continued to alternate between low and high tides.

• All high tide measurements were higher than all low tide measurements.

• Joe noticed that as time passed, the high tides only became higher and the low tides only became lower.

Given Joe’s measurements in no particular order, you must reconstruct the correct order in which the measurements were taken.

Input Specification

The first line contains the integer $N$ $(1\le N\le 100)$. The next line contains $N$ distinct space-separated positive integers, where each integer is at most $1000000$.

Output Specification

Output the $N$ integers in the unique order that Joe originally took the measurements.

Sample Input

8
10 50 40 7 3 110 90 2

Output for Sample Input

10 40 7 50 3 90 2 110

Explanation of Output for Sample Input

The low tide measurements (in order) were 10, 7, 3, and 2. The high tide measurements (in order) were 40, 50, 90, and 110.

Problem S3: Nailed It!

Time limit: 2 seconds

Problem Description

Tudor is a contestant in the Canadian Carpentry Challenge (CCC). To win the CCC, Tudor must demonstrate his skill at nailing wood together to make the longest fence possible using boards. To accomplish this goal, he has $N$ pieces of wood. The $i^{th}$ piece of wood has integer length $L_i$.

A board is made up of exactly two pieces of wood. The length of a board made of wood with lengths $L_i$ and $L_j$ is $L_i+L_j$. A fence consists of boards that are the same length. The length of the fence is the number of boards used to make it, and the height of the fence is the length of each board in the fence. In the example fence below, the length of the fence is 4; the height of the fence is 50; and, the length of each piece of wood is shown:

Input Specification

The first line will contain the integer $N$ $(2\le N\le 1000000)$.
The second line will contain $N$ space-separated integers $L_1,L_2,\dots ,L_N$ $(1\le L_i\le 2000)$.

For 5 of the 15 available marks, $N\le 100$.
For an additional 4 of the 15 available marks, $N\le 1000$.
For an additional 3 of the 15 available marks, $N\le 100000$.

Output Specification

Output two integers on a single line separated by a single space: the length of the longest fence and the number of different heights a longest fence could have.

Sample Input 1

4
1 2 3 4

Output for Sample Input 1

2 1

Explanation for Output for Sample Input 1

Tudor first combines the pieces of wood with lengths $1$ and $4$ to form a board of length $5$. Then he combines the pieces of wood with lengths $2$ and $3$ to form another board of length $5$. Finally, he combines the boards to make a fence with length $2$ and height $5$.

Sample Input 2

5
1 10 100 1000 2000

Output for Sample Input 2

1 10

Explanation for Output for Sample Input 2

Tudor can’t make a fence longer than length $1$, and there are $10$ ways to make a fence with length $1$ by choosing any two pieces of wood to nail together. Specifically, he may have a fence of height 11, 101, 1001, 2001, 110, 1010, 2010, 1100, 2100 and 3000.

Problem S4: Minimum Cost Flow

Time limit: 3 seconds

Problem Description

The city of Watermoo has buildings numbered $1,2,\dots ,N$. The city has $M$ pipes that connect pairs of buildings. Due to urban planning oversights, building 1 is the only sewage treatment plant in the city. Each pipe can be either active or inactive. The set of active pipes forms a valid plan if building 1 is directly or indirectly connected to each other building using active pipes. (Pipes directly connect pairs of buildings. Buildings $X$ and $Z$ are indirectly connected if $X$ is directly or indirectly connected to $Y$, and $Y$ is directly or indirectly connected to $Z$.)

The municipal government of Watermoo is currently operating a valid plan of $N-1$ pipes today, but they think it is too expensive! Each pipe has a monthly maintenance fee that the city must pay when it is active, and the total cost of a valid plan is the sum of the maintenance fees of its active pipes. (Inactive pipes cost nothing.)

Additionally, researchers at the University of Watermoo have developed an experimental pipe enhancer which you can use on one pipe of your choice. It will reduce that pipe’s cost from $C$ down to $max(0,C-D)$, where $D$ is the enhancer’s strength.

The city wants you to minimize the cost of the plan, and they want you to do it quickly. Every day, the city will allow you to activate one pipe, and deactivate another pipe. How many days do you need to make the set of active pipes form a valid plan, whose cost is minimum among all valid plans and all choices of enhanced pipe?

Note that it is possible that the plan becomes invalid while you are working, but by the end it should be a valid plan.

Input Specification

The first line will contain the integers $N$, $M$, and $D$ $(1\le N\le 100000,N-1\le M\le 200000,0\le D\le {10}^9)$. Each of the next $M$ lines contain three integers $A_i$, $B_i$, and $C_i$, which means that there is a pipe from building $A_i$ to building $B_i$ that costs $C_i$ per month when activated $(1\le A_i,B_i\le N,1\le C_i\le {10}^9)$. The first $N-1$ of these lines represent the valid plan the city is currently using.

It is guaranteed that there is at most one pipe connecting any two buildings and no pipe connects a building to itself.

For 3 of the 15 available marks, $N\le 8$, $M\le 28$ and $D=0$.
For an additional 5 of the 15 available marks, $N\le 1000$ and $M\le 5000$ and $D=0$.
For an additional 3 of the 15 available marks, $D=0$.
For an additional 2 of the 15 available marks, $N\le 1000$ and $M\le 5000$.

Output Specification

Output one integer on a single line, the minimum number of days to complete this task. If the initial valid plan is already an optimal plan, then output $0$.

Sample Input 1

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

Output for Sample Input 1

1

Explanation for Output for Sample Input 1

Note that it does not matter which pipe you use the pipe enhancer on because $D=0$, so it will not affect the maintenance fee of any pipe.
On the first day, you should deactivate the pipe from building $2$ to $3$ and activate the pipe from building $4$ to $1$.

Sample Input 2

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

Output for Sample Input 2

2

Explanation for Output for Sample Input 2

One solution using the minimum number of days is to first use the pipe enhancer on the pipe from building $1$ to $2$ to decrease its cost to 3. Then on the first day, replace the pipe from building $2$ to $3$ with the pipe from building $1$ to $3$, and on the second day replace the pipe from $1$ to $4$ with the pipe from building $1$ to $5$. Note that the cost of the optimal plan is 10.
Additionally, there are no solutions where you use the pipe enhancer on the pipe from building $1$ to $3$ or the pipe from building $1$ to $5$. Doing so would make that pipe have a maintenance fee of 0, and then any optimal plan would have cost 11 (and we have already seen that we can achieve a cost of 10).

Sample Input 3

4 4 0
1 2 715827882
2 3 715827882
3 4 715827882
4 1 715827884

Output for Sample Input 3

0

Explanation for Output for Sample Input 3

The initial valid plan is already an optimal plan. Be careful of integer overflow when implementing your solution.

Problem S5: RMT

Time limit: 5 seconds

Problem Description

The Rail Metro Transit (RMT) operates a very unusual subway system. There are $N$ subway stations numbered from 1 to $N$. There are $M$ subway lines numbered from 1 to $M$, with each station belonging to exactly one line and at least one station per line. The subway lines are circular. That is, if a station is numbered $S$, the next station after $S$ is the station on the same line with the next largest number, unless $S$ is the greatest number of a station in the line, in which case the next station after $S$ is the station on the same line with the least number.

RMT is conducting a load test of their system using volunteer passengers to ride the subway trains. The test begins with one subway train in each station and for every $i$, there are $A_i$ passengers in the train at station $i$. The volunteers do not leave their assigned trains throughout the entire duration of the load test.

Throughout the test, RMT will perform $Q$ actions. Each of the $Q$ actions is one of two types: either they will survey the total number of passengers in the trains at the stations numbered from $\ell$ to $r$; or they will operate all the trains on some line $x$. When a train on line $x$ is operated, it goes to the next station in that line.

You are RMT’s biggest fan, so you have generously volunteered to keep track of RMT’s actions and report the answers to their surveys.

Input Specification

The first line will contain three space-separated integers $N$, $M$, and $Q$ $(1\le M\le N\le 150000;1\le Q\le 150000)$. The second line will contain the subway line numbers that each station from $1$ to $N$ belongs to: $L_1,L_2,\dots ,L_N$. The third line will contain $N$ integers $A_1,A_2,\dots ,A_N$ $(1\le A_i\le 7000)$ representing the initial number of passengers at each station from $1$ to $N$.

The next $Q$ lines will each have one of the following forms:

• 1 $\ell$ r, which represents a survey ($1\le \ell \le r\le N$).

• 2 $x$, which represents RMT operating line $x$ ($1\le x\le M$).

For 2 of the 15 available marks, $N\le 1000$ and $Q\le 1000$.
For an additional 2 of the 15 available marks, $L_i\le L_{i+1}$ $(1\le i<N)$.
For an additional 3 of the 15 available marks, $M\le 200$.
For an additional 3 of the 15 available marks, there will be no more than $200$ trains on any single line.

Output Specification

For every survey, output the answer to the survey on a separate line.

Sample Input 1

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

Output for Sample Input 1

15
10
9

Explanation for Output for Sample Input 1

The subway system is illustrated below, with the stations numbered from 1 to 5 and the lines connecting stations marked as either being line 1 or line 2:

Sample Input 2

3 1 7
1 1 1
114 101 109
1 1 1
2 1
1 1 1
2 1
1 1 1
2 1
1 1 1

Output for Sample Input 2

114
109
101
114

Explanation for Output for Sample Input 2

The subway system is illustrated below, with the stations numbered from 1 to 3 and the lines connecting stations marked as all being line 1: