Array Game (Codeforces 1600E)
Tags: Greedy, games

Alice and Bob are playing a game. They are given an array $$$A$$$ of length $$$N$$$. The array consists of integers. They are building a sequence together. In the beginning, the sequence is empty. In one turn a player can remove a number from the left or right side of the array and append it to the sequence. The rule is that the sequence they are building must be strictly increasing. The winner is the player that makes the last move. Alice is playing first. Given the starting array, under the assumption that they both play optimally, who wins the game?

Input: The first line contains one integer $$$N$$$ ($$$1 \leq N \leq 2*10^5$$$) - the length of the array $$$A$$$.The second line contains $$$N$$$ integers $$$A_1$$$, $$$A_2$$$,...,$$$A_N$$$ ($$$0 \leq A_i \leq 10^9$$$)

Output: The first and only line of output consists of one string, the name of the winner. If Alice won, print "Alice", otherwise, print "Bob".


Sample Inputs:
1
5

3
5 4 5

6
5 8 2 1 10 9

Sample Outputs:
Alice

Alice

Bob

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
leftMax = 1
rightMax = 1
for i in range(n - 1):
    if a[i] < a[i + 1]:
        leftMax += 1
    else:
        break
for i in range(n - 1, 0, -1):
    if a[i] < a[i - 1]:
        rightMax += 1
    else:
        break
if leftMax % 2 == 1 or rightMax % 2 == 1 or n == 1:
    print('Alice')
else:
    print('Bob')

Solution (Python):
arraySize = int(input())
(left, right) = (0, arraySize - 1)
array = list(map(int, input().split()))
while left + 1 < arraySize and array[left] < array[left + 1]:
    left += 1
while right > 0 and array[right] < array[right - 1]:
    right -= 1
left += 1
right = arraySize - right
if left % 2 or right % 2:
    print('Alice')
else:
    print('Bob')

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
(l, r) = (0, n - 1)
while l < n - 1 and a[l] < a[l + 1]:
    l += 1
while r >= 0 and a[r] < a[r - 1]:
    r -= 1
if l + 1 & 1 or n - r & 1:
    print('Alice')
else:
    print('Bob')