Problem Analysis of Kickstart — Round C (2019)

Hello everyone!

I have been busy in semester exams as well as settling in my internship, so couldn’t be much active! But recently, I gave Kickstart (Round C), which had quite some fun problems, so I thought of sharing my solutions.

There were 3 problems in this round, each containing small and large test cases. I was able to solve two problems completely, and one problem partially.

So, let’s begin by discussing them! (Like always, I have removed the built-up story so we’ll focus on the main task. )

1. Wiggle Walk:

Problem Description -

We are provided with a R x C grid and a starting position (r, c). In each instruction we have to move one square north, south, east or west. If we reach a square that has already been visited, then we have to continue moving in the same direction until we reach a square that hasn’t been visited.

We need to return the final position after N instructions, provided no instruction causes us to move out of the grid.

Solution -

Let the current position be (x, y), then we can easily observe the change in the position when the following instructions are executed (provided the new position hasn’t been visited yet) :-

N ( North): x = x — 1
E (East): y = y + 1
S (South): x = x + 1
W (West): y = y — 1

In-order to keep track of the visited positions, we can maintain a boolean map for each position (x, y) and we’ll keep on changing the current the position repeatedly for a particular instruction till an unvisited square isn’t reached.

2. Circuit Board:

Problem Description -

We are given with a 2-D array of size R x C. We need to return the maximum area of a sub-matrix, such that the difference between the maximum and the minimum values in each of its row is no greater than K (given as input).

Solution -

As mentioned in my previous post, my general approach to any grid problem is to reduce it to one dimension (array).

Let’s initially consider a 1-D array of size N. Here, in order to find the maximum size subarray, we can maintain an array ind[ ] where

ind[i] = j, where 'j' is the maximum index with satisfies the given constraint (difference < K)

We can find ind array in O(N*N). There are other efficient methods (O(NlogN)), but it isn’t required in the question.

For 1-D, our answer would be max ( ind[i]-i+1 ) for all i.

Now let’s try to extend this approach to 2-D. We can represent a sub-matrix by its 2 diagonal ends, (r1, c1) and (r2, c2) such that r1 <= r2 and c1 <= c2.

Let’s fix r1, r2 and c1 to some value. Can we find the maximum c2 possible such that the condition holds? Yes!

The maximum possible value is — min(ind[r][c1]) for all r1 <= r <= r2

Refer to the code below for implementation details -

Overall Complexity — O(N*N*N)

There also exist a more efficient method of O(N*N*logN). For that please refer the analysis page of the contest.

3. Catch Some

Problem Description -

There are N dogs of Ai color, placed at Pi position each. We can only observe a dog if we are at the same position as that dog, wearing a shirt of the same color as the dog. The tshirt color can be changed only at position 0. It takes one second to move one unit distance to the left or right. We need to find the least amount of time it will take to observe K dogs.

Solution -

First let’s solve the case when the person (say P) has to return to origin after visiting the ‘K’ dogs.

Here are some few key observations -

1. Each color is independent. We change color at origin, then visit the dogs of same color, then return to origin.
2. If we are visiting a dog of color ‘c’, then it is optimal to visit all the dogs of color ‘c’ prior to this position.

From these observations, we get the intuition that something of dynamic programming sort of technique can be used. For each color we need to choose how many dogs of that color we’ll observe.

Let pos[i][k] denote the position of dog of color ‘i’, and kth closest dog of color ‘i’ from the origin.

Let dp[i][j] denotes that we have considered dogs of color — [1 .. i] and have observed j dogs.

Then the transition will be -

dp[i][j] = min(dp[i-1][j], dp[i-1][j — k] + 2*pos[i][k])

Our final answer will be dp[1000][K].

Let’s find out the complexity of this algorithm. We can see that for each dog it’ll take O(K), so total complexity is O(1000*K + N*K)

Now coming back to the original question, we can see that after observing the last dog, she won’t return back to the origin (for the optimal case).

Let the color of last observed dog be ‘c’. Let the number of dogs observed of that color be ‘x’. Then we can see that we need to calculate the dp excluding the color c, and we need to find dp[1000][K — x].

But if we iterate on every dog to be the last observed dog, then this would take O(N*1000*K). This complexity won’t pass for the constraints given.

Observe that the computation we do before color ‘c’ and after color ‘c’ is same for all elements of color ‘c’. So, we can maintain prefix and suffix of that dp, and calculate on color ‘c’.

Let prefix_dp[i][j] denotes that we have considered dogs of color — [1 .. i] and have observed j dogs.

Then the transition will be -

prefix_dp[i][j] = min(prefix_dp[i-1][j], prefix_dp[i-1][j — k] + 2*pos[i][k])

Let suffix_dp[i][j] denotes that we have considered dogs of color — [i .. 1000] and have observed j dogs.

Then the transition will be -

suffix_dp[i][j] = min(suffix_dp[i+1][j], suffix_dp[i+1][j — k] + 2*pos[i][k])

Now our answer will become-

min over i(prefix_dp[c — 1][i] + pos[c][x] + suffix_dp[c+1][K-i-x])

Overall Complexity — O(1000*K + N*K)