# Google Kick Start Archive — Round H 2018 problems

## Overview

This Kickstart round was easier than our previous rounds and began with Big Buttons, which was a simple problem solvable by the Trie data structure. Then came Mural, whose large dataset required an interesting insight, but a rather easy implementation. Finally, we had Let Me Count The Ways, whose large dataset involved the use of the inclusion-exclusion principle.

Thanks to everyone who participated!

Cast

Problem A (Big Buttons): Written by Akashdeep Nain and prepared by Lalit Kundu.

Problem B (Mural): Written by Zhang Che and prepared by Kevin Tran.

Problem C (Let Me Count The Ways): Written by Chao Li‎ and prepared by Yan Li.

Solutions, other problem preparation, reviews and contest monitoring by Akashdeep Nain, Anirudh GP, Celestine Lau, Ian Tullis, Jonathan Irvin Gunawan, Himanshu Jaju, Kevin Tran, Lalit Kundu, Satyaki Upadhyay, Tony Wong and Yan Li.

Analysis authors:

• Big Buttons: Himanshu Jaju
• Mural: Lalit Kundu
• Let Me Count The Ways: Jonathan Irvin Gunawan

## A. Big Buttons

### Problem

You are a contestant on a popular new game show and are playing for the grand prize!

There are two big buttons, a red one and a black one. You will make a sequence of exactly N button presses.

There are lots of different sequences of presses you could make, but there are P forbidden prefixes, each of length no greater than N. If you make a sequence of presses which begins with any of the forbidden sequences, you will not win the grand prize. It is fine for your sequence to contain one or more forbidden prefixes as long as they do not appear at the start of your sequence.

A winning sequence must consist of exactly N button presses and must not begin with one of the forbidden prefixes. How many different winning sequences are there?

### Input

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 two integers N and P, as described above. Then, there are P more lines, each of which contains a string of between 1 and N characters, inclusive, describing one of the forbidden sequences of presses. An `R` represents pressing the red button, whereas a `B` represents pressing the black button.

### 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 winning sequences, as desribed above.

### Limits

1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ P ≤ min(2N, 100).
Each forbidden prefix is between 1 and N characters long, inclusive.
No two forbidden prefixes will be the same.

1 ≤ N ≤ 10.

1 ≤ N ≤ 50.

### Sample

Note: there are additional samples that are not run on submissions down below.
Sample Input
```3
3 2
BBB
RB
5 1
R
4 3
R
B
RBRB
```
Sample Output
```Case #1: 5
Case #2: 16
Case #3: 0
```

In the first case, you must make a sequence of 3 presses. There are 8 possible sequences of three presses, but some of them will cause you to lose the game. They are listed below:

• `RBB`. This is forbidden since it starts with the first forbidden sequence (`RB`).
• `RBR`. This is forbidden since it starts with the first forbidden sequence (`RB`).
• `BBB`. This is forbidden since it starts with the second forbidden sequence (`BBB`).
Thus, there are only 5 winning sequences.

In the second case, you must make a sequence of 5 presses. There is only one forbidden sequence, which is `R`. This means that the first press must be `B`, and the next 4 presses can be either button. This gives a total of 16 different button presses.

In the third case, you must make a sequence of 4 presses. There are three forbidden sequences, but since every possible sequence begins with either `R` (the first forbidden sequence) or `B` (the second forbidden sequence), there are no winning sequences. So the answer is 0.

### Additional Sample - Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.
Sample Input
```1
50 5
BRBRBBBRBRRRBBB
BRBRBRRRBRRRBRB
BBBRBBBRBRRRBBB
BRBRBRRRBRRRB
BRBRBBBRBBBRB
```
Sample Output
```Case #1: 1125556309458944
```

## B. Mural

### Problem

Thanh wants to paint a wonderful mural on a wall that is N sections long. Each section of the wall has a beauty score, which indicates how beautiful it will look if it is painted. Unfortunately, the wall is starting to crumble due to a recent flood, so he will need to work fast!

At the beginning of each day, Thanh will paint one of the sections of the wall. On the first day, he is free to paint any section he likes. On each subsequent day, he must paint a new section that is next to a section he has already painted, since he does not want to split up the mural.

