Thank you for participating in Kick Start’s Round A, especially given some of the issues affecting the scoreboard and submitting solutions. We apologize — we’ve heard you and understand these issues caused frustration, and our team is working hard to ensure we fix the issue for future rounds.

Our first Kick Start round this year featured problems requiring varied skills. The first problem, *Training*,
required an ad-hoc reasoning around optimal decisions and optimizing the implementation via precomputation.
The second problem, *Parcel*'s solution was based on binary search and the concepts of graph theory. The last problem, *Contention*
was a data structures heavy problem requiring some nice observations.

**Cast**

Training: Written by Asim Krishna Prasad and prepared by Sadia Nahreen.

Parcels: Written by Bartosz Kostka and prepared by Kunal Jain and Lalit Kundu.

Contention: Written and prepared by Kevin Tran.

Solutions, other problem preparation, reviews and contest monitoring by Akashdeep Nain, Anupam Das, Bir Bahadur Khatri, Himanshu Jaju, Ian Tullis, Jilei (Jerry) Wang, Jonathan Irvin Gunawan, Kevin Tran, Lalit Kundu, Lizzie Sapiro, Max Ward, Raihat Zaman Neloy, Sadia Atique, and Shimi Zhang.

Analysis authors:

- Training: Sadia Atique
- Parcels: Reyno Tilikaynen
- Contention: Himanshu Jaju

As the football coach at your local school, you have been tasked with picking a team of exactly
**P** students to represent your school. There are **N** students for you to pick from.
The i-th student has a *skill rating* **S _{i}**, which is a positive integer
indicating how skilled they are.

You have decided that a team is *fair* if it has exactly **P** students on it and they all
have the same skill rating. That way, everyone plays as a team.
Initially, it might not be possible to pick a fair team, so you will give
some of the students one-on-one coaching. It takes one hour of coaching to increase the skill
rating of any student by 1.

The competition season is starting very soon (in fact, the first match has already started!), so you'd like to find the minimum number of hours of coaching you need to give before you are able to pick a fair team.

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each test case starts with a line containing the two integers **N** and **P**,
the number of students and the number of students you need to pick, respectively.
Then, another line follows containing
**N** integers **S _{i}**; the i-th of these is the skill of the i-th student.

For each test case, output one line containing `Case #x: y`

, where
`x`

is the test case number (starting from 1) and `y`

is the minimum number
of hours of coaching needed, before you can pick a fair team of **P** students.

Time limit: 15 seconds per test set.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

1 ≤ **S _{i}** ≤ 10000, for all i.

2 ≤

2 ≤ **N** ≤ 1000.

2 ≤ **N** ≤ 10^{5}.

Sample Input

3 4 3 3 1 9 100 6 2 5 5 1 2 3 4 5 5 7 7 1 7 7

Sample Output

Case #1: 14 Case #2: 0 Case #3: 6

In Sample Case #1, you can spend a total of 6 hours training the first student and 8 hours training the second one. This gives the first, second and third students a skill level of 9. This is the minimum time you can spend, so the answer is 14.

In Sample Case #2, you can already pick a fair team (the first and second student) without having to do any coaching, so the answer is 0.

In Sample Case #3, **P** = **N**, so every student will be on your team. You have to
spend 6 hours training the third student, so that they have a skill of 7, like everyone else.
This is the minimum time you can spend, so the answer is 6.

You have been hired recently as the Chief Decision Maker (CDM) at a famous parcel delivery company, congratulations! Customers love speedy deliveries of their parcels and you have decided to decrease the time it takes to deliver parcels around the world to win customers. You have introduced this idea to the authorities and they have allocated you enough budget to build at most one new delivery office.

The world can be divided into an **R** × **C** grid of squares. Each square either
contains a delivery office or it does not. You may pick a grid square that does not already
contain a delivery office and build a new delivery office there.

The delivery time of a parcel to a square is 0 if that square contains a delivery office. Otherwise, it is defined as the minimum Manhattan distance between that square and any other square containing a delivery office. The overall delivery time is the maximum of delivery times of all the squares. What is the minimum overall delivery time you can obtain by building at most one new delivery office?

