Game Theory in Competitive Programming Part 9

Codeforces: Let’s Go Hiking

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

Problem Statement

A permutation p is written from left to right on the paper. First Qingshan chooses an integer index

and tells it to Daniel.

After that, Daniel chooses another integer index

The game progresses turn by turn and as usual, Qingshan moves first. The rules follow:

If it is Qingshan’s turn, Qingshan must change x to such an index x` that

at the same time.

If it is Daniel’s turn, Daniel must change y to such an index y` that

at the same time.

The person who can’t make her or his move loses, and the other wins. That is the person to make the last move wins. You, as Qingshan’s fan, are asked to calculate the number of possible x to make Qingshan win in the case both players play optimally.

Problem Link: https://codeforces.com/problemset/problem/1495/B

Explanation

Example 1- 1 2 5 4 3

In the given permutation, Qingshan can choose integer 5 which is at x=3 to get the maximum possible moves.

Case 1 - Let’s assume, at the same time, that Daniel chooses x=5 to get maximum steps. In order to win, both of them need to strategize their position to have maximum steps.

Move 1- Qingshan moves one step right and gets to position 4 whose value is 4 and thus satisfies the condition for her move. Now, Daniel, currently at position 5, won’t have any possible move, and thus Qingshan Wins.

Case-2 - On the other side, Daniel can start from x=1, and thus having the next possible maximum steps.

Move 1- Qingshan moves one step left and moves to position 2 whose value is 2 and thus satisfies the condition for her move. Now, Daniel, currently at x=1 won’t have any possible move, and thus Qingshan Wins.

Example 2- 1 2 4 6 5 3 7

To get the maximum possible steps, let’s look at when Qingshan starts at x=4 which has a value of 6.

Case 1- Let’s assume that Daniel selects the position x=1 having value 1 and thus Qingshan plans to move right.

Move 1- Qingshan takes one step right to reach x=5 whereas Daniel also moves right to get at x=2.

Move 2- Qingshan moves another step towards right to get at x=6 and thus Daniel has a chance to move right to get at x=3.

Move 3- Now, Qingshan is out of steps as she can’t move another step. At the same time, Daniel still has moves available to go to the right. Hence Daniel wins.

Case 2- Let’s assume that Daniel selects the position x=1 having value 1 and thus Qingshan plans to move towards the left.

Move 1- Qingshan moves left to x=3 allowing Daniel to move right to x=2. Now, Qingshan is out of steps, and hence, Daniel wins.

We can see that Qingshan is losing in both cases.

Approach

Let’s assume that the permutations are steps of height the same as their value.

Qingshan’s movement- It is given that she can move one position left or right only on the condition that the value of the next position is less than the current value. Comparing it to the steps, she can only move downwards.

Daniel’s movement- It is given that he can move one position left or right only on the condition that the value of the next position is greater than the current value. Comparing it to the steps, he can only move upwards.

Analyzing the way for Qingshan to win, she can win only if she is at the peak of the longest decreasing or longest increasing substring as Qingshan needs to have the maximum possible steps in order to win. At the same time, Daniel can plan to win only if he is at the minimum of longest increasing or longest decreasing substring of numbers and will try to block the path of Qingshan. Hence, he will be at the minimum of the same peak on which Qingshan is.

Now, if two long substrings are having the same length and different peaks, that is, there are two peaks of the same length substring:- if Qingshan starts on the first peak, Daniel can select the minima of the other peak and thus will win as he is the one moving second.

If there is only one peak, Qingshan can start at the peak. If the peak is in a way, such that the length on both sides of the substring is equal, as in the example, then there are two routes for Qingshan, left or right because there are the same number of steps for Qingshan to step down on both the sides. She will decide her move according to the first move of Daniel.

If Daniel chooses one side, Qingshan can move on the same side. She will only win if the length of the substring is odd.

Qingshan can win if she selects the peak, and the length of the substring is odd. In all other cases, she will lose.

When there is only one possible move in a case, and Daniel has to move, he will block the path of Qingshan by moving on the step in between them.

Hence there will be only two answers, either she has a position where she will win, that is, one as the answer, or she doesn’t, thus giving a boolean value as an answer.

Solution

The Bool type function “check” takes a vector as an argument. The vector contains the values as the permutations of the game.

The first two loops in the function help in finding the longest substring, increasing and decreasing, and their peak by maintaining two vectors having substring lengths.

After that, the maxima of both peaks are stored in the variable peak.

Now, both the vectors of substring lengths are iterated and the number of the max peaks is calculated. If the number of max peaks is greater than 2, the function returns with a value of 0. Which means that there is no possible position.

Now, both the vectors are iterated again. If at any position, both increasing and decreasing peaks are the same, and if the length of the peak is odd, the function returns 1, referring that there exists one position where Qingshan can start.

Else, if any one of the conditions fails, Qingshan loses.