# Google Kick Start Archive — Round B 2016 problems

## A. Sherlock and Parentheses

### Problem

Sherlock and Watson have recently enrolled in a computer programming course. Today, the tutor taught them about the balanced parentheses problem. A string `S` consisting only of characters `(` and/or `)` is balanced if:

• It is the empty string, or:
• It has the form `(`S`)`, where S is a balanced string, or:
• It has the form S1S2, where S1 is a balanced string and S2 is a balanced string.

Sherlock coded up the solution very quickly and started bragging about how good he is, so Watson gave him a problem to test his knowledge. He asked Sherlock to generate a string S of L + R characters, in which there are a total of L left parentheses `(` and a total of R right parentheses `)`. Moreover, the string must have as many different balanced non-empty substrings as possible. (Two substrings are considered different as long as they start and end at different indexes of the string, even if their content happens to be the same). Note that S itself does not have to be balanced.

Sherlock is sure that once he knows the maximum possible number of balanced non-empty substrings, he will be able to solve the problem. Can you help him find that maximum number?

### 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: L and R.

### 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 answer, as described above.

### Limits

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

0 ≤ L ≤ 20.
0 ≤ R ≤ 20.
1 ≤ L + R ≤ 20.

0 ≤ L ≤ 105.
0 ≤ R ≤ 105.
1 ≤ L + R ≤ 105.

### Sample

Sample Input
```3
1 0
1 1
3 2
```
Sample Output
```Case #1: 0
Case #2: 1
Case #3: 3
```
In Case 1, the only possible string is `(`. There are no balanced non-empty substrings.
In Case 2, the optimal string is `()`. There is only one balanced non-empty substring: the entire string itself.
In Case 3, both strings `()()(` and `(()()` give the same optimal answer.
For the case `()()(`, for example, the three balanced substrings are `()` from indexes 1 to 2, `()` from indexes 3 to 4, and `()()` from indexes 1 to 4.

## B. Sherlock and Watson Gym Secrets

### Problem

Watson and Sherlock are gym buddies.

Their gym trainer has given them three numbers, A, B, and N, and has asked Watson and Sherlock to pick two different positive integers i and j, where i and j are both less than or equal to N. Watson is expected to eat exactly iA sprouts every day, and Sherlock is expected to eat exactly jB sprouts every day.

Watson and Sherlock have noticed that if the total number of sprouts eaten by them on a given day is divisible by a certain integer K, then they get along well that day.

So, Watson and Sherlock need your help to determine how many such pairs of (i, j) exist, where i != j. As the number of pairs can be really high, please output it modulo 109+7 (1000000007).

### 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 4 integers A, B, N and K, 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 required answer.

### Limits

1 ≤ T ≤ 100.
Time limit: 60 seconds per test set.
Memory limit: 1GB.
0 ≤ A ≤ 106.
0 ≤ B ≤ 106.

1 ≤ K ≤ 10000.
1 ≤ N ≤ 1000.

1 ≤ K ≤ 100000.
1 ≤ N ≤ 1018.

### Sample

Sample Input
```3
1 1 5 3
1 2 4 5
1 1 2 2
```
Sample Output
```Case #1: 8
Case #2: 3
Case #3: 0
```
In Case 1, the possible pairs are (1, 2), (1, 5), (2, 1), (2, 4), (4, 2), (4, 5), (5, 1), and (5, 4). In Case 2, the possible pairs are (1, 2), (1, 3), and (4, 1). In Case 3, No possible pairs are there, as i != j.

## C. Watson and Intervals

### Problem

Sherlock and Watson have mastered the intricacies of the language C++ in their programming course, so they have moved on to algorithmic problems. In today's class, the tutor introduced the problem of merging one-dimensional intervals. N intervals are given, and the `i`th interval is defined by the inclusive endpoints [Li, Ri], where Li ≤ Ri.

The tutor defined the covered area of a set of intervals as the number of integers appearing in at least one of the intervals. (Formally, an integer p contributes to the covered area if there is some j such that Lj`p`Rj.)

Now, Watson always likes to challenge Sherlock. He has asked Sherlock to remove exactly one interval such that the covered area of the remaining intervals is minimized. Help Sherlock find this minimum possible covered area, after removing exactly one of the N intervals.

### Input

Each test case consists of one line with eight integers N, L1, R1, A, B, C1, C2, and M. N is the number of intervals, and the other seven values are parameters that you should use to generate the other intervals, as follows:

First define `x1` = L1 and `y1` = R1. Then, use the recurrences below to generate `xi, yi` for `i` = 2 to N:

• `xi` = ( A*`xi-1` + B*`yi-1` + C1 ) modulo M.
• `yi` = ( A*`yi-1` + B*`xi-1` + C2 ) modulo M.
We define Li = `min(xi, yi)` and Ri = `max(xi, yi)`, for all `i` = 2 to N.

### 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 minimum possible covered area of all of the intervals remaining after removing exactly one interval.

### Limits

1 ≤ T ≤ 50.
Memory limit: 1GB.
0 ≤ L1R1 ≤ 109.
0 ≤ A ≤ 109.
0 ≤ B ≤ 109.
0 ≤ C1 ≤ 109.
0 ≤ C2 ≤ 109.
1 ≤ M ≤ 109.

#### Small dataset (Test set 1 - Visible)

Time limit: 30 seconds.
1 ≤ N ≤ 1000.

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

Time limit: 200 seconds.
1 ≤ N ≤ 5 * 105(500000).

