Thank you for participating in Kick Start 2019 Round G.
Cast
Book Reading: Written and prepared by Jonathan Irvin Gunawan.
The Equation: Written by Zhang Chen and prepared by Jonathan Irvin Gunawan.
Shifts: Written by Himanshu Jaju and prepared by Raihat Zaman Neloy.
Solutions, other problem preparation, reviews and contest monitoring by Bartosz Kostka, Himanshu Jaju, Hsin-Yi Wang, Jonathan Irvin Gunawan, Kevin Tran, Lalit Kundu, Raihat Zaman Neloy, Yang Xiao, and Zhang Chen.
Analysis authors:
Supervin is a librarian handling an ancient book with N pages, numbered from 1 to N. Since the book is too old, unfortunately M pages are torn out: page number P1, P2, ..., PM.
Today, there are Q lazy readers who are interested in reading the ancient book. Since they are lazy, each reader will not necessarily read all the pages. Instead, the i-th reader will only read the pages that are numbered multiples of Ri and not torn out. Supervin would like to know the sum of the number of pages read by each reader.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the three integers N, M, and Q, the number of pages in the book, the number of torn out pages in the book, and the number of readers, respectively. The second line contains M integers, the i-th of which is Pi. The third line contains Q integers, the i-th of which is Ri.
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 total number of pages that will
be read by all readers.
Time limit: 40 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ P1 < P2 < ... < PM ≤ N.
1 ≤ Ri ≤ N, for all i.
1 ≤ M ≤ N ≤ 1000.
1 ≤ Q ≤ 1000.
1 ≤ M ≤ N ≤ 105.
1 ≤ Q ≤ 105.
3 11 1 2 8 2 3 11 11 11 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 1000 6 1 4 8 15 16 23 42 1
Case #1: 7 Case #2: 0 Case #3: 994
In sample case #1, the first reader will read the pages numbered 2, 4, 6, and 10. Note that the page numbered 8 will not be read since it is torn out. The second reader will read the pages numbered 3, 6, and 9. Therefore, the total number of pages that will be read by all readers is 4 + 3 = 7.
In sample case #2, all pages are torn out so all readers will read 0 pages.
In sample case #3, the first reader will read all the pages other than the six given pages.
The laws of the universe can be represented by an array of N non-negative integers. The i-th of these integers is Ai.
The universe is good if there is a non-negative integer k such that the following equation is satisfied: (A1 xor k) + (A2 xor k) + ... (AN xor k) ≤ M, where xor denotes the bitwise exclusive or.
What is the largest value of k for which the universe is good?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and M, the number of integers in A and the limit on the equation, respectively.
The second line contains N integers, the i-th of which is Ai, the i-th integer in the array.
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 of k for which the universe is good, or -1 if there is no such k.
Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ N ≤ 1000.
0 ≤ M ≤ 100.
0 ≤ Ai ≤ 100, for all i.
4 3 27 8 2 4 4 45 30 0 4 11 1 0 100 6 2 5 5 1 5 1 0
Case #1: 12 Case #2: 14 Case #3: 100 Case #4: -1
In sample case #1, the array contains N = 3 integers and M = 27. The largest possible value of k that gives a good universe is 12 ((8 xor 12) + (2 xor 12) + (4 xor 12) = 26).
In sample case #2, the array contains N = 4 integers and M = 45. The largest possible value of k that gives a good universe is 14 ((30 xor 14) + (0 xor 14) + (4 xor 14) + (11 xor 14) = 45).
In sample case #3, the array contains N = 1 integer and M = 0. The largest possible value of k that gives a good universe is 100 (100 xor 100 = 0).
In sample case #4, there is no value of k that gives a good universe, so the answer is -1.
Aninda and Boon-Nam are security guards at a small art museum. Their job consists of N shifts. During each shift, at least one of the two guards must work.
The two guards have different preferences for each shift. For the i-th shift, Aninda will gain Ai happiness points if he works, while Boon-Nam will gain Bi happiness points if she works.
The two guards will be happy if both of them receive at least H happiness points. How many different assignments of shifts are there where the guards will be happy?
Two assignments are considered different if there is a shift where Aninda works in one assignment but not in the other, or there is a shift where Boon-Nam works in one assignment but not in the other.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and H, the number of shifts and the minimum happiness points required, respectively. The second line contains N integers. The i-th of these integers is Ai, the amount of happiness points Aninda gets if he works during the i-th shift. The third line contains N integers. The i-th of these integers is Bi, the amount of happiness points Boon-Nam gets if she works during the i-th shift.
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 number of different assignments of shifts where the guards will be happy.
Time limit: 40 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
0 ≤ H ≤ 109.
0 ≤ Ai ≤ 109.
0 ≤ Bi ≤ 109.
1 ≤ N ≤ 12.
1 ≤ N ≤ 20.
2 2 3 1 2 3 3 2 5 2 2 10 30
Case #1: 3 Case #2: 0
In Sample Case #1, there are N = 2 shifts and H = 3. There are three possible ways for both Aninda and Boon-Nam to be happy:
In Sample Case #2, there are N = 2 shifts and H = 5. It is impossible for both Aninda and Boon-Nam to be happy, so the answer is 0.
We can solve this test set by naively computing the number of pages that each lazy readers will
read. We can do this by initially having an array torn of N booleans, where
torn[x] is true if and only if page x is torn out, and then for each lazy reader i,
we can iterate from 1 to N, incrementing our answer only if the value that we iterate is a
multiple of Ri and not torn out.
The running time of this solution is O(N × Q).
Let f(x) be the number of pages that are multiples of x and not torn out. To compute f(x), we can only check whether the pages x, 2x, 3x, ..., floor(N/x)x are torn out. Therefore, we can do this in N/x time.
This means that we can compute f(1), f(2), ..., f(N) in a total of N(1/1 + 1/2 + ... + 1/N) time. 1/1 + 1/2 + ... + 1/N is approximately O(log N) (since the n-th harmonic number is approximately O(log N)), so in total f(1), f(2), ..., f(N) can be computed in a total of O(N log N) time.
After precomputing f(x), we can easily count the number of pages that each lazy readers will read in O(1). The running time of this solution is O(N log N + Q).
For the first test set, notice that the maximum value of k is 127. This is because each Ai is at most 100, so the leading digit of Ai is at most 26 = 64. If k ≥ 128, then the leading digit of k is at least 27 = 128, meaning that (Ai xor k) ≥ 128 > M.
Hence, we can compute the answer by checking each value of k less than 128 and finding the largest one which produces a sum less than M.
For the second test set, the reasoning above tells us that k < 250, which is too big for us to check every value.
Instead, notice that each bit of k only affects a single bit of each Ai. We can use this property to compute each bit of k separately.
For each 1 ≤ i ≤ 50, define ones(i) to be the number of rules Ai with the i-th bit (numbered starting from the least significant bit) equal to 1. Likewise, define zeroes(i) to be the number of rules with the i-th bit equal to 0. Then we can re-write the sum:
Σ1 ≤ j ≤ N Aj xor k
as:
Σi : i-th bit of k is 1 2i×zeroes(i) + Σi : i-th bit of k is 0 2i×ones(i)
Note that we can minimize this sum by choosing the i-th bit of k to be 1 if ones(i) ≥ zeroes(i), or 0 otherwise. Define f(j) to be the minimum value of the above sum over all bits i ≤ j. We can use f(j) to determine if a feasible value of k exists for the lowest j bits, which lets us solve this problem greedily. The greedy solution is as follows: starting from the most significant bit i, check if we can set it to be one (by adding cost of setting this bit to one and f(i-1)). If this value is less than or equal to m, there exists a feasible k with the i-th bit set to one. Since we want to set to maximize k, it is optimal for us to set this bit to 1. Otherwise, if the sum is larger than m, set the bit to zero. Then iterate by decreasing m by the cost at the current bit and checking the next most significant bit (i-1). In this way, we are able to find the largest feasible k. If f(i) is precomputed, the runtime of this algorithm is O(Nlog(max(Ai))).
Note that since Ai ≤ 1015 and N ≤ 1000, the maximum sum is a little more than 1018, so using 64-bit integers is sufficient for this problem.
For each shift, we have three choices,
We can go through all possible choices for all shifts, and check for how many combinations both of their happiness score is at least H. There are total 3N such combinations possible, enumerating through all of them fits the time limit for test set 1.
For test set 2, we can divide the shifts into 2 sets, each having the size of at most ceil(N/2). We can divide them into two sets, because the choices for each shift are independent of each other. For each set, we can enumerate every possible combination, and compute happiness score for both of the guards for each combination, which gives us a list of happiness score pairs for those two sets. Then for each happiness score pair (h1, h2) of the combinations of set 1, we need to count the number of happiness score pairs (p1, p2) of the combinations of set 2, such that p1+h1 ≥ H and p2+h2 ≥ H, which can be converted to p1 ≥ H-h1 and p2 ≥ H-h2.
Essentially, we can follow these steps below to find the answer.
For this approach, we need a data structure that supports these two operations:
These two operations can be done in O(log2(X)) time using range tree, where X is the number of elements in the data structure. Here upper bound of X is 3(N/2). The total complexity of this approach will be O(3(N/2) × log2(3(N/2))) ~ O(3(N/2) × N) which is sufficient for test set 2.