Problem Analysis of Code Jam to I/O for Women’19
There were 4 problems in the contest. I managed to solve 3 problems completely and 4th problem partially. The problem set was much better than the last Code Jam to I/O for Women contest. It had one ad-hoc problem, a dynamic programming problem, a random walk problem and a pretty interesting interactive problem (my favourite).
Lets begin by the discussing the 4 problems! There already exists an official analysis of the problem set but here I try to give an insight on how I approached the problems. I’ve removed the built-up story from all the questions and we’ll just focus on the primary task.
1. Grid Escape
Problem Description -
There’s a grid of size R x C, with each player residing in one of the cells. A player can choose only one of the four directions (North, South, East, West) to go from the current cell to the next cell. Each player keeps on traversing until it finds a way out of the grid or if it has made R x C moves without escaping.
We need to find the direction chosen in each cell such that exactly K of the players are able to escape or tell whether it’s impossible.
Solution -
My general approach for grid problems is to reduce it to 1 dimension (an array). Generally the solution for grid is the extension of the solution for the array. So is the case here too!
We’ll only consider 2 directions (east and west). Consider a grid of size 1 x 1 having a single player then the player can choose any one out of the 2 directions to escape out of the grid. Hence for K = 1 it is possible, but for K = 0 the answer is impossible.
Supposedly, we have a grid of size 1 x 2, then a player residing in (1, 1) can move East to reach (1, 2) while the player in (1, 2) has 2 directions to choose from. If Player 2 attempts to move towards West then both of the players will never be able to escape from the grid.
Hence, for K = 1 it is impossible.
If we assume a grid of size 1 x n, then all the players can escape out from the grid until we have one player that attempts to block the others preceding it. Therefore, if we assume that all the players from (1,1) to (1, n-k-1) move from left to right, then if the player in the (n — k)th cell attempts to move from right to left, then all the players before it will never be able to escape from the grid. Hence, we can deduce that for exactly K = n — 1 players, it is “Impossible” to decide a path so that all of them can escape.
The above approach can be generalised for 2-D grid as well (with 4 directions).
Imagine following a zig-zag path to reach from (1, 1) to (r, c) such that we start from (1,1) and move East to reach (1, n), then go South to reach ( 2, n) and further move left to reach (2, 1). In this way, if a player traverses from (1, 1) to (r, c), any player following its path will be able to escape from the grid.
2. Parcel Post
Problem Description -
We are given an array of size N. We need to divide the array in maximum number of contiguous desirable segments such that no 2 segments have an element in common except the ends of the segment. Each desirable segment must hold one of the 2 following properties -
- There exists 3 distinct indices such that i < j < k, A[i] > A[j] and A[k] > A[j]
- There exists 3 distinct indices such that i < j < k, A[i] < A[j] and A[k] < A[j]
The given initial array follows one of the properties.
Solution -
Dividing an array into segments which hold some property are quite popular problems. The main crux generally lies in the property of each segment. So let us focus on it first.
We can observe that if a subarray A[i … j] is desirable then a subarray which contains this is also desirable. Using the above observation, we can conclude that in order to make A[i … j] desirable, it is necessary for any of the following two conditions to be true :
- A proper subarray of A[i...j] is desirable.
- We have an index p such that : i < p < j, A[i] < A[p] and A[p] > A[j],
A[i] > A[p] and A[p] < A[j].
Using this, we can calculate whether every segment i to j is desirable or not in O(N*N).
Then we can apply Dynamic Programming to calculate maximum number of segments in which we can divide the initial array into. Let dp[i] denote the maximum number of desirable segments we can divide the A[1 … i]. We can calculate dp[i] in O(N) if we have dp[j] for all j < i. Refer to the code snippet below for further details.
Bonus: Can you think of anything better than O(N*N)? (Think of some greedy approach)
3. Sleep Walking
Problem Description -
We have a 2-D grid with infinite number of unit cells. A person P is currently in the unit cell at the coordinates (X, Y) — that is, in a cell X columns east of, and Y rows north of (0, 0). P can make a random unit move in any one of the directions — north, south, west, east. For every move, we can block 2 cells in the 2D grid where P cannot move. We have to find the minimum expected number of moves made by P to reach (0, 0).
Solution -
Considering both X and Y to be non — negative (without loss of generality) and F(X, Y) be the expected number of moves made by P.
There are two possible cases for the positions of (X, Y) -
- X != 0 and Y != 0
- X = 0 or Y = 0
Case 1: We can place the blocks on (X, Y+1) and (X+1, Y) so that P is forced to move in a direction towards the origin (West or South). Therefore, P can choose two out of the four directions with equal probability.
1. F(X, Y) = ½ F(X-1, Y) + ½ F(X, Y-1) + 1
Case 2: If (X, Y) lies on y — axis, then the blocks should be placed on (0, Y+1) and (-1, Y) so that P can move either East or South with equal probability.
2. F(0, Y) = ½ F(0, Y-1) + ½ F(1, Y) + 1
Similarly, we can deduce the function for x — axis as well.
The recurrence for Case 1 looks fine, but for Case 2 it doesn’t right. I mean that it is right, but it seems that F(0, Y) depends on F(1, Y). But F(1, Y) depends on F(0, Y). So because of this circular dependence, we need to change the recurrence for F(0, Y).
We know that —
3. F(1, Y) = ½ F(0, Y) + ½ F(1, Y-1) + 1
Let us substitute equation 3 into equation 2.
4. F(0, Y) = ⅔ F(0, Y-1) + ⅓ F(1, Y-1) + 2
Now we can use equations 1 and 4 to find expected moves for every X and Y.
4. War of Words
Problem Description -
You are playing a game with the robot consisting of 10⁵ words: the set of all five-letter strings made up of uppercase English letters between A and J, inclusive. All the words have a unique rank associated with them and higher-rank word defeats lower-rank word, with the one exception that the lowest-ranked word beats the highest-ranked word. The rank order is only known to the robot.
The game has the following rules:
- Turn 0: You start by naming a word W(0).
- Turn 1: The robot names a word W(1). If W(1) beats W(0), the robot scores a point. This continues; on turn i, the active player is you if i is even, or the robot if i is odd. The active player names a word Wi and scores a point if W(i) beats W(i-1). (If the two words are the same, no point is scored.) The score is not announced — in particular, you will not know whether each of your words has scored a point! This continues for a total of 201 turns.
On every turn, robot will choose a word uniformly at random from all possible words that will score a point on that turn, and independently of all of its previous word choices.
The goal was to get at least 50 points (for the larger case).
Solution -
First let us ignore the exception of the lowest-ranked word(L) beats the highest-ranked word(H).
As we don’t have the rank order, the only thing we can do for the W(0) is to pick it randomly. After that, the robot names W(1). Now the only information about W1 that we can deduce is rank(W(0)) < rank(W(1)). We cannot say exactly about rank(W(1)), but we can say something about its expected value. We know that the robot chooses the word uniformly at random. That means E(rank(W(1))) = (100000 + rank(W(0))) / 2.
Let us choose W(2) to be W(1), to which the robot will name W(3). Now we can see that we’ll eventually end up with H, but in how many steps? Obviously the worst case is in about 100000, but we want to know the expected value of it. It will take 0 turns if we are lucky enough to start at H, 1 turn if we start 1 rank away, an expected 1 + ((0 + 1) / 2) = 1.5 turns if we start 2 ranks away, an expected 1 + ((0 + 1 + 1.5) / 3) = 1.8333… turns if we start 3 ranks away, and so on. These are the harmonic numbers. So if we were to start at random it’ll take approximately 12 steps to reach the H.
Now coming back to the original problem (where there is an exception of H and L), how would we know if we’ve reached H? For that we’ll have to look at the pair of consecutive strings that we and the robot have played. The H-L transition will occur every cycle. So if we get multiple instances of 2 words back to back then we can think of it has H-L transition. To make sure that we assume H and L correctly with high probability, we know that if we play L, then the robot will pick any of the 99999 words randomly. So we can say with probability that if we get a repeated instance of 2 words, followed by a unique instance in another turn, then we can say that we have found H and L.
After having found H and L, we can win every other turn. As we will have a higher ranked word than that the robot plays.