### Sample

Sample Input
```3
1 1 1 1 1 1 1 1
3 2 5 1 2 3 4 10
4 3 4 3 3 8 10 10
```
Sample Output
```Case #1: 0
Case #2: 4
Case #3: 9
```
In case 1, using the generation method, the set of intervals generated are: {[1, 1]}. Removing the only interval, the covered area is 0.

In case 2, using the generation method, the set of intervals generated are: {[2, 5], [3, 5], [4, 7]}. Removing the first, second or third interval would cause the covered area of remaining intervals to be 5, 6 and 4, respectively.

In case 3, using the generation method, the set of intervals generated are: {[3, 4], [1, 9], [0, 8], [2, 4]}. Removing the first, second, third or fourth interval would cause the covered area of remaining intervals to be 10, 9, 9 and 10, respectively.

## D. Sherlock and Permutation Sorting

### Problem

Sherlock and Watson have already been introduced to sorting in their computer programming course. Now, Watson has always been curious about parallel computing and wants to sort a permutation of the integers 1 through N by breaking it into chunks, sorting the chunks individually, and then concatenating them.

For a permutation `p1, p2, ..., pN`, a chunk is a contiguous subarray of the permutation: i.e., a sequence of elements `pi, pi + 1, ..., pj`, for the elements at indexes i and j such that 1 ≤ `i``j`N.

Watson wants to partition his permutation into an ordered list of one or more chunks, without changing the order that the elements are in, in such a way that each element of the permutation is in exactly one chunk, and all elements in a chunk are smaller than all elements in any later chunk.
For example, for the permutation [2, 1, 3, 5, 4], these are the only four legal ways for Watson to break it into chunks: [[2, 1, 3], [5, 4]] or [[2, 1], [3, 5, 4]] or [[2, 1], , [5, 4]] or [[2, 1, 3, 5, 4]]. Watson is happiest when there are as many chunks as possible; we denote the maximum number of chunks for a permutation p as f(p). In this example, the maximum number of chunks is 3.

Watson wants to consider all permutations p of the numbers 1 through N, and find the sum of squares of f(p). Watson knows Sherlock might come in handy and comes to him for help, but Sherlock is as clueless as Watson and asks you for help. As the sum of squares can be large, please find it modulo M.

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

### 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 sum of squares of `f(p)` for all permutations `p` of size N, modulo M.

### Limits

Memory limit: 1GB.

1 ≤ M ≤ 109.

#### Small dataset (Test set 1 - Visible)

1 ≤ T ≤ 100.
Time limit: 20 seconds.
1 ≤ N ≤ 100.

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

1 ≤ T ≤ 20.
Time limit: 60 seconds.
1 ≤ N ≤ 5000.

### Sample

Sample Input
```3
1 2
2 4
3 7
```
Sample Output
```Case #1: 1
Case #2: 1
Case #3: 6
```
In Case 1, there is only one permutation. `f() * f() % 2` = 1.

In Case 2, there are two permutations.
`f([1, 2])` = 2.
`f([2, 1])` = 1.
`(22 + 12) % 4` = 1.

In Case 3, there are six permutations.
`f([1, 2, 3])` = 3.
`f([1, 3, 2])` = 2.
`f([2, 1, 3])` = 2.
`f([2, 3, 1])` = 1.
`f([3, 1, 2])` = 1.
`f([3, 2, 1])` = 1.
`(32 + 22 + 22 + 12 + 12 + 12) % 7` = 6.

## Analysis — A. Sherlock and Parentheses

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

## Analysis — B. Sherlock and Watson Gym Secrets

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

## Analysis — C. Watson and Intervals

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

## Analysis — D. Sherlock and Permutation Sorting

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

## Statistics — A. Sherlock and Parentheses

### Test set 1: 3846 correct solutions (98.9% solve rate)

First
jonathanirvings 2:46
ketan.bits 4:21
Sumeet.Varma 4:47
Raynger 4:47
praran26 4:51

### Test set 2: 2912 correct solutions (74.9% solve rate)

First
jonathanirvings 2:46
ketan.bits 4:21
Sumeet.Varma 4:47
Raynger 4:47
praran26 4:51

## Statistics — B. Sherlock and Watson Gym Secrets

### Test set 1: 1760 correct solutions (45.3% solve rate)

First
shuvojit1024 11:08
rezwan4029 12:08
rishivikram 12:44
TongWei...NJU 14:45
vippu95 16:20

### Test set 2: 268 correct solutions (6.9% solve rate)

First
ngochai94 25:40
rais.fathin38 25:41
nfssdq 31:51
jonathanirvings 33:28
alecsyde 34:37

## Statistics — C. Watson and Intervals

### Test set 1: 526 correct solutions (13.5% solve rate)

First
ankitsultana 41:01
fergus.dall 42:55
aj95 45:17
Theogry 46:49
scopeInfinity 47:25

### Test set 2: 152 correct solutions (3.9% solve rate)

First
Theogry 46:49
hdu.toraoh 49:26
rais.fathin38 49:39
ngochai94 50:51
bsbandme 57:21

## Statistics — D. Sherlock and Permutation Sorting

First
bsbandme 31:42
nfssdq 53:04
Theogry 61:56
terrance 65:02
pkqdsb90 76:06

### Test set 2: 15 correct solutions (0.4% solve rate)

First
bsbandme 31:42
nfssdq 53:04
stonebuddha 84:12
pandagmz 92:06
alecsyde 109:22