Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

An interesting game challenge

Problem statement
Andy loves playing games. He wants to play a game with his little brother, Bob, using an array, A, of n distinct integers. The rules are as follows:

  • Bob always plays first and the two players move in alternating turns.
  • In a single move, a player chooses the maximum element currently present in the array and removes it as well as all the other elements to its right. For example, if A = \left[2,3,5,4,1\right], then it becomes A = \left[2,3\right] after the first move because we remove the maximum element (i.e., 5) and all elements to its right (i.e., 4 and 1).
  • The modifications made to the array during each turn are permanent, so the next player continues the game with the remaining array. The first player who is unable to make a move loses the game.

Andy and Bob play g games. Given the initial array for each game, can you find and print the name of the winner on a new line? If Andy wins, print ANDY; if Bob wins, print BOB.

Input Format
The first line contains a single integer denoting g (the number of games). The 2\times g subsequent lines describe each game array over two lines:

  1. The first line contains a single integer, n, denoting the number of elements in A.
  2. The second line contains n distinct space-separated integers describing the respective values of a_0, a_1, \dots, a_{n-1} for array A.

Constraints
Array contains n distinct integers.
1 \le g \le 100
1 \le n \le 10^5
1 \le a_i \le 10^9
The sum of n over all games does not exceed 10^5.

Output Format
For each game, print the name of the winner on a new line (i.e., either BOB or ANDY).

Sample Input 0

2
5
5 2 6 3 4
2
3 1

Sample Output 0

ANDY
BOB

Explanation 0
Andy and Bob play the following two games:

1.
Initially, the array looks like this:

In the first move, Bob removes 6 and all the elements to its right, resulting in A = \left[5,2\right]:

In the second move, Andy removes 5 and all the elements to its right, resulting in A = \left[\right]:

At this point, the array is empty and Bob cannot make any more moves. This means Andy wins, so we print ANDY on a new line.

2.
In the first move, Bob removes 3 and all the elements to its right, resulting in A = \left[\right]. As there are no elements left in the array for Andy to make a move, Bob wins and we print BOB on a new line.

Solution

public class AnInterestingGame {
    private static final String BOB = "BOB";
    private static final String ANDY = "ANDY";

    private static void solve(int[] a, int start, int end, String player) {
        if (start > end) {
            System.out.println(player.equals(BOB) ? ANDY : BOB);
        } else {
            int max = Integer.MIN_VALUE;
            int maxIdx = -1;
            for (int i = start; i <= end; i++) {
                if (a[i] > max) {
                    max = a[i];
                    maxIdx = i;
                }
            }

            solve(a, start, maxIdx - 1, player.equals(BOB) ? ANDY : BOB);
        }

    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);
        int games = in.nextInt();
        for (int g = 0; g < games; g++) {
            int n = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
            }

            solve(a, 0, a.length - 1, BOB);
        }
    }
}