Google Kick Start Archive — Round D 2020 problems

Overview

Thank you for participating in Kick Start 2020 Round D.

Cast

Breaking Records: Written by Kevin Tran and prepared by Jonathan Irvin Gunawan.

Alien Piano: Written by Gregory Yap and prepared by Swapnil Gupta.

Beauty of Tree: Written by Saurabh Joshi and prepared by Sherry Wu.

Locked Doors: Written by Kevin Tran and prepared by Anson Ho.

Solutions, other problem preparation, reviews and contest monitoring by Akul Siddalingaswamy, Anson Ho, Anushi Maheshwari, Bohdan Pryshchenko, Cristhian Bonilha, Gregory Yap, Hsin-Yi Wang, Jared Gillespie, Jonathan Irvin Gunawan, Kevin Tran, Krists Boitmanis, Lalit Kundu, Lizzie Sapiro, Michał Łowicki, Nikhil Hassija, Paul Hoang, Raihat Zaman Neloy, Ruoyu Zhang, Sadia Atique, Sanyam Garg, Saurabh Joshi, Shantam Agarwal, Sherry Wu, Sudarsan Srinivasan, Swapnil Gupta, Vikash Dubey, Vipin Singh, and Wajeb Saab.

Analysis authors:

• Breaking Records: Cristhian Bonilha
• Alien Piano: Krists Boitmanis
• Beauty of Tree: Akul Siddalingaswamy
• Locked Doors: Swapnil Gupta

A. Record Breaker

Problem

Isyana is given the number of visitors at her local theme park on N consecutive days. The number of visitors on the i-th day is Vi. A day is record breaking if it satisfies both of the following conditions:

• The number of visitors on the day is strictly larger than the number of visitors on each of the previous days.
• Either it is the last day, or the number of visitors on the day is strictly larger than the number of visitors on the following day.
Note that the very first day could be a record breaking day!

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. The second line contains N integers. The i-th integer is Vi.

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 record breaking days.

Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
0 ≤ Vi ≤ 2 × 105.

1 ≤ N ≤ 1000.

Test Set 2

1 ≤ N ≤ 2 × 105 for at most 10 test cases.
For the remaining cases, 1 ≤ N ≤ 1000.

Sample

Sample Input
```4
8
1 2 0 7 2 0 2 0
6
4 8 15 16 23 42
9
3 1 4 1 5 9 2 6 5
6
9 9 9 9 9 9
```
Sample Output
```Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0
```

In Sample Case #1, the bold and underlined numbers in the following represent the record breaking days: 1 2 0 7 2 0 2 0.

In Sample Case #2, only the last day is a record breaking day.

In Sample Case #3, the first, the third, and the sixth days are record breaking days.

In Sample Case #4, there is no record breaking day.

B. Alien Piano

Problem

An alien has just landed on Earth, and really likes our music. Lucky for us.

The alien would like to bring home its favorite human songs, but it only has a very strange instrument to do it with: a piano with just 4 keys of different pitches.

The alien converts a song by writing it down as a series of keys on the alien piano. Obviously, this piano will not be able to convert our songs completely, as our songs tend to have many more than 4 pitches.

The alien will settle for converting our songs with the following rules instead:

• The first note in our song can be converted to any key on the alien piano.
• For every note after,
• if its pitch is higher than the previous note, it should be converted into a higher-pitched key than the previous note's conversion;
• if lower, it should be converted into a lower-pitched key than the previous note's conversion;
• if exactly identical, it should be converted into the same key as the previous note's conversion.
Note: two notes with the same pitch do not need to be converted into the same key if they are not adjacent.

What the alien wants to know is: how often will it have to break its rules when converting a particular song?

