Google Kick Start Archive — Round B 2014 problems
Overview
A. Password Attacker
Problem
Passwords are widely used in our lives: for ATMs, online forum logins, mobile device unlock and door access. Everyone cares about password security. However, attackers always find ways to steal our passwords. Here is one possible situation:
Assume that Eve, the attacker, wants to steal a password from the victim Alice. Eve cleans up the keyboard beforehand. After Alice types the password and leaves, Eve collects the fingerprints on the keyboard. Now she knows which keys are used in the password. However, Eve won't know how many times each key has been pressed or the order of the keystroke sequence.
To simplify the problem, let's assume that Eve finds Alice's fingerprints only occurs on M keys. And she knows, by another method, that Alice's password contains N characters. Furthermore, every keystroke on the keyboard only generates a single, unique character. Also, Alice won't press other irrelevant keys like 'left', 'home', 'backspace' and etc.
Here's an example. Assume that Eve finds Alice's fingerprints on M=3 key '3', '7' and '5', and she knows that Alice's password is N=4-digit in length. So all the following passwords are possible: 3577, 3557, 7353 and 5735. (And, in fact, there are 32 more possible passwords.)
However, these passwords are not possible:
1357 // There is no fingerprint on key '1'
3355 // There is fingerprint on key '7',
so '7' must occur at least once.
357 // Eve knows the password must be a 4-digit number.
With the information, please count that how many possible passwords satisfy the statements above. Since the result could be large, please output the answer modulo 1000000007(109+7).
Input
The first line of the input gives the number of test cases, T.
For the next T lines, each contains two space-separated numbers M and N, indicating a test case.
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 possible passwords modulo 1000000007(109+7).
Limits
Time limit: 30 seconds per test set.
Memory limit: 1GB.
Small dataset (Test set 1 - Visible)
T = 15.
1 ≤ M ≤ N ≤ 7.
Large dataset (Test set 2 - Hidden)
T = 100.
1 ≤ M ≤ N ≤ 100.
Sample
4 1 1 3 4 5 5 15 15
Case #1: 1 Case #2: 36 Case #3: 120 Case #4: 674358851
B. New Years Eve
Problem
At new years party there is a pyramidal arrangement of glasses for wine. For example, at the top level, there would just be one glass, at the second level there would be three, then 6 and then 10 and so on and so forth like the following image:
The glasses are numbered using 2 numbers, L and N. L represents the level of the glass and N represents the number in that level. Numbers in a given level are as follows:
Level 1:
1
Level 2:
1
2 3
Level 3:
1
2 3
4 5 6
Level 4:
1
2 3
4 5 6
7 8 9 10
Each glass can hold 250ml of wine. The bartender comes and starts pouring wine in the top glass(The glass numbered L = 1 and N = 1) from bottles each of capacity 750ml.As wine is poured in the glasses, once a glass gets full, it overflows equally into the 3 glasses on the next level below it and touching it, without any wine being spilled outside. It doesn't overflow to the glasses on the same level beside it. It also doesn't overflow to the any level below next level (directly).
For example: When the glass of L = 2 and N = 2 overflows, the water will overflow to glasses of L = 3 and N = 2, 4, 5.
Once that the bartender is done pouring B bottles, figure out how much quantity in ml of wine is present in the glass on level L with glass number N.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of three integers, B, L, N, B is the number of bottles the bartender pours and L is the glass level in the pyramid and N is the number of the glass in that level.
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 quantity of wine in ml in that glass.
We recommend outputting y to 7 decimal places, but it is not required. y will be considered correct if it is close enough to the correct number: within an absolute or relative error of 10-6. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.
Limits
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 150.
Small dataset (Test set 1 - Visible)
1 ≤ B ≤ 1000.
1 ≤ L ≤ 100.
1 ≤ N ≤ Number of glasses on the corresponding level.
Large dataset (Test set 2 - Hidden)
1 ≤ B ≤ 50000.
1 ≤ L ≤ 400.
1 ≤ N ≤ Number of glasses on the corresponding level.
Sample
7 1 2 1 1 1 1 2 1 1 20 1 1 1 3 1 2 3 1 10 4 10
Case #1: 166.6666667 Case #2: 250.0000000 Case #3: 250.0000000 Case #4: 250.0000000 Case #5: 0.0000000 Case #6: 55.5555556 Case #7: 157.4074074
C. Card Game
Problem
Bob is fond of playing cards. On his birthday party, his best friend Alice gave him a set of cards.
There are N cards and each card contains an integer number. He put the cards from left to right on a desk and wants to discard some of them. Before he discards any cards, he will choose a number K. At each time, he always chooses 3 adjacent cards to discard, and we assume that the numbers on each card from left to right are a, b and c. Bob guarantees that
c - b = b - a = K
Bob want to know what is the smallest number of cards he can be left with at the end. If he ever has a choice of which cards to discard, he chooses the cards and will leave the fewest cards at the end.
Input
The first line of the input gives the number of test cases, T. T test cases follow.
Each test cases contains two lines. The first line of each test case contains two integers: the number of cards N and the number K Bob chooses. The second line contains N integers a1, a2, ..., aN the numbers on the cards from left to right.
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 smallest number of cards Bob can be left with after he has discarded everything he can.
Limits
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ ai ≤ 106(1 ≤ i ≤ N).
1 ≤ N ≤ 100.
Small dataset (Test set 1 - Visible)
K = 0.
Large dataset (Test set 2 - Hidden)
1 ≤ K ≤ 106.
Sample
2 6 0 4 4 3 3 3 4 5 1 3 1 2 3 4
Case #1: 0 Case #2: 2
D. Parentheses Order
Problem
An n parentheses sequence consists of n (s and n )s.
A valid parentheses sequence is defined as the following:
You can find a way to repeat erasing adjacent pair of parentheses () until it becomes empty.
For example, (()) is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes () then you can make it empty.
)()( is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes )( and you cannot erase any more.
Now, we have all valid n parentheses sequences. Find the k-th smallest sequence in lexicographical order.
For example, here are all valid 3 parentheses sequences in lexicographical order:
((())) (()()) (())() ()(()) ()()()
Input
The first line of the input gives the number of test cases, T. T lines follow. Each line represents a test case consisting of 2 integers, n and k.
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 k-th smallest parentheses sequence in all valid n parentheses sequences. Output "Doesn't Exist!" when there are less than k different n parentheses sequences.
Limits
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
Small dataset (Test set 1 - Visible)
1 ≤ n ≤ 10.
1 ≤ k ≤ 100000.
Large dataset (Test set 2 - Hidden)
1 ≤ n ≤ 100.
1 ≤ k ≤ 1018.
Sample
3 2 2 3 4 3 6
Case #1: ()() Case #2: ()(()) Case #3: Doesn't Exist!
Analysis — A. Password Attacker
For small dataset, a simple brute-force algorithm will do. Also, since M < 10 and N ≤ 7, you can simply use 32-bit integer to enumerate all potential passwords. Pseudo-code:
answer = 0
for password in (0 .. 10N-1):
condition1 = every digit in password < M
condition2 = every element in {0 .. M-1} occurs at least once in password
if condition1 == true and condition2 == true:
answer = answer + 1
print(answer)
However, the algorithm above is not fast enough for large dataset. Assume that f(M,N) be the answer. If we ignore the condition that "All M characters should occurs in the password at least once", then the answer will be very simple -- MN.
But we can't ignore that. f(M,N) = MN takes some invalid passwords into count. What are they? They're the passwords formed with less than M characters. More precisely, we need to deduct all f(i,N) from MN where 1≤i<M. Is that enough?
Not yet. Note that we need to choose a set of i characters first. Consider character set S={3,5,7} with N=4. If we want to remove all i=1-character passwords, we need to remove 3333, 5555 and 7777 -- we need to pick up a subset of S with i elements. That's a classical combinatorial problem.
By putting everything together, we have f(M,N) = MN - sigma(1≤i<M)C(M,i)*f(i,N) and f(1,N) = 1. We can easily solve it by using dynamic programming.
Analysis — B. New Years Eve
Analysis — C. Card Game
For small dataset, there is a greedy solution - we can choose any 3 adjacent cards with same number, util we can't find such triple.
For large dataset, there it's a dynamic programming problem. We can define a state DP[i][j], which indicates the smallest number of card Bob can not drop if we consider all cards with index from i to j. So for every legal state, we have four choices:
- Get rid of the card with index i
- Get rid of the card with index j
- Choose a card with index k, which meets
aj - ak = ak - ai = K
- Choose a card with index k, and split the cards into two parts(one from i to k and the other one from k + 1 to j)