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

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 **V _{i}**. A day is

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

Please help Isyana find out the number of record breaking days.

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 **V _{i}**.

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.

Time limit: 20 seconds.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

0 ≤ **V _{i}** ≤ 2 × 10

1 ≤ **N** ≤ 1000.

1 ≤ **N** ≤ 2 × 10^{5} for at most 10 test cases.

For the remaining cases, 1 ≤ **N** ≤ 1000.

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

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.

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.

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.

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, **A _{1}**,

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.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

1 ≤ **A _{i}** ≤ 10

Time limit: 20 seconds.

1 ≤ **K** ≤ 10.

Time limit: 40 seconds.

1 ≤ **K** ≤ 10^{4}.

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.

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

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?

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.

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.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

1 ≤ **A** ≤ **N**.

1 ≤ **B** ≤ **N**.

Time limit: 20 seconds.

1 ≤ **N** ≤ 100.

Time limit: 40 seconds.

For up to 5 cases, 1 ≤ **N** ≤ 5 × 10^{5}.

For all other cases, 1 ≤ **N** ≤ 100.

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

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 **D _{i}**.

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 **K _{i}**-th room
that she will take a picture in if she starts in the

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 **D _{i}**.
Then,

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.

Time limit: 40 seconds.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

1 ≤ **D _{i}** ≤ 10

All

1 ≤

1 ≤

2 ≤ **N** ≤ 1000.

1 ≤ **Q** ≤ 1000.

2 ≤ **N** ≤ 10^{5} and 1 ≤ **Q** ≤ 10^{5} for at most 20 test cases.

For the remaining cases, 2 ≤ **N** ≤ 1000 and 1 ≤ **Q** ≤ 1000.

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.

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.

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

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.

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

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

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 4^{K} combinations to be
tested and O(4^{K}) time complexity.

Let DP[i, j] be the minimum number of rule violations required to convert the first i notes
**A _{1}**,

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 **A _{i-1}** and

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.

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

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

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

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

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**).

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, answer is
**S**+**K.**

- If X is the door left to
- 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(log**N**). 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]])

- If X < Y, then answer is Y +

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

Test Data

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