Problem Analysis of Code Jam to I/O for Women’19

(Think of some greedy approach)3.

Sleep WalkingProblem 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 != 0X = 0 or Y = 0Case 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) + 1Case 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) + 1Similarly, 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) + 1Let us substitute equation 3 into equation 2.

4.

F(0, Y) = ⅔ F(0, Y-1) + ⅓ F(1, Y-1) + 2Now we can use equations 1 and 4 to find expected moves for every X and Y.

4.

War of WordsProblem 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.

.

. More details

Leave a Reply