# Google Kick Start Archive — Round G 2018 problems

## Overview

Thanks to everyone who participated!

Cast

Problem A (Product Triplets): Written by Akashdeep Nain and prepared by Satyaki Upadhyay‎.

Problem B (Combining Classes): Written by and prepared by Jonathan Irvin Gunawan.

Problem C (Cave Escape): Written by Zhang Chen and prepared by Kevin Tran.

Solutions, other problem preparation, reviews and contest monitoring by Akashdeep Nain, Gary Sham, Ian Tullis, Jonathan Irvin Gunawan, Kevin Tran, Lalit Kundu and Satyaki Upadhyay.

Analysis authors:

• Product Triplets: Jonathan Irvin Gunawan
• Combining Classes: Jonathan Irvin Gunawan
• Cave Escape: Himanshu Jaju

## A. Product Triplets

### Problem

Given N integers A1, A2, ..., AN, count the number of triplets (x, y, z) (with 1 ≤ x < y < z ≤ N) such that at least one of the following is true:

• Ax = Ay × Az, and/or
• Ay = Ax × Az, and/or
• Az = Ax × Ay

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line containing an integer N: the number of integers in array A. The second line consists of N integers Ai; the i-th of these is the value of the i-th integer, 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 triplets satisfying the condition given in the problem statement.

### Limits

1 ≤ T ≤ 30.
Time limit: 40 seconds per test set.
Memory limit: 1 GB.
0 ≤ Ai ≤ 2 × 105, for all i.

3 ≤ N ≤ 200.

3 ≤ N ≤ 7000.

### Sample

Sample Input
```4
6
5 2 4 6 3 1
6
2 4 8 16 32 64
3
1 1 1
3
200000 200000 200000
```
Sample Output
```Case #1: 1
Case #2: 6
Case #3: 1
Case #4: 0
```

In Sample Case #1, the only triplet satisfying the condition given in the problem statement is (2, 4, 5). The triplet is valid since the second, fourth, and fifth integers are 2, 6, and 3, and 2 × 3 = 6.

In Sample Case #2, the six triplets satisfying the condition given in the problem statement are: (1, 2, 3), (1, 3, 4), (1, 4, 5), (1, 5, 6), (2, 3, 5), (2, 4, 6).

In Sample Case #3, make sure you only count the triplet (1, 2, 3) once.

In Sample Case #4, there is no triplet satisfying the condition given in the problem statement since the product of any pair of integers in the array will not be in the array.

## B. Combining Classes

### Problem

Supervin is teaching N classes, which are numbered from 1 to N. After giving his most recent exam, he noticed that in each of his classes, the test scores of his students form a sequence of consecutive integers. Therefore, Supervin can summarize the scores for the i-th class as two integers Li and Ri. This means that the i-th class has Ri - Li + 1 students, and for each x (Li ≤ x ≤ Ri), there is exactly one student with score x.

Supervin would like to combine the scores from the students from all of his classes and sort the scores in non-increasing order. He has Q questions (numbered from 1 to Q) about this list; for the i-th question, he wants to know what the Ki-th highest score is. (If Ki is greater than the number of students, then the answer for the i-th question is 0.)

Can you help Supervin answer all of his questions? Since there may be many answers, instead of outputting all of them, output proof that you have answered them: the sum of (Si × i) for all 1 ≤ i ≤ Q, where Si is the answer to the i-th question.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case contains four lines. The first line contains two integers N and Q as described above. The next three lines each contain six integers in the following format, respectively:

• X1 X2 A1 B1 C1 M1
• Y1 Y2 A2 B2 C2 M2
• Z1 Z2 A3 B3 C3 M3
These values are used to generate Li, Ri, and Ki as follows:

We define:

• Xi = (A1 × Xi - 1 + B1 × Xi - 2 + C1) modulo M1, for i = 3 to N.
• Yi = (A2 × Yi - 1 + B2 × Yi - 2 + C2) modulo M2, for i = 3 to N.
• Zi = (A3 × Zi - 1 + B3 × Zi - 2 + C3) modulo M3, for i = 3 to Q.
We also define:
• Li = min(Xi, Yi) + 1, for i = 1 to N.
• Ri = max(Xi, Yi) + 1, for i = 1 to N.
• Ki = Zi + 1, for i = 1 to Q.

### 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 (Si × i) for all 1 ≤ i ≤ Q, where Si is the answer to the i-th question.

### Limits

