Bahu is playing a board game with Bala. Each player has 3 * N army cards with various strength values. There are 3 battlefields in the game. Each player must distribute their cards among the battlefields, face down, such that each battlefield gets exactly N of their cards.
When the game begins, all cards will be revealed. For each battlefield, each player sums up the strength values of their N cards in that battlefield, and then the players compare those totals. If one player has a higher total, that player wins that battlefield. If the totals are the same, Bala wins that battlefield; this is his special advantage.
The overall winner of the game is the player who wins the most battlefields. (Since there are 3 battlefields, it is guaranteed that there will not be an overall tie.)
Bala thinks that his advantage is enough to make him win, so he just randomly shuffles his cards and puts the first N on the first battlefield, the next N on the second battlefield, and the last N on the third battlefield.
Even though Bahu is at a disadvantage, he is still going to try to win! Find the probability that he will win if he distributes his cards optimally. Note that all Bala's cards are faced down so Bahu must choose the distribution of his cards before seeing the distribution of Bala's cards.
The first line of the input gives the number of test cases, T. T test cases follow; each consists of three lines. The first line contains an integer N, as described above. The second line contains 3 * N integers A0, A1, ... , A3*N-1, representing the strength values of Bahu's cards. The third line consists of 3 * N integers B0, B1, ... , B3*N-1, representing the strength values of Bala's cards.
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 probability described above. y will be
considered correct if it is within an absolute or relative error of
10-6 of the correct answer. See the
FAQ
for an explanation of what that means, and what formats of real numbers we
accept.
1 ≤ T ≤ 100.
Time limit: 60 seconds per test set.
Memory limit: 1 GB.
1 ≤ Ai ≤ 106, for all i.
1 ≤ Bi ≤ 106, for all i.
N = 3.
3 ≤ N ≤ 5.
2 3 2 2 2 2 2 2 2 3 3 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 3 3 2 2 2 2 2 2 2 2 3
Case #1: 1.000000000 Case #2: 0.333333333
In Sample Case #1, Bahu can put cards (2, 2, 2) in first battle field, (2, 2, 3) in second battle field and (2, 2, 3) in third battle field. As all Bala's cards are 2, Bala wins the first battle field and Bahu wins the second and third battle field.
The milk tea in China is very delicious. There are many binary ("either-or")
options for customizing a milk tea order, such as "with ice"/"no ice",
"with sugar"/"no sugar", "with bubbles"/"no bubbles",
"with pudding"/"no pudding", and so on. A customer's preferences for their
milk tea can be represented as a binary string. For example, using the four
properties above (in the order they are given), the string 1100
means "with ice, with sugar, no bubbles, no pudding".
Today, Shakti is on duty to buy each of his N friends a milk tea, at
a shop that offers P binary options. But after collecting everyone's
preferences, Shakti found that the order was getting too complicated, so
Shakti has decided to buy the same type of milk tea for everyone. Shakti
knows that for every friend, for every preference that is not satisfied, they
will complain once. For example, if two of the friends have preferences for
types 101 and 010, and Shakti chooses type
001, then the first friend will complain once and the second
friend will complain twice, for a total of three complaints.
Moreover, there are M different forbidden types of milk tea that the shop will not make, and Shakti cannot choose any of those forbidden types.
What is the smallest number of complaints that Shakti can get?
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 3
integers N, M, and P, as described above. Then, there
are N more lines, each of which contains a binary string; these
represent the preferences of the N friends. Finally, there are
M more lines, each of which contains a binary string; these represent
the forbidden types of milk tea that the shop will not make. Binary strings
consist only of 0 and/or 1 characters.
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 complaints that Shakti can get, per
the rules described above.
1 ≤ T ≤ 100.
Time limit: 30 seconds per test case.
Memory limit: 1 GB.
All of the forbidden types of milk tea are different.
1 ≤ N ≤ 10.
1 ≤ M ≤ min(10, 2P - 1).
1 ≤ P ≤ 10.
1 ≤ N ≤ 100.
1 ≤ M ≤ min(100, 2P - 1).
1 ≤ P ≤ 100.
2 3 1 4 1100 1010 0000 1000 2 4 4 1111 1111 1111 0111 1011 1101
Case #1: 4 Case #2: 2
In Sample Case #1, there are 3 friends, and they want milk teas of types
1100, 1010, and 0000. If Shakti could
choose type 1000, then each friend would complain once,
for a total of 3 complaints. However, type 1000 is not available
in the shop. So, given these constraints, an optimal solution is to choose
type 1100. Then, his friends will complain 0, 2, and 2 times,
respectively, for a total of 4 complaints.
In Sample Case #2, Shakti's best option is to choose type 1110.
Each friend will complain once, for a total of 2 complaints. Notice that
different friends might have the same preferences. Also notice that the
limits for both the Small and Large datasets guarantee that there is always
at least one possible type of milk tea that is not forbidden.
Yogurt can be a nutritious part of an appetizer, main course, or dessert, but it must be consumed before it expires, and it might expire quickly! Moreover, different cups of yogurt might expire on different days.
Lucy loves yogurt, and she has just bought N cups of yogurt, but she is worried that she might not be able to consume all of them before they expire. The i-th cup of yogurt will expire Ai days from today, and a cup of yogurt cannot be consumed on the day it expires, or on any day after that.
As much as Lucy loves yogurt, she can still only consume at most K cups of yogurt each day. What is the largest number of cups of yogurt that she can consume, starting from today?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with one line containing two integers N and K, as described above. Then, there is one more line with N integers Ai, as described above.
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 maximum number of cups of yogurt that Lucy can consume,
as described above.
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ K ≤ N.
1 ≤ Ai ≤ 109, for all i.
1 ≤ N ≤ 1000.
K = 1.
1 ≤ N ≤ 5000.
2 2 1 1 1 5 1 3 2 3 2 3
Case #1: 1 Case #2: 3
In Sample Case #1, each of the two cups of yogurt will expire in one day. Today, Lucy can consume one of them, but she can only consume at most one cup each day, so she cannot consume both. Tomorrow, Lucy cannot consume the remaining cup of yogurt, because it will have expired.
2 2 2 1 1 6 2 1 1 1 7 7 7
Case #1: 2 Case #2: 5
In Sample Case #1, Lucy can consume up to two cups each day, so she can consume all of the yogurt.
Bahu needs to determine the best possible card distribution given that Bala will choose a distribution uniformly at random. In the Small dataset, N = 3, so there are only 9! / 3! / 3! / 3! = 1680 different ways for a player to distribute their cards. (If there are multiple cards with the same strength value, some of these distributions may be practically equivalent, but we will treat them as different for simplicity.) We can enumerate all 1680 possible distributions Ui for Bahu, and all 1680 possible distributions Aj for Bala. (These variables are named after the last letters of the players' names.) For each Ui, we find the fraction of all Ajs that lose against that Ui. The largest such fraction is our answer. The time complexity is on the order of 16802 times a small constant factor.
In the Large dataset, it is possible that N = 5. In that case, there are 15! / 5! / 5! / 5! = 756756 different distributions. We cannot use the above strategy with a 7567562 time factor.
Only the sums of the cards in the three battlefields matter; let them be U1, U2, U3 for Bahu and A1, A2, A3 for Bala. Then Bahu wins if at least two of the following inequalities are satisfied: U1 > A1, U2 > A2, U3 > A3.
We can deal with the "at least two" part of that criterion by using the inclusion-exclusion principle. Then, for each Ui:
The number of Ajs satisfying the above criterion =
The number of Ajs satisfying U1 > A1 and U2 > A2 +
The number of Ajs satisfying U1 > A1 and U3 > A3 +
The number of Ajs satisfying U2 > A2 and U3 > A3 -
2 × the number of Ajs satisfying U1 > A1 and U2 > A2
and U3 > A3.
The last of those quantities is the most difficult one to calculate. Here we need another observation that there are only 15 choose 5 = 3003 different possibilities for all U1, U2, U3. We can label these possibilities 1 through 3003.
This is a 3-dimensional query, but we can remove 1 dimension by processing the Us in increasing order of U1 and also preprocessing As in increasing order of A1. After that, we can create a 2-dimensional segment tree to store all (A2, A3)s that have A1 < U1. We can find all (A2, A3)s such that U2 > A2 and U3 > A3 in log 3003 × log 3003 time complexity. The other 3 quantities in the equation above can also be found in a similar way. The overall time complexity is on the order of 756756 × log 3003 × log 3003 times a small constant factor, which is fast enough to solve this dataset.
For the Small dataset, there are only 2P different combinations of options available. Since P is at most 10, there are only 1024 possible combinations. Take the combination that gives the fewest mistakes that isn't forbidden.
For the Large dataset, first notice that there are at most 100 forbidden combinations. One approach is to generate the 101 combinations that cause the fewest complaints and take the best one that is not forbidden (there is at least one combination that is not forbidden in the top 101).
To generate these combinations, begin by noticing that in terms of the number of complaints you will get, each of the options can be considered separately. To help us later, preprocess for each option, how many complaints we would get if we were to get the milk tea with that option and without it. We will now build up the best combinations one option at a time.
Let Tk denote the top 101 combinations that generate the fewest complaints when we consider only the first k options, represented as a binary string (tiebreaking arbitrarily). The key idea is to note that each combination in Tk+1 has a combination from Tk as a prefix.
This is easy to show by contradiction. Take any string S from Tk+1 and remove the last bit to get the prefix S'. Suppose for a contradiction that S' is not Tk. Taking any string in Tk and appending the removed bit will give a combination that generates strictly fewer (when considering the tiebreak) complaints. This gives 101 strings that generate fewer complaints, which contradicts S being in Tk+1.
So the final algorithm is as follows:
Intuitively, if Lucy wants to maximize the amount of yogurt she consumes, she should consume as many cups as possible each day, and always choose a cup that is closest to expiring.
We can directly implement the above strategy to solve the Small dataset, in which Lucy can only consume one cup per day. On each day, we scan the list for the smallest unselected cup that has not expired, consume it, and remove it from the list. Since we make up to N passes through a list with up to N items, the time complexity is O(N2).
To improve the above strategy to solve the Large dataset, we can first sort the cups in non-decreasing order of time until expiration. Then, on each day, we remove all expired cups from the beginning of the list and then consume the next K. Since we only handle each cup in the sorted list once, the initial sorting step determines the overall time complexity, which is O(N log N).
But we can do even better! Notice that there are only N cups, and since K ≥ 1, Lucy could consume or discard all of them in at most N days. So any Aj ≥ N can be replaced with N. Then, we can count how may cups will expire on each day, and then proceed backwards from the Nth day to the first day. On each day, Lucy consumes at most K cups, and moves any remaining cups from that day to the previous day, since it is safe to consume them earlier. (Any extra cups left over on day 1 must be discarded.) We make one forward pass through the data to count the cups and one reverse pass to answer the question, so this strategy is O(N).