Time limit: 1 second
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 \leq 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 \leq N\), then output 0.
The first line of input will contain an integer \(N\) \((1 \leq N \leq 100\ 000)\). 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 \leq 1000\).
Output the largest integer \(K\) such that \(K \leq N\) and the Swifts and the Semaphores have the same total number of runs after \(K\) days.
3
1 3 3
2 2 62
After 2 days, each team had scored a total of 4 runs.
3
1 2 3
4 5 60
The only time when the Swifts and the Semaphores had scored the same number of runs was the beginning of the season.
4
1 2 3 4
1 3 2 44
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.
Time limit: 1 second
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.
The first line contains the integer \(N\) \((1 \leq N \leq 100)\). The next line contains \(N\) distinct space-separated positive integers, where each integer is at most \(1\ 000\ 000\).
Output the \(N\) integers in the unique order that Joe originally took the measurements.
8
10 50 40 7 3 110 90 210 40 7 50 3 90 2 110
The low tide measurements (in order) were 10, 7, 3, and 2. The high tide measurements (in order) were 40, 50, 90, and 110.
Time limit: 2 seconds
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:
The first line will contain the integer \(N\) \((2 \le N
\le 1\ 000\ 000)\).
The second line will contain \(N\)
space-separated integers \(L_1, L_2, \ldots,
L_N\) \((1 \le L_i \le
2\,000)\).
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 100\ 000\).
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.
4
1 2 3 42 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\).
5
1 10 100 1000 20001 10
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.
Time limit: 3 seconds
The city of Watermoo has buildings numbered \(1, 2, \ldots, 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.
The first line will contain the integers \(N\), \(M\), and \(D\) \((1 \le N \le 100\,000, N-1 \le M \le 200\,000, 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 1\,000\) and \(M \le 5\,000\) 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 1\,000\) and \(M \le 5\,000\).
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\).
4 4 0
1 2 1
2 3 2
3 4 1
4 1 11
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\).
5 6 2
1 2 5
2 3 5
1 4 5
4 5 5
1 3 1
1 5 12
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).
4 4 0
1 2 715827882
2 3 715827882
3 4 715827882
4 1 7158278840
The initial valid plan is already an optimal plan. Be careful of integer overflow when implementing your solution.
Time limit: 5 seconds
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.
The first line will contain three space-separated integers \(N\), \(M\), and \(Q\) \((1 \le M \le N \le 150\,000; 1 \le Q \le 150\,000)\). The second line will contain the subway line numbers that each station from \(1\) to \(N\) belongs to: \(L_1, L_2, \ldots, L_N\). The third line will contain \(N\) integers \(A_1, A_2, \ldots, A_N\) \((1 \le A_i \le 7\,000)\) 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
1\,000\) and \(Q \le
1\,000\).
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.
For every survey, output the answer to the survey on a separate line.
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 315
10
9The 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:
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 1114
109
101
114The subway system is illustrated below, with the stations numbered from 1 to 3 and the lines connecting stations marked as all being line 1:
