Interviewstreet- Permutation Game

Question

Alice and Bob play the following game:

1) They choose a permutation of the first N numbers to begin with.

2) They play alternately and Alice plays first.

3) In a turn, they can remove any one remaining number from the permutation.

4) The game ends when the remaining numbers form an increasing sequence. The person who played the last turn (after which the sequence becomes increasing) wins the game.

Assuming both play optimally, who wins the game?

Input: The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by a permutation of the integers 1..N on the second line.

Output: Output T lines, one for each test case, containing "Alice" if Alice wins the game and "Bob" otherwise.

Sample Input:

2

3

1 3 2

5

5 3 2 1 4

Sample Output:

Alice

Bob

Constraints:

1 <= T <= 100

2 <= N <= 15

The permutation will not be an increasing sequence initially.

I am trying to solve above problem. I have derived till far but I am stuck at a point. Please help me to proceed further.

In above problem, for permutation of length 2, player 1 always wins.

For a permutation of length 3, player 2 wins if the string is strictly increasing or decreasing.

For a permutation of length 4, If player 1 is able to make the string strictly increasing or decreasing by removing a character, she wins else player 2 wins.

Hence a conclusion is:

If current player is able to make the string strictly increasing he/she wins. (Trivial case)

If he/she is able to make it strictly decreasing the the winner is decided by the number of elements in that sequence. If there are even number of elements in that sequence, current player looses, else wins.

But what should be done if the resultant string is neither increasing nor decreasing??

Answer 1

This is a typical game problem. You have 2^15 possible positions which denote which are the remaining numbers. From the number of the remaining numbers you can derive whose turn it is. So now you have a graph that is defined in the following manner - the vertices are the possible sets of remaining numbers and there is an edge connecting two vertices u and v iff there is a move that changes set u to set v(i.e. set v has exactly one number less).

Now you already pointed out for which positions you know who is the winner straight away - the ones that represent increasing sequences of numbers this positions are marked as loosing. For all other positions you determine if they are wining or loosing in the following manner: a position is winning iff there is an edge connecting it to a loosing position. So all that is left is to something like a dfs with memoization and you can determine which positions are winning and which are loosing. As the graph is relatively small (2^15 vertices) this solution should be fast enough.

Hope this helps.

Answer 2

Of course, this can be done with "brute force" for small N, but don't you suspect an easier answer around inversions and the sign of a permutation?

Originally I suspected an answer like "Alice wins iff the sign is -1, else loses", but this is not the case.

But I would like to propose a representation of the problem that not only your algorithm may use, but one that will equally boost your paper-and-pen performance in this game.

An inversion is a pair of indices i<j such that a[i]>a[j]. Consider (i,j) an edge of an undirected graph with vertices 1,...,N. Each player deletes a vertex from this graph and wins if there are no edges left.

For 5 3 2 1 4, the resulting graph is

   5--3
  /|\ |
 / | \|
4  1--2

and Alice quickly sees that removing "5" gives Bob the opportunity to remove 2. Then no inversions are left, and Bob wins.

Answer 3

This game can be solved recursively.

Each time alice takes her first pick and picks i, subtract 1 from all the remaining numbers that are larger than i. Now we have the same game but with the numbers 1 to N-1

lets say your sequence is

1,3,5,4,2

on her first move, Alice can pick any number. case1: she picks 1, alice can win if bob cant win with 3,5,4,2 (equivalently 2,4,3,1)

case2: she picks 3 first. Alice can win if bob cant win with 1,5,4,2 (equivalently 1,4,3,2)

case3: she picks 5 first. Alice can win if bob cant win with 1,3,4,2

you get the idea.

So you can make a recursive function to work out the solution for a size N permutation all by using size N-1 permutations for each possible first guess. the base case for the recursion is when you have an in-order sequence.

Each step of the recursion, the person tries all possibilities and picks any that makes them win.

Because there are many combinations of moves that can get down to the same sequence, the recursion has overlapping sub problems. This means we can use dynamic programming, or simply "memoize" our function, greatly increasing efficiency.

For further speedup one may use symmetry in the permutations, as many groups of permutations are equivalent, such as the reverse of one permutation would yield the same result.

Good luck.

Answer 4

@tiwo ,@rup COnsidering 5 3 2 1 4 is the sequence first alice removes 5 and the bob removes 2 then the sequence is 3 1 4 which is not in increasing order then alice gets the chance to remove 1 and the the sequence is in ascending order Alice should be the answer. In the graph you gave there should be an edge between 3 and 1 as 1 and 3 are in inversion.

Please tell me where i am wrong as the answer given in the problem is infact BOB