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:
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 Si, 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 Si; 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 ≤ Si ≤ 10000, for all i.
2 ≤ P ≤ N.
2 ≤ N ≤ 1000.
2 ≤ N ≤ 105.
3 4 3 3 1 9 100 6 2 5 5 1 2 3 4 5 5 7 7 1 7 7
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.
3 3 3 101 000 101 1 2 11 5 5 10001 00000 00000 00000 10001
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 Li to Ri inclusive. You now have the boring job of entering each booking into the system, one at a time.
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 Li and Ri, indicating that the i-th booking would like to book all the seats from Li to Ri, inclusive.
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 ≤ 106.
1 ≤ Li ≤ Ri ≤ N.
1 ≤ Q ≤ 300.
1 ≤ Q ≤ 30000.
For at least 85 of the test cases, Q ≤ 3000.
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
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:
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:
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(Si, Si+1... SP) - Si),
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 NCP 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).
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((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))
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 (x2, y2), the distance will be maximized when x1 + y1 and x1 - y1 are either maximized or minimized.
Hence, we can compute the maximum and minimum values of both x1 + y1 and x1 - y1 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(RClog(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.
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(Q2) 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(NlogN). In total this algorithm is O(Nlog(Q+N)), if you use a constant time set (like a hashset).