Puzzles

permutationgame

Permutation Game (30 Points)
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.
Constraints:
1 <= T <= 100
2 <= N <= 15
The permutation will not be an increasing sequence initially.
Sample Input:
2
3
1 3 2
5
5 3 2 1 4
Sample Output:
Alice
Bob






String Reduction (25 Points)
Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly?
Input:
The first line contains the number of test cases T. T test cases follow. Each case contains the string you start with.
Output:
Output T lines, one for each test case containing the smallest length of the resultant string after applying the operations optimally.
Constraints:
1 <= T <= 100
The string will have at most 100 characters.
Sample Input:
3
cab
bcab
ccccc
Sample Output:
2
1
5

pointsplane

Points in a Plane (40 Points)
There are N points in the plane. In one turn, you can select a set of collinear points on the plane and remove them. Your goal is to remove all the points in the least number of turns. Given the coordinates of the points, calculate the minimum number of turns needed and also in how many ways can this be done. Two ways are considered different if some point is removed in a different turn in them.
Input:
The first line contains the number of test cases T. T test cases follow. Each test case contains N on the first line, followed by N lines giving the coordinates of the points.
Output:
Output T lines, one for each test case, containing the least number of turns needed to remove all points and the number of ways to do so. As the answers can be large, output them modulo 1000000007.
Constraints:
1 <= T <= 50
1 <= N <= 16
0 <= xi,yi <= 100
No two points will have the same coordinates.
Sample Input:
2
3
0 0
0 1
1 0
4
3 4
3 5
3 6
5 5
Sample Output:
2 6
2 8
Explanation:
For the 1st input, Let the points be labelled p1,p2,p3. Then the ways are :

a. p1,p2 in the 1st turn and p3 in the 2nd
b. p1,p3 in the 1st turn and p2 in the 2nd
c. p2,p3 in the 1st turn and p1 in the 2nd
d. p3 in the 1st turn and p1,p2 in the 2nd
e. p2 in the 1st turn and p1,p3 in the 2nd
f.  p1 in the 1st turn and p3,p2 in the 2nd 

stonepiles

There are N piles of stones where the ith pile has xi stones in it. Alice and Bob play the following game:
a. Alice starts, and they alternate turns.
b. In a turn, a player can choose any one of the piles of stones and divide the stones in it into any number of unequal piles such that no two of the piles you create should have the same number of stones. For example, if there 8 stones in a pile, it can be divided into one of these set of piles: (1,2,5), (1,3,4), (1,7), (2,6) or (3,5). 
c. The player who cannot make a move (because all the remaining piles are indivisible) loses the game.
Given the starting set of piles, who wins the game assuming both players play optimally?
Input:
The first line contains the number of test cases T. T test cases follow. The first line for each test case contains N, the number of piles initially. The next line contains N space delimited numbers, the number of stones in each of the piles.
Output:
Output T lines, one corresponding to each test case containing "ALICE" if Alice wins the game and "BOB" otherwise.
Constraints:
1 <= T <= 50
1 <= N <= 50
1 <= xi <= 50
Sample Input:
4
1
4
2
1 2
3
1 3 4
1
8
Sample Output:
BOB
BOB
ALICE
BOB
Explanation:
For the first case, the only possible move for Alice is (4) -> (1,3). Now Bob breaks up the pile with 3 stones into (1,2). At this point Alice cannot make any move and has lost.