Note: The Manhattan distance between two squares (r1,c1) and (r2,c2) is defined as |r1 - r2| + |c1 - c2|, where |*| operator denotes the absolute value.

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
The first line of each test case contains the number of rows **R** and number of columns
**C** of the grid. Each of the next **R** lines contains a string of **C** characters
chosen from the set {`0`

, `1`

}, where `0`

denotes the absence of a
delivery office and `1`

denotes the presence of a delivery office in the square.

For each test case, output one line containing `Case #x: y`

, where `x`

is
the test case number (starting from 1) and `y`

is the minimum overall delivery time you
can obtain after adding at most one additional delivery office.

Time limit: 15 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

There is at least one delivery office in the initial grid.

1 ≤ **R** ≤ 10.

1 ≤ **C** ≤ 10.

1 ≤ **R** ≤ 250.

1 ≤ **C** ≤ 250.

Sample Input

3 3 3 101 000 101 1 2 11 5 5 10001 00000 00000 00000 10001

Sample Output

Case #1: 1 Case #2: 0 Case #3: 2

In Sample Case #1, you get a minimum overall delivery time of 1 by building a new delivery office in any one of the five squares without a delivery office.

In Sample Case #2, all the squares already have a delivery office and so the minimum
overall delivery time is 0. Note you have to add **at most** one delivery office.

In Sample Case #3, to get a minimum overall delivery time of 2, you can build a new delivery office in any of these squares: (2, 3), (3, 2), (3, 3), (3, 4), or (4, 3). Any other possibility results in a higher overall delivery time than 2.

You are selling tickets for the front row of seats at a movie theater.
The front row has **N** seats, numbered 1 to **N** from left to right.
You have been out of the office the last week, and upon your return, **Q** *bookings* for
seats have piled up!
The i-th booking requests all the seats from
**L _{i}** to

Since some of the bookings may overlap, the system might not be able to fulfill each booking entirely. When you enter a booking into the system, it will assign every seat requested by the booking that hasn't already been assigned to a booking entered into the system earlier.

What is the largest integer k where there exists an order that you can enter the bookings into the system, such that each booking is assigned at least k seats?

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each test case starts with a line containing two integers **N** and **Q**,
the number of seats and the number of bookings, respectively.
Then, there are **Q** more lines, the i-th of which contains the two integers
**L _{i}** and

For each test case, output one line containing `Case #x: y`

, where `x`

is
the test case number (starting from 1) and `y`

is
the largest value k, as described above.

Time limit: 15 seconds per test set.

Memory limit: 1GB.

**T** = 100.

1 ≤ **N** ≤ 10^{6}.

1 ≤ **L _{i}** ≤

1 ≤ **Q** ≤ 300.

1 ≤ **Q** ≤ 30000.

For at least 85 of the test cases, **Q** ≤ 3000.

Sample Input

3 5 3 1 2 3 4 2 5 30 3 10 11 10 10 11 11 10 4 1 8 4 5 3 6 2 7

Sample Output

Case #1: 1 Case #2: 0 Case #3: 2

In Sample Case #1, there are **N** = 5 seats and **Q** = 3 bookings. One possible order is:

- Put in the second booking, where the system will book 2 seats (3 and 4).
- Put in the first booking, where the system will book 2 seats (1 and 2).
- Put in the third booking, where the system will book 1 seat (only seat 5, since seats 1, 2, 3 and 4 are already booked).

In Sample Case #2, there are **N** = 30 seats and **Q** = 3 bookings.
No matter what order you assign the seats in, at least one booking will have no seats assigned to it. So the answer is 0.
Notice that there can be seats that are not part of any bookings!

In Sample Case #3, there are **N** = 10 seats and **Q** = 4 bookings. One possible order is:

