Thank you for participating in Kick Start 2019 Round D.
Cast
X or What: Written by Max Ward, and prepared by Shang-En Huang and Kevin Tran.
Latest Guests: Written by Kevin Tran and prepared by Shang-En Huang.
Food Stalls: Written by Kevin Tran and prepared by Raihat Zaman Neloy.
Solutions, other problem preparation, reviews and contest monitoring by Anushi Maheshwari, Bir Bahadur Khatri, Darcy Best, Gagan Madan, Himanshu Jaju, Kevin Tran, Lalit Kundu, Raihat Zaman Neloy, Sadia Atique, Teja Vardhan Reddy Dasannagari, Vivek Dhiman, and Yang Xiao.
Analyses were authored by Sandeep Mohanty.
Steven has an array of N non-negative integers. The i-th integer (indexed starting from 0) in the array is Ai.
Steven really likes subintervals of A that are xor-even. Formally, a subinterval of A is a pair of indices (L, R), denoting the elements AL, AL+1, ..., AR-1, AR. The xor-sum of this subinterval is AL xor AL+1 xor ... xor AR-1 xor AR, where xor is the bitwise exclusive or.
A subinterval is xor-even if its xor-sum has an even number of set bits in its binary representation.
Steven would like to make Q modifications to the array. The i-th modification changes the Pi-th (indexed from 0) element to Vi. Steven would like to know, what is the size of the xor-even subinterval of A with the most elements after each modification?
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, denoting the number of elements in Steven's array and the number of modifications, respectively.
The second line contains N integers. The i-th of them gives Ai indicating the i-th integer in Steven's array.
Then, Q lines follow, describing the modifications. The i-th line contains Pi and Vi, The i-th modification changes the Pi-th element to Vi. indicating that the i-th modification changes the Pi-th (indexed from 0) element to Vi.
For each test case, output one line containing Case #x: y_1 y_2 ... y_Q, where x is the test case number (starting from 1) and y_i is
the number of elements in the largest xor-even subinterval of A after the i-th modification.
If there are no xor-even subintervals, then output 0.
Time limit: 40 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
0 ≤ Ai < 1024.
0 ≤ Pi < N.
0 ≤ Vi < 1024.
1 ≤ N ≤ 100.
1 ≤ Q ≤ 100.
1 ≤ N ≤ 105.
1 ≤ Q ≤ 105.
2 4 3 10 21 3 7 1 13 0 32 2 22 5 1 14 1 15 20 26 4 26
Case #1: 4 3 4 Case #2: 4
The city of Circleburg has a large circular street with N consulates along it. The consulates are numbered 1, 2, ..., N in clockwise order.
Today G guests, numbered 1, 2, ..., G will drive along the circular street for M minutes.
Each guest is either
a clockwise guest (denoted by the character C) or
an anti-clockwise guest (denoted by the character A).
The i-th guest starts at the consulate numbered Hi and at the end of each minute will drive to an adjacent consulate. The i-th guest starts at the j-th consulate. If that guest is:
Each consulate will only remember the guest that visited them last. If there are multiple guests who visited last, then the consulate will remember all of those guests.
For each guest, determine how many consulates will remember them.
The first line of the input gives the number of test cases, T. T test cases follow.
Each testcase begins with a line containing the three integers N, G and M,
which are the number of consulates, the number of guests and the number of minutes respectively.
Then, G lines follow. The i-th line contains the integer Hi followed by
a single character; C if the i-th guest is a clockwise guest or A if
the i-th guest is an anti-clockwise guest.
For each test case, output one line containing Case #x: y1 y2 ... yG, where x is the test case number (starting from 1) and
yi is the number of consulates that remember the i-th guest.
Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Hi ≤ N, for all i.
2 ≤ N ≤ 100.
1 ≤ G ≤ 100.
0 ≤ M ≤ 100.
2 ≤ N ≤ 105.
1 ≤ G ≤ 105.
0 ≤ M ≤ 109.
4 5 3 2 5 C 2 A 1 A 2 4 0 1 A 1 C 1 A 1 C 3 2 10 3 C 2 A 6 1 6 4 A
Case #1: 2 2 1 Case #2: 1 1 1 1 Case #3: 2 2 Case #4: 6
In the first sample case, there are N = 5 consulates, G = 3 guests, who will drive for M = 2 minutes.
In the second sample case, there are N = 2 consulates, G = 4 guests, who will drive for M = 0 minutes.
In the third sample case, there are N = 3 consulates, G = 2 guests, who will drive for M = 10 minutes.
In the fourth sample case, there is only one guest. This guest visits all the consulates eventually, so is remembered by all of them. Thus the answer is 6.
Everybody loves street food, especially the local residents of Bitetown! For this reason, you have decided to build exactly K food stalls and one warehouse on the main street of Bitetown.
The main street is a long horizontal line that is 109 metres long. There are N spots that you are allowed to build stalls or a warehouse on. You may not build anywhere else on the street. The i-th spot is Xi meters from the left end of the street.
You can build at most one stall or warehouse at the i-th spot (but not both), which costs Ci dollars. Additionally, if the warehouse is in the j-th spot, then building a stall in the i-th spot costs an extra |Xj - Xi| dollars.
Please find the minimum cost to build exactly K food stalls and one warehouse.
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 K and N, the number of stalls you must build and the number of spots on the street, respectively.
The second line contains N integers Xi; the i-th of these is the distance of the i-th spot from the left end of the street, in meters.
The third line contains N integers Ci; the i-th of these is the cost of building a stall or warehouse at the i-th spot.
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 cost to build K stalls.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ K < N
1 ≤ Ci ≤ 109, for all i.
1 ≤ Xi ≤ 109, for all i.
Xi ≠ Xj for all i ≠ j.
2 ≤ N ≤ 100
There will be at most 5 cases with 500 < N ≤ 105.
The remaining cases will have 2 ≤ N ≤ 500.
3 2 4 1 2 3 10 100 70 80 20 1 5 150 300 301 400 700 8 35 26 5 2 6 7 22 21 20 23 26 25 24 10 10 10 10 10 10 10
Case #1: 178 Case #2: 62 Case #3: 82
In Sample Case 1, you must build K = 2 stalls and one warehouse, and there are N = 4 spots to build on. One possible solution is to build the warehouse on the 3rd spot with cost 80 dollars, and build the two stalls on the 2nd and 4th spot.
In Sample Case 2, you must build K = 1 stalls and one warehouse, and there are N = 5 spots to build on. One possible solution is to build the warehouse on the 2nd spot with cost 35 dollars, and build the stall on the 3rd spot, which costs 26 + |301-300| = 27 dollars. This costs 62 dollars in total, which is the minimum possible.
In Sample Case 3, you must build K = 6 stalls and one warehouse, and there are N = 7 spots to build on. One possible solution is to build the warehouse on the 4th spot and build the 6 stalls on the 6 remaining spots. It is left as an exercise to the contestant to verify that this costs 82 dollars in total and is the minimum possible. Note that in this example, the spots are not in ascending order of their distance from the left end of the street.
Let's define a new array S. We set S0 = 0, S1 = A1 and Si = Si - 1 xor Ai for i = 2 to N (Note that S is zero-indexed while A is one-indexed). We can see that once we've calculated this, Al xor Al + 1 ... xor Ar is simply given by Sr xor Sl - 1.
With this, Test set 1 can be solved just by calculating the xor sum of every sub-interval of A and checking if it's xor-even. After each update, we need to recompute S which only takes O(N) time. So each query can be handled in O(N2) time with an overall complexity of O(QN2).
Let's extend the definition of xor-even to mean any number having even number of 1s in it's binary representation, similarly for xor-odd. Now, notice that if we xor two xor-even numbers or two xor-odd numbers (numbers having an odd number of 1s in their binary representations), we get a xor-even number and, similarly, if we xor a xor-even number with a xor-odd number, we get a xor-odd number. Hence, if there are a even number of xor-odd numbers in an interval then that interval is going to be xor-even and vice versa.
This means that if there are even number of xor-odd numbers in our array, the whole array is xor-even. Otherwise, we consider the subarray starting just after the first xor-odd number and going till the end and the subarray starting from the first element in our array and ending just before the last xor-odd number. Both are xor-even intervals and the larger of them should be the largest xor-even interval in our array.
We can do this by keeping a set of all positions of xor-odd numbers. Every time we update a number, we simply do an insertion or a deletion or leave the set unchanged. If the size of the set is even, then the whole array is xor-even, otherwise we get the left most and the right most positions from this set and output the answer as discussed above.
Since we will have an O(N) elements in the set and there will be Q queries, each of O(log(N)) time, this solution has a complexity of O((N+Q)log(N)).
We can also solve this problem using van Emde Boas trees in O(Qlog(log (N))). Or we can use offline algorithms as well to achieve even better asymptotic solutions. Figuring out the details of these approaches is left as exercises to the reader.
For this test set, we simply simulate the entire affair. For each second, we update the positions of all the guests and will add them to the list of latest guests list of the consulate that they visit. We also keep track of the minute when the list for each consulate was updated so that if a guest comes at a later time, we discard the old list and put this guest (and possibly others) to a new list. Finally after the Mth minute, we iterate through all these lists and find for each guest, how many lists they were a part of and output the answer. This takes a total of O(Gx(M+N)) time which is sufficient for this test set.
Let's simplify the problem by assuming all the guests travel clockwise. We can get the final position of each guest after M minutes by simply taking their current position, adding M to it and finding the modulo of the result with N. We categorise the guests into groups based upon their final positions. All guests having the same final positions are in the same group and guests having different final positions are in different groups. We maintain a mapping from guests to groups. We are going to find for each group, how many consulates remember it.
Now notice that for any consulate only the group whose final position is on or just after it in a clockwise order can be the last visiting group. We can get this by doing a binary search on the sorted list of final positions of the groups or using a sliding window. Note that there can be at most one group which will be remembered by a consulate.
If this group did not visit this consulate then no one has visited it. To find this we find the time when the group would have visited this consulate last. So we take the difference of their final positions and the position of the consulate and subtract this number from M. If the resultant is negative that means no one visited this consulate. Otherwise, for this consulate, we make a note of this group and the time when they visited.
We handle anti-clockwise guests similarly and get for each consulate the last anti-clockwise guest group to visit it and the time when the group visited.
Now we iterate through the consulates and see which was the last group to visit it (we include both the clockwise and the anti-clockwise groups). We then increment the number of consulates that remembers this group. Finally, we iterate through the guests and see which group they belong to and output the number of consulates that remember this group. This solution has a run-time of O(N+G) if implemented using the sliding window technique or a run-time of O(G + Nlog(N)) if we use binary-search instead.
We will start by fixing the position of the warehouse. Once that is done, we know the cost of putting up a stall at any spot. This allows for a dynamic programming approach where we let dp[i][j] represent the cost of putting j stalls in the first i spots. dp[i][j] is minimum of dp[i - 1][j] and (dp[i-1][j-1] + distance of ith spot from warehouse + Ci) (we skip i if we have chosen to place the warehouse at i). dp[N][K] + cost of building the warehouse represents our solution for the chosen location of the warehouse.
By doing this for all possible positions for the warehouse, we will get the minimum cost for placing all K stalls. So this approach has a complexity of O(N2K).
Now suppose we decided on the K + 1 spots where we will place our stalls and warehouse but are yet to decide where to place our warehouse, let's say the co-ordinates of these spots are Y1, Y2, ..., YK + 1 in increasing order. Obviously, it'll be the spot Yj such that |Yj - Y1| + |Yj - Y2| + ... |Yj - YK + 1| is minimum. This is the classic post office location problem and is solved by putting the warehouse in the median point of our chosen points (in case of even number of points with two medians, any one will yield an optimal answer).
Once we have this observation, we know that we must put floor(K/2) stalls on the left of our warehouse and K-floor(K/2) stalls on the right. If we can calculate, for every position of the warehouse, the minimum cost to place these points, we will be done. Here we will show how to calculate the minimum cost to place floor(K/2) stalls to the left of every position of the warehouse.
For simplicity, we assume the given points X1, X2, ..., XN to be sorted. Now, we will maintain a max-heap of size floor(K/2). For position i, we define Vi = XN - Xi + Ci. Initially, we will store V1, V2, ..., Vfloor(K/2) in our heap. We'll also maintain the sum of all the elements in our heap.
If we consider that we are placing the warehouse at Xfloor(K/2)+1, then the minimum cost of placing all floor(K/2) stalls to the left of it is given by sum of all the elements in our heap - floor(K/2) * (XN - Xfloor(K/2)+1). We try to get this cost for all other valid placements of the warehouse.
So, for i = floor(K/2) + 1 to N - (K-floor(K/2)) - 1, we check if Vi is less than the maximum element of our heap. If it is then we remove the maximum and insert Vi and update the sum of all our heap elements by subtracting the difference of the removed element and the inserted element. We subtract floor(K/2) * (XN - Xi+1) from the sum and compare it with the minimum cost obtained thus far, updating it with the current cost if current cost is lower.
We can use a similar approach to get the cost of all elements to the right, there Vi will just be Xi and we should iterate from right to left and in each iteration, subtract (K-floor(K/2)) * Xi from the sum of the elements in the heap and update the minimum cost with that.
Finally we see for which point i, the sum of cost of placing floor(K/2) stalls on the left of it, K-floor(K/2) stalls on the right and Ci is minimised and output this value.