In a turn, they can remove any one remaining number from the permutation.
The game ends when the remaining numbers form an increasing sequence of or more numbers. The person who played the last turn (after which the sequence becomes increasing) wins the game.
Assuming both play optimally, who wins the game?
For example, if the starting permutation might be . First, Alice chooses or (use for the example) leaving . Since this is a decreasing sequence, Bob can remove any number for optimum play (he will lose regardless). Alice then removes any number leaving an array of only one element. Since Alice removed the last element to create an increasing sequence, Alice wins.
Complete the permutationGame function in the editor below. It should return a string that represents the winner of the game, either Bob or Alice.
permutationGame has the following parameter:
- arr: an array of integers that represents the starting permutation
The first line contains the number of test cases .
Each of the next pairs of lines is in the following format:
- The first line contains an integer , the size of the array
- The second line contains space-separated integers, where
The permutation will not be an increasing sequence initially.
Output lines, one for each test case, containing Alice if Alice wins the game and Bob otherwise.
1 3 2
5 3 2 1 4
For the first test, Alice can remove the or the to make the sequence increasing and wins the game.
For the second test, if is removed then the only way to have an increasing sequence is to only have number left. This would take a total of moves, thus allowing Bob to win. On the first move if Alice removes the , it will take more moves to create an increasing sequence thus Bob wins. If Alice does not remove the , then Bob can remove it on his next turn to create the same game state to win (decreasing sequence, numbers left).