1 ≤ T ≤ 100.
Time limit: 180 seconds per test set.
Memory limit: 1 GB.
1 ≤ N ≤ 4 × 105.
0 ≤ Ai < Mi, for all i.
0 ≤ Bi < Mi, for all i.
0 ≤ Ci < Mi, for all i.
0 ≤ X1 < M1.
0 ≤ X2 < M1.
0 ≤ Y1 < M2.
0 ≤ Y2 < M2.
0 ≤ Z1 < M3.
0 ≤ Z2 < M3.
1 ≤ Mi ≤ 109, for all i.

Q = 1.

1 ≤ Q ≤ 105.

### Sample

Note: there are additional samples that are not run on submissions down below.
Sample Input
```2
5 1
3 1 4 1 5 9
2 7 1 8 2 9
4 8 15 16 23 42
7 1
2 3 4 5 6 31
1 3 4 5 5 17
2 2 1 3 2 100
```
Sample Output
```Case #1: 7
Case #2: 28
```

In Sample Case #1, the generated arrays X, Y, Z are:

• X = [3, 1, 3, 0, 8].
• Y = [2, 7, 7, 2, 6].
• Z = [4].
Therefore,
• L = [3, 2, 4, 1, 7].
• R = [4, 8, 8, 3, 9].
• K = [5].
The students' scores for each of the classes are [3, 4], [2, 3, 4, 5, 6, 7, 8], [4, 5, 6, 7, 8], [1, 2, 3], and [7, 8, 9]. This means that the students' scores for all classes combined are [3, 4, 2, 3, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 1, 2, 3, 7, 8, 9]. If we sort them in non-increasing order, they are [9, 8, 8, 8, 7, 7, 7, 6, 6, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 1]. Therefore, the student with the 5th highest score has score 7. Thus, S = [7] and the answer is 7 × 1 = 7.

### 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
```2
5 5
3 1 4 1 5 9
2 7 1 8 2 9
4 8 15 16 23 42
1 2
0 0 0 0 0 1
0 0 0 0 0 1
0 1 0 0 0 2
```
Sample Output
```Case #1: 39
Case #2: 1
```

In Sample Case #1, every parameter is the same as Sample Case #1 except the value of Q. Therefore, the values of L and R, and the students' scores for all classes combined are still the same as Sample Case #1. However, the queries are now K = [5, 9, 40, 23, 12]. The students with the 5th, 9th, and 12th highest scores have scores of 7, 6, and 4, respectively. Since there are only 20 students, the 23rd and 40th students do not exist. Therefore, S = [7, 6, 0, 0, 4] and the answer is 7 × 1 + 6 × 2 + 0 × 3 + 0 × 4 + 4 × 5 = 7 + 12 + 20 = 39.

In Sample Case #2, the generated arrays X, Y, Z are:

• X = [0].
• Y = [0].
• Z = [0, 1].
Therefore,
• L = [1].
• R = [1].
• K = [1, 2].
Therefore, there is only one student, and S = [1, 0], so the answer is 1 × 1 + 0 × 2 = 1.

## C. Cave Escape

### Problem

Mr. Raven is stuck in a cave represented by a matrix of N rows and M columns, where rows are numbered from 1 to N from top to bottom, and columns are numbered from 1 to M from left to right. The cell at the i-th row and the j-th column is denoted by (i, j). Mr. Raven is currently at the cell (SR, SC), and the exit of the cave is located at the cell (TR, TC).

Some cells of the cave may contain obstacles. Mr. Raven cannot step into a cell that has an obstacle.
Other cells may contain traps. The first time that Mr. Raven enters a cell with a trap, he must spend a number of energy points equal to the strength of the trap. If he has fewer energy points than needed, he cannot enter the cell.
Moreover, some other cells may contain potions. The first time that Mr. Raven enters a cell with a potion, he gains energy points equal to the strength of the potion.

Mr. Raven initially has E energy points. He can move between cells that share an edge (not just a corner). On the exit cell, Mr. Raven can choose not to exit the cave and continue to explore the cave if he wants to. Can you help him find the maximum number of energy points he can have when he exits the cave, if it is possible to do so?

### 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 seven integers N, M, E, SR, SC, TR and TC as described above. The i-th of the next N lines describes the i-th row of the cave. Each line consists of M integers Vij; the j-th of these represents the cell in the j-th column of the i-th row. Each Vij can be one of the following

• 0: represents an empty cell.
• -100000: represents a cell with an obstacle.
• an integer between -99999 and -1 (both inclusive): represents a trap with strength -Vij.
• an integer between 1 and 99999 (both inclusive): represents a potion with strength Vij.

### 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 energy points that Mr. Raven can have when he reaches the exit of the cave. If it is not possible for Mr. Raven to reach the exit, output `-1`.

### Limits

