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:
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:
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 Vi.
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 ≤ Vi ≤ 2 × 105.
1 ≤ N ≤ 1000.
1 ≤ N ≤ 2 × 105 for at most 10 test cases.
For the remaining cases, 1 ≤ N ≤ 1000.
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
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.
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:
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, A1, A2 ... AK, where Ai refers to the pitch of the i-th note for this test case.
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 ≤ Ai ≤ 106.
Time limit: 20 seconds.
1 ≤ K ≤ 10.
Time limit: 40 seconds.
1 ≤ K ≤ 104.
2 5 1 5 100 500 1 8 2 3 4 5 6 7 8 9
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:
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:
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 × 105.
For all other cases, 1 ≤ N ≤ 100.
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
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.
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?
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.
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 ≤ Di ≤ 105, for all i.
All Di are distinct.
1 ≤ Si ≤ N, for all i.
1 ≤ Ki ≤ N, for all i.
2 ≤ N ≤ 1000.
1 ≤ Q ≤ 1000.
2 ≤ N ≤ 105 and 1 ≤ Q ≤ 105 for at most 20 test cases.
For the remaining cases, 2 ≤ N ≤ 1000 and 1 ≤ Q ≤ 1000.
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
Case #1: 5 3 5 2 Case #2: 8 8
In sample case #1, there are four queries:
In sample case #2, there are two queries:
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;
}
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.
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.
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
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).
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:
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:
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).