- Put in the second booking, where the system will book 2 seats (4 and 5).
- Put in the third booking, where the system will book 2 seats (3 and 6, since 4 and 5 are already booked). Notice that the seats booked are not necessarily adjacent to each other.
- Put in the fourth booking, where the system will book 2 seats (2 and 7).
- Put in the first booking, where the system will book 2 seats (1 and 8).

**Note**: We do not recommend using interpreted/slower languages for the Large dataset of this problem.

To make a fair team, we have to train the members of the team to the same skill level as the most
skillful member of the team.

For any **P** students we pick, the time required to make a fair team is =
Σ(max(**S**_{i}, **S**_{i+1}... **S**_{P}) - **S**_{i}),
for all students i = 1 to **P** in the team. Our goal is to minimize this value.

One possible approach could be to go through all possible subsets of **P** students, from the
given **N** students.
But there exists ^{N}C_{P} such subsets(here symbol C denotes
Combination). Number of such subsets will
be in the order of Factorial(**N**) and
so enumerating through all of them will not fit within the time limit.

We can start with the observation that once we fix the student with highest skill level x, to minimize
our goal we should always choose students with skills as high as possible, but less than or equal to
x. Hence we can sort students on the basis of skill level in decreasing order, and iterate over each
student assuming they would have the highest skill level in the team. Say, this student is at position
i in the sorted sequence; the team would be formed of students on positions i, i + 1, ..., i + **P** - 1
(i.e. a contiguous subarray of size **P**).

For each subarray of size **P** in the sorted array, we can calculate the training time required
to make a fair team using the aforementioned formula. There are **N** - **P** + 1 subarrays of size
**P**, and the complexity of calculating training time of subarray size **P** is O(**P**).
So the overall complexity of this approach is O(**N** × **P**), which will be sufficient
for test set 1.

We need to go through all of the subarrays once, but can we calculate the training time of a subarray faster?

Let us assume the array is sorted in decreasing order. The training time formula for a subarray
starting at position i is

= Σ(**S**[i] - **S**[j]) where j = i to i + **P** -1

= **P** × **S**[i] - Σ(**S**[j]) where j = i to i + **P** - 1

As we always need the sum of a contiguous subarray, we can pre compute the prefix sum of the whole
array in advance, and get the sum of any subarray in O(1) time, which makes the calculation of
training time O(1).

So, the overall complexity of this approach is O(**N**).

Test Data

We recommend that you practice debugging solutions without looking at the test data.

For Test Set 1, we are able to check all possible locations for the new delivery office in order to find the one that minimizes delivery time. We will do this in two stages. First, we will compute the delivery time for each square given the existing delivery offices. Second, we will try all possible locations for the new office. The precomputation in the first part will allow us to find the delivery time in the second part more efficiently.

For the first stage, we compute the delivery time of a square by iterating over the entire grid
and finding the minimum manhattan distance to a square that has a delivery office. This has a time
complexity of O(**RC**) per square for a total time complexity of O((**RC**)^{2}).

For the second stage, we iterate over all possible locations for the new delivery office and for
each location, search the entire grid for the square with the maximum new delivery time. The new
delivery time is the minimum of the delivery time computed in the first part and the manhattan
distance to the new delivery office. This also has a time complexity of O(**RC**) per delivery
location for a total time complexity of O((**RC**)^{2}), which is sufficient for Test
Set 1.

Alternatively, we could skip the first stage if we use a faster way of computing the delivery time for each square such as breadth-first search. See the next section for more details.

We can use a similar approach for Test Set 2, however we will need a more efficient way to compute
the maximum delivery time for a new delivery location. We will do this by solving the following
subproblem: given a value of **K**, can we add a new delivery office so that the maximum
delivery time is at most **K**? The solution to this subproblem will be similar to Test Set 1,
however having a target value of **K** allows us to identify exactly which squares need to be
serviced by the new delivery office. We can use this difference to create a faster solution.

Note that if the answer to the original problem is **K**, then the answer to our subproblem
will be 'No' for values in the range [1, **K**-1] and 'Yes' for values in the range
[**K**, infinity]. For these kinds of subproblems, we can use binary search: if a given value
works, then it is an upper bound for the answer; otherwise it's a strict lower bound for the
answer. Hence, once we have a solution for the subproblem, we can use binary search to solve
the original problem. This is a common technique to transform optimization problems into decision
problems.

