# Google Kick Start Archive — Round B 2014 problems

## Overview

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

T = 15.
1 ≤ MN ≤ 7.

T = 100.
1 ≤ MN ≤ 100.

### Sample

Sample Input
```4
1 1
3 4
5 5
15 15```
Sample Output
```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

Sample Input
```7
1 2 1
1 1 1
2 1 1
20 1 1
1 3 1
2 3 1
10 4 10

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

K = 0.

1 ≤ K ≤ 106.

### Sample

Sample Input
```2
6 0
4 4 3 3 3 4
5 1
3 1 2 3 4
```
Sample Output
```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.

1 ≤ n ≤ 10.
1 ≤ k ≤ 100000.

1 ≤ n ≤ 100.
1 ≤ k ≤ 1018.

### Sample

Sample Input
```3
2 2
3 4
3 6
```
Sample Output
```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:

``````
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:
```
```

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.

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

## Analysis — B. New Years Eve

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

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

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

## Analysis — D. Parentheses Order

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

## Statistics — A. Password Attacker

### Test set 1: 736 correct solutions (62.1% solve rate)

First
Bidhan 8:29
rais.fathin38 9:26
916852 9:55
nvdung149 9:57
Sakib 10:04

### Test set 2: 352 correct solutions (29.7% solve rate)

First
Bidhan 8:29
rais.fathin38 9:26
916852 9:55
nvdung149 9:57
Sakib 10:04

First
drazil 23:45
Zhanqi 41:42
916852 42:29
dovegx 52:40
asdsteven 53:00

First
drazil 23:45
Zhanqi 41:42
916852 42:29
dovegx 52:40
asdsteven 53:00

## Statistics — C. Card Game

### Test set 1: 750 correct solutions (63.2% solve rate)

First
amitsaharana 13:43
lllidan 24:02
krishnab 24:49
seraph 26:00
Jianh 26:14

First
kellynq 35:18
Rijul 35:36
Hewr 36:27
shuxi0ng 41:19
pulkitg10 47:42

## Statistics — D. Parentheses Order

### Test set 1: 679 correct solutions (57.3% solve rate)

First
canicula 15:58
nirwan 16:26
anurag.08.09 17:23
toughman 20:18
umangpopli 21:43

### Test set 2: 59 correct solutions (5.0% solve rate)

First
Kriiii 32:16
flashmt 45:19
anindamajumder3007 45:53
cacophonix 47:39
yumeno-ukihashi 49:12