Game Theory in Competitive Programming Part — 11

Codeforces: Godsend

Welcome to part 11 of this series, in case you have missed part 10, here is the link: Part 10

Problem Statement:

Leha somehow found an array consisting of n integers. Looking at it, he came up with a task. Two players play the game on the array(arr[]). Players move one by one. The first player can choose for his move a subsegment of non-zero length with an odd sum of numbers and remove it from the array, after that the remaining parts are glued together into one array and the game continues. The second player can choose a subsegment of non-zero length with an even sum and remove it. Loses the one who can not make a move. Who will win if both play optimally?

Examples:

Input: 4

1 3 2 3

Output: First

Explanation: In this case, the first player removes the whole array in one move since the sum of all elements is odd and wins as the second player won’t have anything left to remove.

Input: 2

2 2

Output : Second

Explanation: In the second sample the first player can’t make a move and lose.

Problem link: Problem — B — Codeforces

Hint: Focus only on odd numbers. Think about what will happen if the input array consists only of odd numbers.

Solution: The first player wins if there is at least one odd number in the array. Let’s prove this.

Let’s store the total count of odd numbers in the array in variable T.

There are two cases to consider:

1) If T is odd. The first player takes the whole array and wins because the sum of any count of even numbers and the odd count of odd numbers is always odd.

2) T is even. Suppose that position of the rightmost odd number is pos. Then the strategy for the first player is as follows: in his first move, he will pick subarray [1, pos — 1]. The remaining suffix of the array will have exactly one odd number that the second player won’t be able to include in his subarray as that will make the sum odd which the second player doesn’t want. So, regardless of his move, the first player will take the last left odd number at position pos and win.

Source Code: