Thank you for participating in Kick Start 2019 Round C. The first problem, Wiggle Walk was a robot walk simulation problem that could be optimized by maintaining a set like data structure. The second problem, Circuit Board's solution required to efficiently reduce the problem to a classic problem of finding largest rectangle in a histogram. The last problem, Catch Some was a nice dynamic programming problem.
Cast
Wiggle Walk: Written by Kevin Tran and prepared by Sadia Atique.
Circuit Board: Written by Max Ward and Himanshu Jaju, and prepared by Jonathan Irvin Gunawan.
Catch Some: Written by Asima Krishna Prasad and prepared by Raihat Zaman Neloy.
Solutions, other problem preparation, reviews and contest monitoring by Bir Bahadur Khatri, Darcy Best, Gagan Madan, Himanshu Jaju, Jonathan Irvin Gunawan, Keghani Kristelle Kouzoujian, Kevin Tran, Lalit Kundu, Raihat Zaman Neloy, Reyno Tilikaynen, Sadia Atique, and Tony Wong.
Analyses were authored by Sandeep Mohanty.
Banny has just bought a new programmable robot. Eager to test his coding skills, he has placed the robot in a grid of squares with R rows (numbered 1 to R from north to south) and C columns (numbered 1 to C from west to east). The square in row r and column c is denoted (r, c).
Initially the robot starts in the square (SR, SC).
Banny will give the robot N instructions. Each instruction is one of
N,
S,
E or
W, instructing the robot to move one square north, south, east or west respectively.
If the robot moves into a square that it has been in before, the robot will continue moving in the same direction until it reaches a square that it has not been in before. Banny will never give the robot an instruction that will cause it to move out of the grid.
Can you help Banny determine which square the robot will finish in, after following the N instructions?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing the five integers N, R, C, SR and SC, the number of instructions, the number of rows, the number of columns, the robot's starting row and starting column, respectively.
Then, another line follows containing a single string of N characters;
the i-th of these characters is the i-th instruction Banny gives the robot (one of
N,
S,
E or
W, as described above).
For each test case, output one line containing Case #x: r c, where
x is the test case number (starting from 1),
r is the row the robot finishes in and
c is the column the robot finishes in.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ R ≤ 5 × 104.
1 ≤ C ≤ 5 × 104.
1 ≤ SR ≤ R.
1 ≤ SC ≤ C.
The instructions will not cause the robot to move out of the grid.
Time limit: 20 seconds.
1 ≤ N ≤ 100.
Time limit: 60 seconds.
1 ≤ N ≤ 5 × 104.
3 5 3 6 2 3 EEWNS 4 3 3 1 1 SESE 11 5 8 3 4 NEESSWWNESE
Case #1: 3 2 Case #2: 3 3 Case #3: 3 7
Arsh recently found an old rectangular circuit board that he would like to recycle. The circuit board has R rows and C columns of squares.
Each square of the circuit board has a thickness, measured in millimetres. The square in the r-th row and c-th column has thickness Vr,c. A circuit board is good if in each row, the difference between the thickest square and the least thick square is no greater than K.
Since the original circuit board might not be good, Arsh would like to find a good subcircuit board. A subcircuit board can be obtained by choosing an axis-aligned subrectangle from the original board and taking the squares in that subrectangle. Arsh would like your help in finding the number of squares in the largest good subrectangle of his original board.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with one line containing three integers R, C and K, the number of rows, the number of columns, and the maximum difference in thickness allowed in each row.
Then, there are R more lines containing C integers each. The c-th integer on the r-th line is Vr, c, the thickness of the square in the r-th row and c-th column.
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 number of squares in
a good subrectangle.
Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 50.
1 ≤ R ≤ 300.
1 ≤ C ≤ 300.
0 ≤ Vi, j ≤ 103 for all i, j.
K = 0.
0 ≤ K ≤ 103.
3 1 4 0 3 1 3 3 2 3 0 4 4 5 7 6 6 4 5 0 2 2 4 4 20 8 3 3 3 12 6 6 3 3 3 1 6 8 6 4
Case #1: 2 Case #2: 2 Case #3: 6
3 1 4 2 3 1 3 3 3 3 2 0 5 0 8 12 3 7 10 1 4 4 8 20 10 20 10 10 4 5 20 20 5 4 10 10 20 10 20
Case #1: 4 Case #2: 3 Case #3: 4
The sample cases are illustrated below. For each case, the good subcircuit board with the largest number of squares is highlighted in green.
Bundle is an animal researcher and needs to go observe K dogs. She lives on a horizontal street marked at metre increments with consecutive numbers 0, 1, 2, 3 and so on. She begins in her home, which is at position 0. There are also N dogs on the street. The i-th dog is Pi metres to the right of her home on the street (multiple dogs can share the same position).
Dogs come in different colors, which are denoted by positive integers. The i-th animal is of color Ai.
If Bundle is at her home, she can change the current color of her shirt. This is important since the dogs are very shy! Bundle can only observe a dog if she is at the same position as that dog, and is wearing a shirt of the same color as the dog.
It takes Bundle one second to move one metre to the left or right on the street. It takes her no time to change shirts or observe a dog.
What is the least amount of time it will take Bundle to observe K dogs? Note that she does not have to return home after observing K dogs.
The first line of the input gives the number of test cases, T. T test cases follow. Each testcase begins with a line containing the two integers N and K, the number of dogs on the number line and the number of dogs Bundle needs to observe, respectively. The second line contains N integers, the i-th of which is Pi, the position of the i-th dog. The third line contains N integers, the i-th of which is Ai, the color of the i-th dog.
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 least time Bundle needs to observe K dogs.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ K ≤ N.
1 ≤ Ai ≤ 1000.
1 ≤ Pi ≤ 105.
1 ≤ N ≤ 50.
1 ≤ N ≤ 1000.
3 4 3 1 2 4 9 3 3 2 3 4 3 1 2 3 4 1 8 1 8 6 6 4 3 3 1 3 10000 1 2 8 9 5 7
Case #1: 8 Case #2: 6 Case #3: 10028
In Sample Case #1, there are N = 4 dogs and Bundle needs to observe K = 3 dogs. One way that she can achieve this is as follows:
In Sample Case #2, there are N = 4 dogs and Bundle needs to observe K = 3 dogs. One way that she can achieve this is as follows:
In Sample Case #3, note that:
Approaching the problem naively, one might try to simply simulate what has been mentioned in the problem statement i.e. keep on moving the robot in the specified direction till it reaches an un-visited square. This approach is going to have a time complexity of O(N2), which although good enough for test set 1.
The problem with the above approach is that it visits a lot of already visited squares which in worst case will be all the previously visited squares (Consider the input where you are given alternating E and W throughout). If we somehow get to the destination square for each instruction faster, we might be able to reduce the complexity.
Let's say the robot is in some row r and received an instruction W. Now, all the already visited squares (if any) it will pass before reaching an unvisited square have to form a contiguous interval in row r. This suggests that we may use intervals to represent all the visited squares in the same row.
With that in mind, consider we have a set of intervals for each row and each column of the grid to represent which cells have been visited in that particular row or column, let's call them interval-sets. Initially, all these sets are empty except for the set corresponding to row SR, which has a single interval (SC, SC), and the set corresponding to the column SC, which has a single interval (SR, SR).
Now, using this data-structure, let's try to find the destination square for the robot. Let's say it's in square (r, c) and got an instruction W. For this, first we search in the interval-set corresponding to row r. We will try to find which interval in this set contains c (there must definitelty be one!). Once we find it, we immediately know what's going to be the new position for the robot! It's apparent that the same method works for all other directions as well.
All that remains now is to find a way to update our data-structure suitably to also include the newly visited square. This can be done in a very standard manner by simply finding the adjacent intervals for that square in both, the corresponding column interval-set and the corresponding row interval-set and then updating them either by extending one of the intervals or merging them or adding a new 1 length interval.
Since we add at most one interval in each case, the number of intervals is O(N). Since all operations are about finding/inserting/removing a single interval, all of those can be handled easily in O(log(N)) time. So the over all run time of this approach is O(Nlog(N)). There is also a O(N) solution to this problem using hash tables. It is left as an exercise to the reader.
Restating the problem, we are asked to find the largest sub-rectangle in a grid of integers such that the difference between the maximum and minimum integers in each row of the sub-rectangle is not more than K.
For test set 1, we have K = 0. This means we have to find the largest sub-rectangle in which all integers are equal in each of the rows.
To do this, we first define Pi,j as the maximum number of contigious cells on the right of the cell i, j which have the same value as cell i, j.
We immediately observe that Pi, j = 1 + Pi, j + 1 if the integers in j and (j+1)th columns of row i are equal, else Pi,j is 1.
Once we have these values, our problem simply reduces to the well known problem of finding the area of the largest rectangle in a histogram. For every column c, we first divide it into segments where all integers are equal. For any such segment say from row r1 to r2, we take Pi, c for i = r1 to r2 as the heights of histogram. It is clear now that any rectangle in this histogram represents a rectangle where in all integers are equal in each row of the rectangle.
Calculating the largest rectangle in the histogram of width M can be done in O(M) time using stacks.
The idea is to find for every bar of the histogram, the closest bars to the left and right of the current bar which are shorter than the current bar.
To find the closest shorter bar on the left (we can modify the same procedure to also find the closest shorter bar on the right), we traverse our histogram from left to right. We initially have an empty stack which we update as follows:
If the current bar's height is greater than the top element of the stack, then it's the required bar for our current bar and we push the current bar's height into the stack.
Otherwise we keep on popping the stack till we find a number which is lesser than the current bar's height (or the stack becomes empty, in which case there's no bar to the left which is shorter than the current bar). This top element now corresponds to our required bar. We then push the current bar's height into our stack.
Since we push or pop at most once for every bar, the complexity of this procedure is linear as described above.
And hence, we'll have to spend O(R) time per column with a total run time complexity of O(RC).
For this case, K >= 0, so we re-define Pi,j as the maximum length such that the difference between the maximum number and the minimum number present in all cells of row i with column >= j and < j + Pi,j is not more than K.
To calculate Pi,j we binary search for the first cell in the ith row and to the right of jth column such that the condition that the difference between the maximum and minimum number present in these cells is not more than K is violated. We can do this quickly if we can answer range minimum and range maximum queries quickly. Those can be dealt with a lot of different data-structures.
Once we have this, our problem again reduces to the problem of finding the area of the largest rectangle in a histogram. For, every column c, we take Pi, c for i = 1 to R as the heights of histogram. It is clear now that any rectangle in this histogram represents a rectangle where in no row maximum and minimum elements differ by more than K.
If we use a data-structure like Sparse Table to answer the range minimum and maximum queries then we can find all the P-values in O(RClog(C)) time. The last part of finding the largest area rectangle in histogram should be done once for each column, and hence takes O(R) time for each case resulting in O(RC) time in total. Combining both, we have a final complexity of O(RClog(C)). We can further reduce this to a complexity of O(RC) by replacing the Sparse Table data-structure with a two pointers variation using two deques, that approach is left as an exercise for the reader.
Firstly, observe that if Bundle switches the color of her shirt then she should never wear a previously worn color again as that would not give us a better answer. Also, for dogs of the same color, if she observes one dog then she should have observed all dogs who are at a position less than that dog. The condition that she doesn't need to return to her home after observing the last dog is a little tricky. Let's first solve the problem where she must return home after observing the last dog.
For this simplified version, we notice that the order of the color of shirts that Bundle has to put on
doesn't matter. This gives rise to the following dynamic programming approach.
Let dp[i][j] denote the minimum time Bundle needs to observe j dogs such that she has either observed or
has decided she'll not observe dogs of colors 1 to i.
Hence, dp[C][K] becomes our answer, where C is the total number of different colors.
To calculate dp[i][j] we loop upon the number of dogs Bundle could have observed for the (i-1)th color,
and take the minimum cost among them. That is,
dp[i][j] = min(dp[i-1][j] + 0, dp[i-1][j-1] + 2 * Xi,1, dp[i-1][j-2] + 2 * Xi, 2, dp[i-1][j-3] + 2 * Xi, 3 ...)
Where, Xc, d represents the distance of the d-th dog of c-th color from Bundle's house.
Since the size of the loop for a particular color is the number of dogs of previous color + 1, the sum of sizes of all loops is O(N). Hence, we have O(N2) states and do a total of O(N) transitions. This gives us a run time of O(N2) for a given color as the last color.
To complete the solution, we simply do this considering every color as the last color and add in the cost of observing dogs of the last color separately. This will incur an additional O(N) loop to iterate over all colors resulting in a final complexity of O(N3).
We can optimize the previous solution to not do the same calculations with every color as the last color. This can be done by adding a boolean parameter in our state representing if we have already decided on the last color. We simply don't add the cost of returning back home whenever we set this parameter to true.
Essentially, we have dp[i][j][k] where i and j still represent the same things and k is a boolean denoting if we have chosen the last color in the first i colors.
Now, dp[i][j][0] = min(dp[i-1][j][0] + 0, dp[i-1][j-1][0] + 2 * Xi,1, dp[i-1][j-2][0] + 2 * Xi, 2 ...)
dp[i][j][1] = min(min(dp[i-1][j][1] + 0, dp[i-1][j-1][1] + 2 * Xi,1, dp[i-1][j-2][1] + 2 * Xi, 2 ...),
min(dp[i-1][j][0] + 0, dp[i-1][j-1][0] + Xi,1, dp[i-1][j-2][0] + Xi, 2 ...))
Again we have O(N2) states and do a total of O(N) transitions. But we just do this once and not once for every color, yeilding a final complexity of O(N2).