Codeforces Round #706 Let's Go Hiking - Game

Solution

Not hard, But need consider carefully. Still can be kind of game problem.

Let define the concepts below:

1. Top of mountain，Bottom of mountain。Top of mountain means the point $i$ which $p_i > p_{i\pm{1}}$. Bottom of mountain means the $i$ which $p_i<p_{i\pm{1}}$.
2. Left/Right side of mountain. Left/Right the side between two nearby top of mountain and bottom of mountain.
3. Length of side. Of course the length of the side of mountain. The length of side can apply for left side and right side.

conclusion:
Let's say the maximal value of Length of side is max.
If and only if there is only one top of mountain $i$, both the lenght of left side of $i$ and the lenght of right side of $i$ are max and the max is odd. Then this $i$ is the only solution.
Otherwise, just print 0.

Prove case by case:

1. If Qingshan not choose the top of mountain which length is not max. Then Dainel only need start from the bottom of mountain which length is max.
2. If there are no less than two side's length is max, and the these two side is not for the same top/bottom of mountain. Then whatever Qingshan choose (of course one of top of mountain), Daniel only need choose another one. So no possible two win. Just print 0.
3. If the two side which length is max is two side for a bottom of mountain. Then Daniel only need choose the bottom of mountain. Then Qingshan will lose. Just print 0.
4. If only one side which length is max. Then Dainel only need choose the point in the side. Which distance between that point and the top of mountain is even, and this distance longer than length of another side. Then Qingshang will always lose. Because if Qingshan go to Daniel side, because it's even, it will lose. If Qingshan go to another side, then the length is lesser than Daniel. So just print 0.
5. If both side of top of mountain is max. But the max is even. Then of cours, Qingshan will chose the top and Dainel will chose the bottom. If Qingshan go with Dainel side, then because of even, Qingshan will lose. If Qingshan go with another side, then because of same length， Qingshan will lose. Just print 0.
6. If not all the case above. the case is the length of both side of top is same, and this lenght is max, and this max is odd. Then Qingshan chose the top, Daniel chose bottom can win. Print 1.

Code

Submission #109888377 - Codeforces

Codeforces. Programming competitions and contests, programming community

Codeforces

Forgot case #5 when I was solving this problem at beginning. Got WA answer before I realized that.