Google Kick Start Archive — Round G 2019 problems

Overview

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:

• Book Reading: Jonathan Irvin Gunawan
• The Equation: Reyno Tilikaynen

Problem

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.

Input

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.

Output

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.

Limits

Time limit: 40 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ P1 < P2 < ... < PMN.
1 ≤ RiN, for all i.

1 ≤ MN ≤ 1000.
1 ≤ Q ≤ 1000.

1 ≤ MN ≤ 105.
1 ≤ Q ≤ 105.

Sample

Sample Input
```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
```
Sample Output
```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.

B. The Equation

Problem

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?

Input

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.

Output

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.

Limits

Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ N ≤ 1000.

Test set 1 (Visible)

0 ≤ M ≤ 100.
0 ≤ Ai ≤ 100, for all i.

Test set 2 (Hidden)

0 ≤ M ≤ 1015.
0 ≤ Ai ≤ 1015, for all i.

Sample

Sample Input
```4
3 27
8 2 4
4 45
30 0 4 11
1 0
100
6 2
5 5 1 5 1 0
```
Sample Output
```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.

C. Shifts

Problem

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.

Input

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.

Output

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.

Limits

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.

Sample

Sample Input
```2
2 3
1 2
3 3
2 5
2 2
10 30
```
Sample Output
```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:

• Only Aninda works on the first shift, while both Aninda and Boon-Nam work on the second shift.
• Aninda and Boon-Nam work on the first shift, while only Aninda works on the second shift.
• Both security guards work on both shifts.

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.

Test set 1

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).

Test set 2

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).

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

Analysis — B. The Equation

Test set 1 (Visible)

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.

Test set 2 (Hidden)

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 ij. 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.

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

Analysis — C. Shifts

Test set 1 (Visible)

For each shift, we have three choices,

1. Aninda alone guards the shift
2. Boon-Nam alone guards the shift
3. Both of them guard the shift

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.

Test set 2 (Hidden)

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+h1H and p2+h2H, which can be converted to p1H-h1 and p2H-h2.

1. Store the happiness score pairs of combinations of both set 1 and set 2 in two arrays, let's call them A1 and A2.
2. Sort both A1 and A2, by the first value in the pair in decreasing order, then by the second value of the pair in decreasing order.
3. Iterate through A1. For each pair (h1, h2) in A1, do the following:
• Find the pairs (p1, p2) in A2 where p1 is not less H - h1.
• For each of the pair (p1, p2) found, add p2 to a data structure.
• Find the number of elements not less than H - h2 in the data structure, add that to answer.

For this approach, we need a data structure that supports these two operations:

1. Insert a number in the data structure
2. Count number of elements in the data structure not less than a given integer

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.

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