At the end of each day, one section of the wall will be destroyed. It is always a section of wall that is adjacent to only one other section and is unpainted (Thanh is using a waterproof paint, so painted sections can't be destroyed).

The total beauty of Thanh's mural will be equal to the sum of the beauty scores of the sections he has painted. Thanh would like to guarantee that, no matter how the wall is destroyed, he can still achieve a total beauty of at least B. What's the maximum value of B for which he can make this guarantee?

### Input

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 an integer N. Then, another line follows containing a string of N digits from 0 to 9. The i-th digit represents the beauty score of the i-th section of the wall.

### 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 maximum beauty score that Thanh can guarantee that he can achieve, as described above.

### Limits

1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.

2 ≤ N ≤ 100.

#### Large dataset (Test set 2 - Hidden)

For exactly 1 case, N = 5 × 106; for the other T - 1 cases, 2 ≤ N ≤ 100.

### Sample

Sample Input
```4
4
1332
4
9583
3
616
10
1029384756
```
Sample Output
```Case #1: 6
Case #2: 14
Case #3: 7
Case #4: 31
```

In the first sample case, Thanh can get a total beauty of 6, no matter how the wall is destroyed. On the first day, he can paint either section of wall with beauty score 3. At the end of the day, either the 1st section or the 4th section will be destroyed, but it does not matter which one. On the second day, he can paint the other section with beauty score 3.

In the second sample case, Thanh can get a total beauty of 14, by painting the leftmost section of wall (with beauty score 9). The only section of wall that can be destroyed is the rightmost one, since the leftmost one is painted. On the second day, he can paint the second leftmost section with beauty score 5. Then the last unpainted section of wall on the right is destroyed. Note that on the second day, Thanh cannot choose to paint the third section of wall (with beauty score 8), since it is not adjacent to any other painted sections.

In the third sample case, Thanh can get a total beauty of 7. He begins by painting the section in the middle (with beauty score 1). Whichever section is destroyed at the end of the day, he can paint the remaining wall at the start of the second day.

## C. Let Me Count The Ways

### Problem

To celebrate the anniversary of Googleland, N couples are going to go for a boat ride in a rowboat. The rowboat is very long, but it is only one person wide, so the people will sit in a line from front to back.

However, during a rehearsal of the voyage, the boat did not move! After investigating, the organizers found that some newlywed couples were not rowing, but writing love poems for each other the whole time. Specifically, there are M pairs of newlywed couples. If the two members of a newlywed couple are sitting next to each other, they will be so busy writing poems that they will not row.

Now the organizers have come to you, the smartest person in Googleland, to ask, how many possible ways are there to arrange all 2N people on the rowboat, such that for each of the M newlywed couples, the two members are not sitting next to each other? Two ways are different if there is some position in the boat at which the two ways use different people. Notice that for the purpose of counting the number of ways, the two members of a couple are not considered to be interchangeable. Since the number can be very large, the organizers only want to know the value of the answer modulo 1000000007(109+7).

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line with two integers N and M as described above.

### 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 possible arrangements, modulo 1000000007(109+7).

### Limits

1 ≤ T ≤ 100.
Time limit: 40 seconds per test set.
Memory limit: 1 GB.

1 ≤ MN ≤ 100.

1 ≤ MN ≤ 100000.

### Sample

Sample Input
```5
2 1
2 2
3 1
3 2
10 5
```
Sample Output
```Case #1: 12
Case #2: 8
Case #3: 480
Case #4: 336
Case #5: 560963525
```

In Sample Case #1, there are 2 couples. To make the description simpler, we use the characters `A` and `a` to represent the newlywed couple, and `B` and `b` to represent the other couple. Per the rules of the problem, `A` and `a` cannot be adjacent. There are 12 ways to arrange the four people:
`ABab` `ABba` `AbaB` `AbBa`
`aBAb` `aBbA` `abAB` `abBA`
`BAba` `BabA` `bABa` `baBA`

In Sample Case #2, both two couples are newlywed couples, so `A` and `a` cannot be adjacent, and `B` and `b` cannot be adjacent. They can be arranged in the following 8 ways:
`ABab` `AbaB` `aBAb` `abAB`
`BAba` `BabA` `bABa` `baBA`

## Big Buttons: Analysis

### Small dataset

Since we have 2 choices at every step, there are 2N possible strings of length N. We can generate all of these strings in O(2N) time using a naive recursion. For each string, we need to check if any of the P strings is its prefix. A simple implementation of the above would run in O(2N × P × N) time for each case. Since N ≤ 10 in this dataset, this is fast enough.

### Large dataset

In this dataset, since N can be as large as 50, it is not feasible to generate all 2N strings. The main idea in solving the Large dataset is to find the number of invalid strings of length N and subtract it from the total number of strings (2N).

If a forbidden prefix has length L, we have 2(N - L) invalid strings of length N with that prefix. Also, if we have two strings A and B, and A is a prefix of B, then all strings that have B as their prefix will also have A as their prefix. So we can remove all forbidden prefixes that themselves begin with a different forbidden prefix to avoid overcounting the sum of invalid strings.

We can now easily count the sum of invalid strings by finding the number of invalid strings for each remaining forbidden prefix. We can remove redundant forbidden prefixes in O(P × P × N) time, and find the counts of strings with the remaining forbidden prefixes in O(P × N) time, so the overall running time is O(P2N). This is fast enough to solve the Large data set, but can you see how to improve the first step to O(P × N) time by using a trie?

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

## Mural: Analysis

We can observe that we will have painted ceil(N/2) sections in the end, and all these sections would form a contiguous subarray of the input array. Since painting and destroying is done alternatively, it might not be possible to paint any subarray of our choice. Our objective is to find the maximum subarray sum among the set of "paintable" subarrays.

### Small dataset

An intuitive approach would rely on Dynamic Programming and try to define a DP state that could encapsulate the state of the painted and the destroyed sections at any point in time. Note that painted section is contiguous, and the destroyed sections are prefixes and suffixes of the input array.
Hence, we can define f(i, j, l, r) as the maximum possible achievable score if i and j are the lengths of the destroyed prefix and suffix, respectively; whereas l and r denote the left and the right boundaries of the painted subarray. A recurrence can easily be derived by considering at most four further possibilities: we have two ways to extend the mural (by painting the section either to the left or to the right of the already painted boundary), and two ways to extend the destroyed part (either the prefix or the suffix).
Note that it would seem that there are O(N4) different valid states in the above approach, but that is not the case since the sum of lengths of painted and destroyed parts is always the same. We can get rid of the index of the right boundary of the painted subarray (i.e. variable r), as it can be implicitly derived from the variables i and j.
The overall complexity of this approach is O(N3) and that will suffice for the Small dataset.

### Large dataset

The solution to the Large dataset relies on an interesting observation that all possible contiguous subarrays of length ceil(N/2) are "paintable". If we can prove this fact, we can simply do an O(N) rolling window approach over all such subarrays and output the maximum possible sum.

Let's think of an intuitive way to prove this. Say, if we paint the i-th section on the first day, what could be the smallest possible index of the left boundary of the mural in the worst case? To achieve the smallest possible index, we will always extend the boundary on the left side; and in the worst case the flood can always extend the prefix, allowing us to paint only the indices after index ceil(i/2)(inclusive). And similarly, there would be an upper limit on the maximum possible index of the right boundary.
This means that given the desirable left boundary of the mural, we can figure out the "central point" from which we would begin painting. Now, irrespective of the sequence of destructions, we can always meet the desirable left boundary by always extending our subarray to the left whenever a section on the left is destroyed. Similar arguments can be applied to the right boundary.

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

## Let Me Count The Ways: Analysis

### Small dataset

We can solve the Small dataset using dynamic programming. Let f(x, y, z) (x and y are non-negative integers, while z is 0 or 1) be the number of ways to arrange a seating order for x non-newlywed people and y newlywed couples (thus the total is x + 2y people and seats), such that:

• There is no newlywed couple for which the two members are seated next to each other, and
• If z = 1, then one of the x non-newlywed people must not sit in the first remaining unassigned seat.

The base case of this function occurs when there are no people left (i.e. x = y = 0), then f(x, y, z) = 1. Otherwise, f(x, y, 0) can be defined recursively as follows:

• We can put one of the x non-newlywed people in the first seat. Therefore, we need to assign the remaining x - 1 non-newlywed people and y newlywed couples. This contributes x × f(x - 1, y, 0) to the total number of ways captured by f(x, y, 0).
• We can put one of the member of the y newlywed couples in the first seat. The other member of this couple can be considered as an additional non-newlywed person. Therefore, we need to assign the remaining x + 1 non-newlywed people and y - 1 newlywed couples. However, note that this additional person cannot be seated next to his/her newlywed partner (i.e. cannot be seated on the first unassigned seat after his/her newlywed partner sit down). Therefore, this contributes 2 × y × f(x + 1, y - 1, 1) to the total number of ways captured byf(x, y, 0).

Therefore, f(x, y, 0) = x × f(x - 1, y, 0) + 2 × y × f(x + 1, y - 1, 1). The cases for f(x, y, 1) are similar, except that we can't put one of the x non-newlywed people in the first seat. Therefore, f(x, y, 1) = (x - 1) × f(x - 1, y, 0) + 2 × y × f(x + 1, y - 1, 1).

This dynamic programming solution runs in O(N × M) space and time.

### Large dataset

We can solve the Large dataset using the inclusion-exclusion principle. Since M can be up to 100000, it is infeasible to iterate all possible subset of the newlywed couples. However, we can observe that the number of ways to arrange a seating order such that the newlywed couple P sits adjacently (i.e. the two members of a newlywed couple P sit next to each other) is the same as the number of ways to arrange a seating order such that the newlywed couple Q sits adjacently. In general, for a fixed number k of newlywed couples, regardless of which particular couples we choose, the number of seating orders in which all of those k newlywed couples have their two members adjacent is the same.

Therefore, we can define a function g(k) as the number of ways to arrange a seating order such that for each of the first k newlywed couples, the two members of a couple are sitting next to each other. g(k) can be computed by multiplying the following:

• The number of ways these newlywed couples sit. Since the members of each newlywed couple must sit next to each other, we can treat each newlywed couple as if it were one person. Therefore, there are 2N - k seats for k couples. Since the couples are not identical and the order of the couples matters, there are C(2N - k, k) × k! ways, where C(n, k) is the number of ways of picking k unordered outcomes from n possibilities (i.e. "n choose k").
• The number of ways of ordering two people in each newlywed couple, which is 2k.
• The number of ways in which the remaining people can sit, which is (2(N - k))!.
Therefore, g(k) = C(2N - k, k) × k! × 2k × (2(N - k))!

Finally, we should not forget that g(k) counts the number of ways to arrange a seating order such that the first k newlywed couples sit adjacently. To consider all subset of newlywed couples of size k, we need to multiply g(k) by C(M, k).

Putting all the pieces together, the answer we are looking for is Σ (-1)k × g(k) × C(M, k) for all 0 ≤ kM. By precomputing the value of powers of two, factorials, and their modular inverses, this answer can be computed in O(N + M) space and time.

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

## Statistics — A. Big Buttons

### Test set 1: 1687 correct solutions (95.6% solve rate)

First
alexwice 4:52
mcpower 4:59
sdssudhu 7:48
ONP 7:58
LLI_E_P_JI_O_K 8:04

### Test set 2: 1476 correct solutions (83.6% solve rate)

First
alexwice 4:52
mcpower 4:59
sdssudhu 7:48
ONP 7:58
LLI_E_P_JI_O_K 8:04

## Statistics — B. Mural

### Test set 1: 1338 correct solutions (75.8% solve rate)

First
dredwerkz 9:14
TrueBamboo 16:27
ONP 17:33
LLI_E_P_JI_O_K 18:01
Healthy tan jackalope 18:39

### Test set 2: 1014 correct solutions (57.5% solve rate)

First
dredwerkz 9:14
TrueBamboo 16:27
ONP 17:33
LLI_E_P_JI_O_K 18:01
Chandnani 19:22

First
deva2802 15:19
cuom1999 22:03
rapel 22:04
Origenes 25:01
Mahmoudian 29:39

First
deva2802 15:19
cuom1999 22:03
rapel 22:04
Mahmoudian 29:39
ayaze 31:07