1 ≤ T ≤ 100.
Time limit: 120 seconds per test set.
Memory limit: 1 GB.
1 ≤ N ≤ 100.
1 ≤ M ≤ 100.
0 ≤ E ≤ 100000.
1 ≤ SR ≤ N.
1 ≤ SC ≤ M.
1 ≤ TR ≤ N.
1 ≤ TC ≤ M.
(SR, SC) ≠ (TR, TC).
-100000 ≤ Vij < 100000, for all i, j.
At most 15 cells have -100000 < Vij < 0. (There are at most 15 traps.)
VSRSC = 0. (Mr. Raven's initial position is an empty cell.)
VTRTC = 0. (The cell with the exit is empty.)

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

There are no cells that have Vij > 0. (There are no potions in the cave.)

### Sample

Note: there are additional samples that are not run on submissions down below.
Sample Input
```2
4 4 100 1 1 4 4
0 0 0 0
0 0 0 0
0 0 0 -100000
0 0 -100000 0
2 2 100 1 1 2 2
0 0
0 0
```
Sample Output
```Case #1: -1
Case #2: 100
```

In Sample Case #1, it is not possible for Mr. Raven to reach the exit.

In Sample Case #2, there are no traps and no potions, which means Mr. Raven can reach exit and no matter what path he follows his energy will stay unchanged.

### 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
8 8 250 7 1 1 7
-100000 -100000 -100000 -100000 -100000 -100000 0 -100000
-100000 0 -100000 0 -400 0 0 -100000
-100000 100 -300 0 -100000 -300 -100000 -100000
-100000 0 -100000 500 -100000 250 0 -100000
-100000 -200 -100000 -100000 -100000 -100000 -100 -100000
-100000 0 -100000 0 0 50 50 -100000
0 0 -100 0 -100000 50 -100000 -100000
-100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000
```
Sample Output
```Case #1: 250
```

In Sample Case #1, the cave is as depicted in the following image where

• A cell with a positive integer x represents a potion with strength x.
• A cell with a negative integer y represents a trap with strength -y.
• Mr. Raven's initial position is in the cell with "You are here" text.

In this case, one of the optimal ways to reach the exit with maximum energy points is to

• Go to and destroy the trap at the cell (7, 3). 150 energy points remaining.
• Collect all three potions located at positions (6, 6), (6, 7) and (7, 6). 300 energy points remaining.
• Go to an destroy the trap at the cell (5, 7). 200 energy points remaining.
• Collect the potion at the cell (4, 6). 450 energy points remaining.
• Go to and destroy the trap at the cell (5, 2). 250 energy points remaining.
• Collect the potion at the cell (3, 2). 350 energy points remaining.
• Go to and destroy the trap at the cell (3, 3). 50 energy points remaining.
• Collect the potion at the cell (4, 4). 550 energy points remaining.
• Go to and destroy the trap at the cell (3, 6) and exit with 250 energy points remaining.

## Product Triplets: Analysis

### Small dataset

The Small dataset can be solved by complete search. We can check for each possible triplet (x, y, z) (with 1 ≤ x < y < z ≤ N) and check whether at least either one of Ax, Ay, or Az is the product of the other two. Each time we get a valid triplet, we increment our answer variable by one.

Since N ≤ 200 for this dataset, an O(N3) time solution will run within the time limit.

### Large dataset

Let us ignore indices i where Ai = 0 for the time being. In other words, let us assume that Ai > 0 for all i.

We can observe that for any three positive integers a, b, and c, if a × b = c, then a ≤ c and b ≤ c. Therefore, if we sort A in nondecreasing order, for each triplet (x, y, z) (with 1 ≤ x < y < z ≤ N), we only need to check whether Ax × Ay = Az. However, doing this naively will still be an O(N3) time solution.

We can optimize this solution by computing the number of z satisfying y < z and Ax × Ay = Az for each pair (x, y) in constant time. To do this, we can store the number of occurrences of each number in A in a hashmap.

If we design our nested loop such that we have y = {N .. 1} as our outer loop (and x = {y - 1 .. 1} as our inner loop), then we can update our hashmap for Ay just before we decrement the value of y. This is to make sure that our hashmap only contains the elements with indices larger than the current value of y. In other words, the algorithm looks something like:

``````
sort(A)
ans = 0
occurrences = hashmap()
for y : {N .. 1}
for x : {y - 1 .. 1}
ans = ans + occurrences.count(A[x] * A[y])
occurrences.update(A[y], occurrences.get(A[y]) + 1)
```
```

We should not forget that our algorithm so far ignores those indices i where Ai = 0. Suppose there are Z such indices (i.e., there are Z zeroes in A). We can make C(Z, 3) triplets using three zeroes, and C(Z, 2) × (N - Z) triplets using two zeroes and one non-zero.

Therefore, we get our final answer by summing the value of `ans` from our pseudocode, as well as C(Z, 3) and C(Z, 2) × (N - Z). This solution runs in O(N2) time.

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

## Combining Classes: Analysis

### Small dataset

Let us define a function f(x) as the number of students scoring more than or equal to x. We can compute f(x) in O(N) time by iterating through all classes.

Therefore, we can use binary search to find the largest x that satisfies f(x) ≥ K, which is the score of the K-th highest score. This solution runs in O(Q × N × log(109)) time.

### Large dataset

We can solve the Large dataset by compressing the scores first. That is, we map the existing values of Li and Ri onto a range [1, D], where D is the number of distinct values in Li and Ri. After compressing the scores, we can assume that the students' scores are between 1 and 2N.

For each possible score x, let cnt(x) be the number of students with score x. We can compute the values for all cnt(x) in O(N log(N)) using a range-update point-query data structure such as a segment tree. If we compute the suffix sum (similar to prefix sum, but we cumulate the sum backwards) of cnt(x), we will get the number of students scoring more than or equal to x, which is f(x).

Therefore, just as in our solution for the Small dataset, we can use binary search to find the largest x that satisfies f(x) ≥ K. However, note that the answer is not exactly x, since we compressed the scores earlier. The exact details of the implementation are left as an exercise.

This solution runs in O((N + Q) log N) time.

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

## Cave Escape: Analysis

### Small dataset

Since there are no available potions in this dataset, we cannot increase our energy points and hence we are looking for a path with the smallest sum of traps which leads us to the exit. We can consider the cells of the grid as the vertices of our graph and moves between adjacent cells as the edges, with the weight of an edge being the absolute value of the destination cell. Running Dijkstra's algorithm on this graph gives us the path with the smallest sum of traps to reach the exit in O(NM * log(NM)) time.

### Large dataset

We can observe that whenever are potions that we can take without going through traps, we should always take them all before going through a trap. After that, we have two recursive choices :

• Go to the exit if it is reachable without going through a trap.
• Go through a trap cell which is reachable without going through any other trap. This choice can help us get more potions or help us reach the exit cell. After we choose to go through a trap cell, we should again take all potions that we can reach without going through an unvisited trap, and then repeat the choice above.

Let CT be the count of traps in our test case. A naive recursive solution based on the above would be of the order of O(NM * CT!).

Observe that for a chosen subset of traps, all orderings of this subset have the same energy points (after going through all the traps), the same set of reachable unvisited traps and the same reachability of the exit cell. We can precompute these values by doing a graph search (BFS / DFS) on all 2CT subsets. To find the order of visiting the traps, we can use dynamic programming along with bitmasks. For every mask of traps, we can choose to go to the next unvisited reachable trap if its cost is not greater than our current energy points, or go to the exit cell if it is reachable and take the choice that maximizes our answer.

The time complexity for precomputation is O(NM * 2CT) and the time complexity of finding the ordering using dynamic programming is O(2CT * CT).

### Pseudocode

```  for every subset i in 2CT subsets precompute :
Ri := Reachable unvisited traps after visiting traps in subset i
Exiti := Denotes if exit cell is reachable from given subset of visited traps

ret := -1

// Go to exit if it is reachable

// Go to an unvisited reachable trap
ret := max(ret, MaxEnergy(mask | 2i))

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

## Statistics — A. Product Triplets

### Test set 1: 1852 correct solutions (99.5% solve rate)

First
xodiac 4:36
Kind maroon fox 5:07
Handsome olive dinosaur 5:08
vaibhav97 5:30
miniac 5:46

First
lizi 9:16
0ogway 10:32
alexwice 10:40
eatmore 12:36
sdnr1 13:11

## Statistics — B. Combining Classes

### Test set 1: 317 correct solutions (17.0% solve rate)

First
JeffreyHo 29:33
biltharesatyendra 30:49
U_Square 36:53
ankurdua15 39:26
eatmore 39:46

First
eatmore 39:46
lizi 46:48
Mahmoudian 48:02
Egor.Lifar 48:50
ayaze 53:19

## Statistics — C. Cave Escape

First
Hanstan 49:08
yash.15 49:52
mzzr 66:36
alpq 76:00
ulna 79:20

### Test set 2: 20 correct solutions (1.1% solve rate)

First
Mahmoudian 84:42
MemphiSqrt 86:18
AngusRitossa 100:56
ngochai94 101:25
ayaze 105:43