Since it does not take time to place your hand over the first letter, you need to calculate the sum of the distances between the keyboard keys corresponding to each pair of adjacent letters of the word, that is $$$ \sum_{i=2}^{n} \left| \text{pos}(s_i) - \text{pos}(s_{i-1}) \right|$$$ where $$$pos(c)$$$ is the position of the keyboard key corresponding to the letter $$$c$$$.

In order to calculate this sum, let's just iterate through the word $$$s$$$ with the for loop and find the differences between the positions of $$$s_i$$$ and $$$s_{i−1}$$$ on the keyboard.

import sys
    
def solve():

    s = sys.stdin.readline().strip()
    t = sys.stdin.readline().strip()

    pos = {}
    for i, ch in enumerate(s):
        pos[ch] = i
        
    ans = 0
    for i in range(1, len(t)):
        ans += abs(pos[t[i]] - pos[t[i - 1]])
    return ans

t = int(sys.stdin.readline().strip())
for _ in range(t):
    print(solve())

We can sort both $$$a$$$ and $$$b$$$ and use counters to track how many consecutive times we've used characters from each string. Then, as we iterate through both strings, we check the smallest available character in each. If the smallest character is in a string we've already used k times consecutively, we skip it; otherwise, we choose that character, remove it, and reset the counter for the other string.

for _ in range(int(input())): n, m, k = map(int, input().split()) a = sorted(input(), reverse=True) b = sorted(input(), reverse=True)

k_a = k_b = 0 ans = []

while a and b: if (a[-1] >= b[-1] and k_a < k) or k_b >= k: ans.append(b.pop()) k_a += 1 k_b = 0 else: ans.append(a.pop()) k_b += 1 k_a = 0

print("".join(ans))

Let's look at an analogy for this game.

• If Alice takes an even number $$$x$$$, she adds $$$x$$$ points to the global result, otherwise $$$0$$$;
• If Bob takes an odd number $$$x$$$, he adds $$$−x$$$ points to the global result, otherwise $$$0$$$;
• Alice wants to maximize the global result and Bob wants to minimize it.

Obviously, this game is completely equivalent to the conditional game.

Suppose now it's Alice's move. Let's look at some number $$$x$$$ in the array.

• If this number is even, then taking it will add $$$x$$$ points, and giving it to Bob will add $$$0$$$ points.
• If this number is odd, then taking it will add $$$0$$$ points, and giving it to Bob will add $$$−x$$$ points.

So taking the number $$$x$$$ by $$$x$$$ points is more profitable than not taking it (regardless of the parity). To maximize the result, Alice should always take the maximum number in the array.

Similar reasoning can be done for Bob. In the task, it was necessary to sort the array and simulate the game.

from sys import stdin


def input(): return stdin.readline().strip()

T = int(input())

for _ in range(T):
    N = int(input())
    a = sorted(map(int, input().split()), reverse=True)

    alice = bob = 0
    alice_turn = 1
    for ai in a:
        if alice_turn:
            if ai%2 == 0:
                alice += ai
        else:
            if ai%2:
                bob += ai
        alice_turn ^= 1
    
    if alice > bob:
        print("Alice")
    elif bob > alice:
        print("Bob")
    else:
        print("Tie")

We can easily employ a Binary Search Algorithm to find a player $$$y$$$ with the minimum token that can win the game by favoring all the random decisions toward this player $$$y$$$. Then any player that has greater tokens than this player $$$y$$$ will win the game. This will reduce the time complexity to $$$O(nlogn)$$$ instead of $$$O(n^2)$$$.

for _ in range(int(input())):
    n = int(input())
    players = list(map(int, input().split()))
    tokens = sorted(players)

    left, right = 0, n - 1
    tot_sum = sum(tokens)
    init_point = right
    while left <= right:
        mid = left + (right - left) // 2
        curr_sum = sum(tokens[:mid + 1])
        for i in range(mid + 1, n):
            if curr_sum < tokens[i]:
                break
            curr_sum += tokens[i]
            
        if curr_sum == tot_sum:
            right = mid - 1
            init_point = mid 
        else:
            left = mid + 1 
            
    print(n - init_point)
    print(*[indx + 1 for indx in range(n) if players[indx] >= tokens[init_point]])

Firstly, let's prove that the size of the answer is not greater than $$$3$$$ . Suppose that the answer equals to $$$4$$$ . Let $$$a,b,c,d$$$ be coordinates of the points in the answer (and $$$a<b<c<d$$$ ). Let $$$dist(a,b)=2^k$$$ and $$$dist(b,c)=2^l$$$ . Then $$$dist(a,c)=dist(a,b)+dist(b,c)=2^k+2^l=2^m$$$ (because of the condition). It means that $$$k=l$$$ . Conditions must hold for a triple $$$b,c,d$$$ too. Now it is easy to see that if $$$dist(a,b)=dist(b,c)=dist(c,d)=2^k$$$ then $$$dist(a,d)=dist(a,b)∗3$$$ that is not a power of two. So the size of the answer is not greater than $$$3$$$ .

Firstly, let's check if the answer is $$$3$$$ . Iterate over all middle elements of the answer and over all powers of two from $$$0$$$ to $$$30$$$ inclusively. Let $$$xi$$$ be the middle element of the answer and $$$j$$$ — the current power of two. Then if there are elements $$$xi−2^j$$$ and $$$xi+2^j$$$ in the array then the answer is $$$3$$$ .

Now check if the answer is $$$2$$$ . Do the same as in the previous solution, but now we have left point $$$xi$$$ and right point $$$xi+2^j$$$ .

If we did not find answer of lengths $$$3$$$ or $$$2$$$ then print any element of the array.

The solution above have time complexity $$$O(n⋅log10**10)$$$ .

from collections import Counter
     
def find_three(nums, dic):
    # Find a sequence of three numbers with differences of powers of two
    for num in nums:
        i = 1
        while i <= 10 ** 10:
            if num + i in dic and num + 2 * i in dic:
                return 3, [num, num + i, num + 2 * i]
            i *= 2
    return None
 
def find_two(nums, dic):
    # Find a sequence of two numbers with a difference of a power of two
    for num in nums:
        i = 1
        while i <= 10 ** 10:
            if num + i in dic:
                return 2, [num, num + i]
            i *= 2
    return None
 
def main():
    n = int(input().strip())
    nums = sorted(map(int, input().strip().split()))
    dic = Counter(nums)
    
    # Check for sequences of 3, then 2, or return a single number
    result = find_three(nums, dic) or find_two(nums, dic) or (1, [nums[0]])
    
    length, sequence = result
    print(length)
    print(*sequence)
 
if __name__ == "__main__":
    main()