First, we efficiently compute the existing delivery time of every square by inverting the problem:
instead of finding the shortest distance to a delivery office for each square, we find the
shortest distance to each square from a delivery office. This can be done using a multiple-source,
breadth-first search
starting at all of the delivery offices. A multiple-source BFS is the same as a regular BFS except
that you use multiple starting locations instead of one. This search visits each square at most
once, which gives us a time complexity of O(**RC**).

Second, we identify all of the squares which have a delivery time greater than **K** and then
determine if there exists a location that is within a distance of **K** to each of these
squares. In order to do this efficiently, we note that the manhattan distance has an equivalent
formula:

dist((x_{1}, y_{1}), (x_{2}, y_{2})) =
max(abs(x_{1} + y_{1} - (x_{2} + y_{2})),
abs(x_{1} - y_{1} - (x_{2} - y_{2})))

This formula is based on the fact that for any point, the set of points within a manhattan
distance of **K** form a square rotated by 45 degrees. The benefit of this formula is that if
we fix (x_{2}, y_{2}), the distance will be maximized when
x_{1} + y_{1} and x_{1} - y_{1} are either maximized or minimized.

Hence, we can compute the maximum and minimum values of both x_{1} + y_{1} and
x_{1} - y_{1} for all squares with a delivery time greater than **K**. Then, we
can try all possible locations for the new delivery office and check if the maximum distance from
the location to a square with a current delivery time greater than **K** is at most **K** in
constant time. Hence, we can check if the answer is at most **K** with a time complexity of
O(**RC**).

With the binary search, the time complexity becomes O(**RC**log(**R**+**C**)), which is
sufficient for the test set. There is a way to improve this to O(**RC**) time by computing the
min/max values mentioned above for all possible **K** in a single pass over the grid and then
using casework to determine if a viable new delivery office location exists for each **K**, but
this optimization is unnecessary.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

The number of possible orderings of the requests is
Factorial(**Q**), which would not be fast enough
for either of the test sets. We can observe that for a chosen ordering of the requests, the number
of seats that the system books in the last request does not depend on the ordering of the previous
**Q** - 1 requests. So, we could start by finding the request to be processed last and move
backwards towards the earlier requests. The answer is the minimum seats booked across the **Q**
steps.

Another observation is that at every step, we can always choose this last request greedily from
the remaining set: the one where we can book the maximum number of seats. An intuitive proof of
why this works would be noticing that our final answer is non-increasing over the **Q** steps. Now,
we can use exchange argument to prove this observation since choosing a request with lesser seats
booked would not give us a better answer.

A naive implementation would be of the order O(**N** × **Q**), where we recalculate
number of seats for remaining requests in O(**N**) using
sweep line algorithm for each of
the **Q** steps. We can speed this up with another observation: the number of unique ranges
that the requests cover is at max 2 * **Q**, which would make our solution run in O(**Q**^{2})
for every test case.

Let us try to speed up the slow process of recalculating number of seats we can book at every step
For every seat, let us denote the *value* of a seat as the number of remaining requests
trying to book this seat. Everytime the value of a seat drops to 1, we increase the number of
seats we can book for the corresponding request containing this seat booking.

Since requests are represented by an interval, we can use an
interval tree to support the operations
of removing an interval after the initial construction of the tree. Each node of the interval tree
stores the set of intervals that cover it, and also the minimum value of any seat in it's range.
Whenever a remove operation makes the minimum value become one, we walk down the tree to
find the seats that became one, and walk back up the tree to find out which interval is the only interval that now
covers that seat. We now set that seat's value to infinity so that we don't process it again.
This happens only once per seat, for a total amortised cost of O(**N**log**N**).
In total this algorithm is O(**N**log(**Q**+**N**)), if you use a constant time set (like a hashset).

Test Data

We recommend that you practice debugging solutions without looking at the test data.