Interviewstreet- Rearrange the game

Question

Alice and Bob play the following game:

1) First they choose a permutation of the first N numbers.

2) They play alternately, and Alice plays first.

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

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

Assuming both games are optimal, who wins the game?

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

Conclusion: T output lines, one for each test case, containing “Alice” if Alice wins the game and “Bob” otherwise.

Input Example:

2

3

1 3 2

5

5 3 2 1 4

Output result:

Alice

Bean

Limitations:

1 <= T <= 100

2 <= N <= 15

The permutation at first will not be incremental.

I am trying to solve the above problem. I got to the end, but I was stuck at some point. Please help me continue.

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

For a permutation of length 3, player 2 wins if the string strictly increases or decreases.

For a permutation of length 4, if player 1 can force the string to strictly increase or decrease by removing the character, it wins 2 more players.

The conclusion follows:

If the current player can make the line strictly increasing, he wins. (Trivial case)

If he / she can do it strictly, the winner is determined by the number of elements in this sequence. If there are an even number of elements in this sequence, the current player loses, but wins.

But what if the resulting row does not increase or decrease?

Answer 1

This is a typical game problem. You have 2 ^ 15 possible positions that indicate the remaining numbers. From the number of remaining numbers you can get your move. So, now you have a graph, which is defined as follows: the vertices are the possible sets of the remaining numbers, and there is an edge connecting the two vertices u and v, if there is a movement that changes the set u to the set v (i.e., the set v has exactly one number less).

Now you have already indicated which positions you know who will win immediately - those that represent increasing sequences of numbers, these positions are marked as a loss. For all other positions, you determine whether they win or lose as follows: the position wins if there is an edge connecting it to the lost position. Thus, all that remains is something like dfs with memoization, and you can determine which positions are won and which are lost. Since 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 using "brute force" for a small N, but do not suspect that an easier answer around inversions and a sign of permutation ?

Initially, I suspected that "Alice wins if the sign is -1, otherwise it is lost," but this is not so.

But I would like to offer an idea of ​​the problem that not only your algorithm can use, but also one that will equally improve the performance of your paper and pen in this game.

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

For 5 3 2 1 4 , the resulting graph

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

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

Answer 3

This game can be solved recursively.

Each time Alice takes her first choice and chooses i, subtract 1 from all other numbers that are greater than i. Now we have the same game, but with numbers from 1 to N-1

lets say your sequence

1,3,5,4,2

for the first time, Alice can choose any number. Case 1: she chooses 1, Alice can win if bob doesn't win with 3,5,4,2 (equivalent to 2,4,3,1)

Option 2: she chooses first 3. Alice can win if the bob wins with 1,5,4,2 (equivalent to 1,4,3,2)

Question 3: she chooses first 5. Alice can win if bob wins with 1,3,4,2

you get the idea.

Thus, you can make a recursive function to formulate a solution for a permutation of sizes N using permutations of size N-1 for each possible first guess. The base register for recursion is when you execute a sequence in sequence.

Each step of recursion, a person tries all the possibilities and chooses everything that makes them win.

Since there are many combinations of moves that can go to the same sequence, recursion has overlapping routines. This means that we can use dynamic programming or simply “remember” our function, which greatly improves efficiency.

For further acceleration, you can use symmetry in permutations, since many groups of permutations are equivalent, for example, the reverse one permutation will give the same result.

Good luck.

Answer 4

@tiwo, @rup AGREEMENT 5 3 2 1 4 - the sequence in which the first Alice deletes 5 and bob deletes 2, then the sequence 3 1 4, which is not in ascending order, then Alice has a chance to delete 1, and the sequence is in order Alice's increasing should be the answer. The graph you indicated should have an edge between 3 and 1, since 1 and 3 are in inverse.

Please tell me where I am mistaken as the answer provided in the problem is infact BOB

Answer 5

You can solve it with a minimax algorithm. Here is the code in java

 import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int t = ni(); for(int i=0; i<t; i++){ int n = ni(); Map<Long, Boolean> map = new HashMap<Long, Boolean>(); int[] numbers = new int[n]; for(int j=0; j<n; j++){ numbers[j] = ni(); } if(aliceWin(numbers, map)) System.out.println("Alice"); else System.out.println("Bob"); } } public static boolean aliceWin(int[] a, Map<Long, Boolean> map){ long h = hashCode(a); int temp; if(map.containsKey(h)) return true; for(int i=0; i<a.length; i++){ if(a[i]>0){ temp = a[i] ; a[i] = 0; if(isIncreasing(a)){ map.put(h, true); a[i] = temp; return true; } if(!aliceWin(a, map)) { map.put(h, true); a[i] = temp; return true; } a[i] = temp; } } return false; } public static long hashCode(int[] a){ long result = 0; for(int i=0; i<a.length; i++){ result = (result << 4) + a[i]; } return result; } public static boolean isIncreasing(int[] a){ int last = 0; for(int i=0; i<a.length; i++){ if (a[i] > 0){ if(last > a[i]) return false; last = a[i]; } } return true; } public static int ni(){ return sc.nextInt(); } public static void print(Object... args){ System.out.println(Arrays.deepToString(args)); } } 

From the blog: hackerrank-permutation-game

Answer 6

Here is some code that builds a graph for you, but requires that you call reverse () on the graph, create a node source, connecting to all the nodes in the database, return to the source, seeing if Alice wins the way.

 input_ = """2 3 1 3 2 5 5 3 2 1 4""".splitlines() perms = [map(int,perm.split()) for perm in input_ if len(perm)>1] "[['1', '3', '2'], ['5', '3', '2', '1', '4']]" if networkx is None: import networkx from itertools import combinations def build_graph(perm): base = set() G = networkx.DiGraph() for r in range(1,len(perm)+1): for combo in combinations(perm,r): combo = list(combo) if combo == sorted(combo): base.add(tuple(combo)) continue for i in range(r): G.add_edge(tuple(combo),tuple(combo[:i]+combo[i+1:])) #you may want to reverse the graph later to point from base to source. return G,base def solve(G,base): #dfs, pass for perm in perms: G,base = build_graph(perms[0]) print solve(G,base) 

Answer 7

We cannot just check at every step that .. makes one change by the next player, sorts the sequence. If so, make another move. or continue driving

like 5 3 2 1 4 if Alice 3 2 1 4 Bob can't win in one move, eliminating ... like if he does 2 1 4 he sorted nt .. he does 3 1 4 he sorted nt .. he does 3 2 4, it is sorted nt .. so 5 3 2 1 4 → 3 2 1 4 is a valid move !!

now there is a bob revolution .. it checks the same .. but after a while ... there will not be such a number that you can make a movement as described above. so you have to make a random move, and who wins, then it can be easily calculated by the number of steps tht will make a sequence in one element!

Answer 8

To me (using almost your own words):

If he / she can make it strictly increasing from the first move, he wins (trivial case), otherwise the winner is determined by the number of elements in this sequence.

Take the second example as an example.

I think the graphics solution is great, but it forgets that the players are playing optimally. Therefore, it is not necessary to check all the different paths, since some of them will be obtained from a non-optimal choice.