Permutation Game (Codeforces 1772E)
Tags: Others, games

Two players are playing a game. They have a permutation of integers $$$1$$$, $$$2$$$, ..., $$$n$$$ (a permutation is an array where each element from $$$1$$$ to $$$n$$$ occurs exactly once). The permutation is not sorted in either ascending or descending order (i. e. the permutation does not have the form $$$[1, 2, \dots, n]$$$ or $$$[n, n-1, \dots, 1]$$$).Initially, all elements of the permutation are colored red. The players take turns. On their turn, the player can do one of three actions:  rearrange the elements of the permutation in such a way that all red elements keep their positions (note that blue elements can be swapped with each other, but it's not obligatory);  change the color of one red element to blue;  skip the turn. The first player wins if the permutation is sorted in ascending order (i. e. it becomes $$$[1, 2, \dots, n]$$$). The second player wins if the permutation is sorted in descending order (i. e. it becomes $$$[n, n-1, \dots, 1]$$$). If the game lasts for $$$100^{500}$$$ turns and nobody wins, it ends in a draw.Your task is to determine the result of the game if both players play optimally.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 5 \cdot 10^5$$$) — the size of the permutation.The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ — the permutation itself. The permutation $$$p$$$ is not sorted in either ascending or descending order.The sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output: For each test case, print First if the first player wins, Second if the second player wins, and Tie if the result is a draw.

Note: Let's show how the first player wins in the first example.They should color the elements $$$3$$$ and $$$4$$$ blue during their first two turns, and then they can reorder the blue elements in such a way that the permutation becomes $$$[1, 2, 3, 4]$$$. The second player can neither interfere with this strategy nor win faster.

Sample Inputs:
4
4
1 2 4 3
3
2 3 1
5
3 4 5 2 1
6
1 5 6 3 2 4

Sample Outputs:
First
Tie
Second
Tie

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def ii():
    return int(input())

def li():
    return list(map(int, input().split()))

def si():
    return input()

def ti():
    return map(int, input().split())
for _ in range(ii()):
    n = ii()
    p = li()
    f = 0
    s = 0
    c = 0
    for i in range(n):
        if p[i] != i + 1 and p[i] != n - i:
            c += 1
        elif p[i] != i + 1:
            f += 1
        elif p[i] != n - i:
            s += 1
    if f <= s:
        if f + c <= s:
            print('First')
        else:
            print('Tie')
    elif s + c < f:
        print('Second')
    else:
        print('Tie')

Solution (Python):
import sys

def first(a, b, c):
    take = None
    while True:
        if a > 0:
            a -= 1
        elif c > 0:
            if take is None:
                take = 1
            c -= 1
        else:
            return (1, take)
        if b > 0:
            b -= 1
        elif c > 0:
            if take is None:
                take = 2
            c -= 1
        else:
            return (2, take)

def second(a, b, c, take):
    can = True
    while True:
        if a > 0:
            a -= 1
        elif c > 0:
            if take != 1 or can:
                c -= 1
                can = True
        else:
            return 1
        if b > 0:
            b -= 1
        elif c > 0:
            if take != 2 or can:
                c -= 1
        else:
            return 2

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    p = list(map(int, inp().split()))
    (a, b, c) = (0, 0, 0)
    for i in range(n):
        if p[i] != i + 1:
            if p[i] != n - i:
                c += 1
            else:
                a += 1
        elif p[i] != n - i:
            b += 1
    while True:
        if a > 0:
            a -= 1
        elif c == 0:
            print('First')
            return
        else:
            if c <= b:
                print('First')
            else:
                print('Tie')
            return
        if b > 0:
            b -= 1
        elif c == 0:
            print('Second')
            return
        else:
            if c <= a:
                print('Second')
            else:
                print('Tie')
            return
    return
    print(a, b, c)
    (basic, take) = first(a, b, c)
    print(basic, take)
    if basic == take:
        if basic == 1:
            print('First')
        else:
            print('Second')
    else:
        smart = second(a, b, c, take)
        if smart != take:
            print('Tie')
        elif basic == 1:
            print('First')
        else:
            print('Second')

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
from math import gcd, factorial, ceil, pi
from itertools import accumulate
from bisect import bisect_left, bisect_right, insort_left, insort_right
INF = float('inf')
MOD = 998244353
ALPHA = 'abcdefghijklmnopqrstuvwxyaz'
input = stdin.readline

def inpi():
    return int(input())

def inpf():
    return float(input())

def inpis():
    return map(int, input().split())

def inpfs():
    return map(float, input().split())

def inpli():
    return list(map(int, input().split()))

def inpli2(n):
    return [int(input()) for _ in range(n)]

def inplf():
    return list(map(float, input().split()))

def inplf2(n):
    return [float(input()) for _ in range(n)]

def inpls():
    return input().split()

def inpls2(n):
    return [input() for _ in range(n)]

def inpset():
    return set(map(int, input().split()))

def inpmat(n):
    return [list(map(int, input().split())) for _ in range(n)]

def lcm(a, b):
    return a * b // gcd(a, b)

def dist(xn, yn, xk, yk):
    return ((xn - xk) ** 2 + (yn - yk) ** 2) ** 0.5
for _ in range(inpi()):
    n = inpi()
    p = inpli()
    need_f = 0
    need_s = 0
    need_both = 0
    for i in range(n):
        if p[i] != i + 1 and p[i] != n - i:
            need_both += 1
        elif p[i] != i + 1:
            need_f += 1
        elif p[i] != n - i:
            need_s += 1
    if need_s - need_f >= need_both:
        print(f'First')
    elif need_f - need_s > need_both:
        print(f'Second')
    else:
        print(f'Tie')