To elaborate, let us describe one of our songs as having K notes. The first note we describe as "note 1", the second note "note 2", and the last note "note K."
So note 2 comes immediately after note 1.
Now if note 2 is lower than note 1 in our version of the song, yet converted to an equally-pitched or lower-pitched key (relative to note 2's conversion) in the alien's version of the song, then we consider that a single rule break.
For each test case, return the minimum amount of times the alien must necessarily break one of its rules in converting that song.

Input

The first line of the input gives the number of test cases, T. T test cases follow.
Each test case consists of two lines.
The first line consists of a single integer, K.
The second line consists of K space-separated integers, A1, A2 ... AK, where Ai refers to the pitch of the i-th note for this 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 minimum number of times that particular test case will require the alien to break its own rules during the conversion process.

Limits

Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ Ai ≤ 106.

Test Set 1

Time limit: 20 seconds.
1 ≤ K ≤ 10.

Test Set 2

Time limit: 40 seconds.
1 ≤ K ≤ 104.

Sample

Sample Input
```2
5
1 5 100 500 1
8
2 3 4 5 6 7 8 9
```
Sample Output
```Case #1: 0
Case #2: 1
```

We will use the notation A, B, C, D for the alien piano keys where A is the lowest note, and D is the highest. In sample case #1, the alien can simply map our song into the following sequence: `A B C D C` and this correctly reflects all the following:

• our first note with pitch 1 maps to A,
• our second note with pitch 5 maps to its key B. 5 > 1, and B is a higher key than A,
• our third note with pitch 100 maps to its key C. 100 > 5, and C is a higher key than B,
• our fourth note with pitch 500 maps to its key D. 500 > 100, and D is a higher key than C,
• our fifth note with pitch 1 maps to its key C. 1 < 500, and C is a lower key than D.
So none of the rules are broken. Note: `A B C D C` is not the only way of conversion. `A B C D A` or `A B C D B` are also eligible conversions.

In sample case #2, the only conversion sequence that provides the minimal result of 1 rule broken is: `A B C D A B C D`. Notably, the rule break comes from the fact that our 4th note with pitch 4 is lower than our 5th note with pitch 5, but A is a lower key than D.

C. Beauty of tree

Problem

Amadea and Bilva are decorating a rooted tree containing N nodes, labelled from 1 to N. Node 1 is the root of the tree, and all other nodes have a node with a numerically smaller label as their parent.

Amadea and Bilva's decorate the tree as follows:

• Amadea picks a node of the tree uniformly at random and paints it. Then, she travels up the tree painting every A-th node until she reaches the root.
• Bilva picks a node of the tree uniformly at random and paints it. Then, she travels up the tree painting every B-th node until she reaches the root.

The beauty of the tree is equal to the number of nodes painted at least once by either Amadea or Bilva. Note that even if they both paint a node, it only counts once.

What is the expected beauty of the tree?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the three integers N, A and B. The second line contains N-1 integers. The i-th integer is the parent of node i+1.

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 expected beauty of the tree.

`y` will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

Limits

Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ AN.
1 ≤ BN.

Test Set 1

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

Test Set 2

Time limit: 40 seconds.
For up to 5 cases, 1 ≤ N ≤ 5 × 105.
For all other cases, 1 ≤ N ≤ 100.

Sample

Sample Input
```3
8 2 3
1 1 3 4 4 3 4
10 3 4
1 1 1 1 1 1 1 1 1
4 3 1
1 2 3
```
Sample Output
```Case #1: 2.65625
Case #2: 1.9
Case #3: 2.875
```

The trees for each sample case are shown in the diagram below. A few example colourings for sample case #1 are shown below.

• If Amadea picks node 5 and Bilva picks node 8, then together they paint 4 unique nodes: Amadea paints nodes 5 and 3, while Bilva paints nodes 8 and 1.
• If Amadea picks node 7 and Bilva picks node 6, then together they paint 3 unique nodes: Amadea paints nodes 7 and 1, while Bilva paints nodes 6 and 1 (note that Amadea painted node 1 as well).

D. Locked Doors

Problem

Bangles is preparing to go on a tour of her local museum. The museum is made up of N rooms in a row, numbered from 1 to N from left to right. The rooms are connected by N-1 locked doors, each connecting a pair of adjacent rooms. Each door has a difficulty level indicating how difficult it is for Bangles to open the door. No two doors will have the same difficulty level. The door between the i-th room and (i+1)-th room has difficulty level Di.

Bangles will pick one of the rooms to start in, and visit each of the rooms in the museum one at a time, taking pictures as she goes. She takes a picture in her starting room, then she repeats the following procedure until she has taken a picture in all the rooms: Of the two locked doors available to her, she will open the door with the lower difficulty level and take a picture in the newly unlocked room. If there is only one locked door available to her, then she will unlock that door. Once a door is unlocked, it remains unlocked.

Bangles is not yet sure which room she would like to start in, so she needs you to answer Q queries. For the i-th query, she would like to know: What is the Ki-th room that she will take a picture in if she starts in the Si-th room?

Input

The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case contains the two integers N and Q. The second line contains N-1 integers, describing the locked doors. The i-th integer (starting from 1) is Di. Then, Q lines follow, describing the queries. The i-th of these lines contains the two integers Si and Ki.

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 a list of the answers for the Q queries in order, separated by spaces.

Limits

Time limit: 40 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ Di ≤ 105, for all i.
All Di are distinct.
1 ≤ SiN, for all i.
1 ≤ KiN, for all i.

2 ≤ N ≤ 1000.
1 ≤ Q ≤ 1000.

Test Set 2

2 ≤ N ≤ 105 and 1 ≤ Q ≤ 105 for at most 20 test cases.
For the remaining cases, 2 ≤ N ≤ 1000 and 1 ≤ Q ≤ 1000.

Sample

Sample Input
```2
5 4
90 30 40 60
3 4
3 1
1 5
4 3
10 2
6 2 4 5 9 30 7 1 8
6 8
6 8
```
Sample Output
```Case #1: 5 3 5 2
Case #2: 8 8
```

In sample case #1, there are four queries:

• In the first query, Bangle takes pictures in the rooms in the order 3, 2, 4, 5 and 1, so the answer is 5.
• In the second query, Bangle takes pictures in the rooms in the order 3, 2, 4, 5 and 1, so the answer is 3.
• In the third query, Bangle takes pictures in the rooms in the order 1, 2, 3, 4 and 5, so the answer is 5.
• In the fourth query, Bangle takes pictures in the rooms in the order 4, 3, 2, 5, and 1, so the answer is 2.

In sample case #2, there are two queries:

• In the first query, Bangle takes pictures in the rooms in the order 6, 5, 4, 3, 2, 1, 7, 8, 9 and 10, so the answer is 8.
• The second query is the same as the first, so the answer is also 8.

Analysis — A. Record Breaker

We can check whether the current element is the last element and, if not, if it is greater than the next element in constant time. To check whether i is a record breaking day, we also need to check whether the number of visitors of day i is greater than number of visitors from all the previous days.

Test Set 1

For each element j such that (1 <= j < i), check that the number of visitors on day j are less than number of visitors on day i. Hence, for each day we would compare it with all the previous days and it would take O(N) time. Therefore, for N days, the time complexity of this solution would be O(N^2).

Test Set 2

However that wouldn't be fast enough for Test Set 2, so we need a faster approach. Instead of comparing the number of visitors of day i against all the previous days one by one, we can compare the number of visitors of day i against the greatest number of visitors from all previous days. That reduces our processing time for each day from O(N) to O(1). Therefore, for N days, the time complexity of this solution would be O(N), which is sufficiently fast for both Test Set 1 and Test Set 2.

Sample Code (C++)
``````
int countRecordBreakingDays(vector<int> visitors) {
int recordBreaksCount = 0;
int previousRecord = 0;
for(int i = 0; i < checkpoints.size(); i++) {
bool greaterThanPreviousDays = i == 0 || visitors[i] > previousRecord;
bool greaterThanFollowingDay = i == checkpoints.size()-1 || visitors[i] > visitors[i+1];
if(greaterThanPreviousDays && greaterThanFollowingDay) {
recordBreaksCount++;
}
previousRecord = max(previousRecord, visitors[i]);
}
return recordBreaksCount;
}
``````
Test Data
info We recommend that you practice debugging solutions without looking at the test data.

Analysis — B. Alien Piano

Test Set 1

For the small test set, one can generate all possible conversions recursively and select the one with the smallest number of rule violations as the answer. Since each note can be converted to four possible notes in the alien scale, this results into 4K combinations to be tested and O(4K) time complexity.

Test Set 2

Dynamic Programming Solution

Let DP[i, j] be the minimum number of rule violations required to convert the first i notes A1, A2, ..., Ai such that the i-th note Ai is converted to note j of the alien piano (1 ≤ j ≤ 4). Then the answer is the minimum DP[K, j] over all j, 1 ≤ j ≤ 4.

The table DP[i, j] can be computed using dynamic programming as follows.
(1) DP[1, j] = 0 for all j.
(2) For i > 1, DP[i, j] = min{ DP[i - 1, j'] + P(i, j', j) | 1 ≤ j' ≤ 4 }. Here P(i, j', j) is a binary penalty term accounting for a rule violation between the notes Ai-1 and Ai. For example, if Ai-1 > Ai, then P(i, j', j) = 1 whenever j' ≤ j and P(i, j', j) = 0 otherwise.

Since each entry of the table is calculated using a constant number of operations, the overall time complexity of the algorithm is O(K), which is okay to pass the large test set.

Greedy Solution

Let us say that a sequence of pitches is playable if it can be converted to the alien piano notes without violating any rules. Our goal here is to split the given sequence of pitches into as few playable fragments as possible.

We can take the longest playable prefix of the sequence as the first fragment of the split. In this way, the remainder of the sequence is as short as possible, and therefore requires potentially fewer rule violations.

Now let us characterise the playable sequences. Note that repeated notes of the same pitch do not affect the playability of the sequence, therefore, without loss of generality, suppose that any two consecutive notes are at a different pitch. Let us say that two consecutive notes form an upward step if the second note has a higher pitch than the first. Otherwise, we call it a downward step.

Clearly, a sequence of notes is not playable if it contains more than three consecutive upward or downward steps, as we would run out of the alien scale. Otherwise, the sequence is playable and we can convert it using this simple strategy (assuming the note names A, B, C, and D of the alien piano from the lowest to the highest note):
(1) If the first step is upward, convert the first note to A.
(2) If the first step is downward, convert the first note to D.
(3) If three consecutive notes form an upward step followed by a downward step, convert the second note to D.
(4) If three consecutive notes form a downward step followed by an upward step, convert the second note to A.
(5) In all other cases, convert a note one step higher or lower than the note before depending on whether they form an upward or downward step.
Since any maximal sequence of upward steps starts at A and has no more than three steps (and similarly for any maximal sequence of downward steps), we will never leave the alien scale.

The following diagram illustrates the process of splitting the sequence (1, 8, 9, 7, 6, 5, 4, 3, 2, 1, 3, 2, 1, 3, 5, 7) into two playable fragments. Since the subsequence (9, 7, 6, 5, 4) consists of four downward steps, the sequence needs to be split between notes 5 and 4.

According to the analysis above, a single pass through the given sequence of notes maintaining the current number of consecutive upward and downward steps results in an O(K) solution, where K is the number of notes in the sequence. As soon as the number of upward or downward steps exceeds 3, we have to split the sequence by violating the rules and start a new fragment. A Python code snippet is included below for clarity.

```def solve():
k = input()
a = map(int, raw_input().split())
# Filter out repeated notes.
a = [a[i] for i in xrange(0, k) if i == 0 or a[i - 1] != a[i]]
upCount = 0
downCount = 0
violations = 0
for i in xrange(1, len(a)):
if a[i] > a[i - 1]:
upCount += 1
downCount = 0
else:
downCount += 1
upCount = 0
if upCount > 3 or downCount > 3:
violations += 1
upCount = downCount = 0
return violations
```
Test Data
info We recommend that you practice debugging solutions without looking at the test data.

Analysis — C. Beauty of tree

For a given node, the P(visited by either Amadea or Bilva) = 1 - P(not visited by Amadea nor Bilva).
This leads to P(visited by either Amadea or Bilva) = 1 - ((1-P(visited by Amadea)) * (1-P(visited by Bilva)))
i.e. For a given node, note that events of visited-by-Amadea and visited-by-Bilva are mutually independent events, and hence P(being visited by either Amadea or Bilva) = P(visited by Amadea) + P(visited by Bilva) - (P(visited by Amadea)*P(visited by Bilva))

Given the above formula, our goal now is to find out P(visited by Amadea) and P(visited by Bilva) for every node in the tree. We can use DFS in order to do this.
Firstly, let's define 2 variables visits_a[] and visits_b[] where visits_a[i] and visits_b[i] denote the number of visits to node-i across all paths starting from any node in the subtree of node i with skips A and B respectively.

Now, the first DFS run would be from node-1 to compute visits_a[]. As we perform this DFS, we can keep a track of the path that has been taken so far, let's say path_taken[]. As we enter a node-i, we add it to path_taken[] and call DFS on it's children. Once we come back to node-i, we remove it from the path_taken[] and increment visit_a[i] by 1. Note that this increment is for the path leading from node-i to itself. Next, we check if there is some node-j which is A skips behind node-i. Using path_taken[], we check to see if such a node is present and increment the visits_a[node-j] by visits_a[i]. At the end of this DFS run, we have the total visit count for all nodes with the skip distance of A. Now, dividing visits_a[] by N gives us the P(visited by Amadea) for each node in the tree. Repeat the above process for to compute visits_b[] and obtain P(visited by Bilva) for every node in the tree.

With P(visited by Amadea) and P(visited by Bilva) computed for every node in the tree, computing and summing over P(being visited by either Amadea or Bilva) for each node will give us the answer. Since DFS takes linear time in the number of vertices, the time complexity of the solution is O(N).

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

Analysis — D. Locked Doors

Test Set 1

We can say that the rooms which Bangles has covered in the journey will always form a contiguous subarray. This is because, to go from room i to room j, Bangles must have unlocked the doors that occur between room i and room j once, only then Bangles would be able to move to room j. At any point of time, if Bangles has visited rooms from l to r, Bangles need to make a decision whether to go from room r to r+1 or from room l to l-1 depending which door has lower difficulty. Accordingly, Bangles can update l and r. For deciding which room to go next, it would take constant time. Thus, for taking K pictures, it would take O(K) time. K can be at most N. For each query, it would take O(N) time to process the query. Thus, overall complexity of the solution would be O(Q * N).

Test Set 2

The naive solution would time out for the constraints of test set 2. Thus, we can use the following approach to solve this:

Let InterestingLeft[i] be the door which is the closest door to the left of door i and has difficulty higher than door i. In case there is no such door, assign -1 to it. Similarly, let InterestingRight[i] be the door which is the closest door to the right of door i and has difficulty higher than door i. In case there is no such door, assign -1 to it. InterestingLeft[i] and InterestingRight[i] can be calculated by using the stack method in O(N) time.

After we are done unlocking the door i and all doors with difficulty lower than D[i] between doors InterestingLeft[i] and InterestingRight[i], we would either unlock door InterestingLeft[i] or door InterestingRight[i] next depending on which one has lower difficulty. If we have have only one choice, then we unlock that door itself. For generality, let us assume the next door that would be unlocked would be j. j would be equal to either InterestingLeft[i] or InterestingRight[i].

Let us construct a tree using the given relations. For each door i, we find such j and assign j as parent of i. We can see that a node can have at most 2 children: at most one from the left side and at most one from the right side. Thus the relations would form a Cartesian tree. From the given tree, we can make the following observations:

• If a node has only one child:
• If the starting node is inside the subtree of current node, then the node will be visited only after all the nodes in its subtree have been visited.
• If the starting node is outside the subtree of current node, then first the node will be visited and after that the nodes in its subtree will be visited.
• If a node has two children:
• If the starting node is in left subtree, then first all the nodes in subtree of left child will be visited, then the current node will be visited, and finally the subtree of right child will be visited.
• Similarly, if the starting node is in right subtree, then first all the nodes in subtree of right child will be visited, then the current node will be visited, and finally the subtree of left child will be visited.

Building this tree can be done in O(N) time because assigning the parents for each node according to InterestingLeft[i] and InterestingRight[i] takes constant time.

Let the subtree size of node i be Size[i]. Consider a query with starting room S and we need to find K-th room we will be in. Let the starting door X be the first door that we unlock. This can be determined in constant time by comparing the doors adjacent to room S. In the constructed tree, if size[X] < K, the whole subtree will be visited and we will move to its parent node. This will continue until we reach the node u such that size[u] ≥ K, so that we know that our answer lies within this subtree. To find such node, we can use the binary lifting approach similar to finding the lowest common ancestor between two nodes in a tree. This can be precomputed in O(N * log(N)) time. In a query we have following cases:

• If size[X] ≥ K, then:
• If X is the door left to S, then answer is S - K.
• Otherwise, find node Y which is the first node on path from X to root such that size[Y] ≥ K. This can be done using binary lifting in O(logN). Now we can find the answer in constant time as follows:
• If X < Y, then answer is Y + K - size[leftChild[Y]]
• Otherwise, answer is Y + 1 - (K - size[rightChild[Y]])

Each query takes O(logN) time and building the binary tree and preprocessing for binary lifting takes O(N logN) time. Hence, overall complexity of the solution is O(N logN + Q logN).

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