The string "abababab..." of length $$$k + 1$$$ is a $$$k$$$-Fortnite string. Then, set a variable s = "a", and add "a" or "b" to s $$$k$$$ times.

import sys, math, random
input = sys.stdin.readline
out = []
 
for _ in range(int(input())):
    n = int(input())
 
    s = "a"
    for i in range(k):
        if i % 2 == 0:
            s += "b"
        else:
            s += "a"

    out.append(s)
 
print("\n".join(out))

First, sort the array of initial positions $$$a$$$.

Note that if there are two business majors on consecutive squares, Akash cannot get past them. Thus, we can loop through $$$a$$$ and check that no two consecutive elements are consecutive.

If there are no business majors blocking the path, Akash can reach the lactation pod in $$$n - 1$$$ seconds.

If the positions of two consecutive business majors have the same parity, Akash can get by both without pausing. Otherwise, if they have the same parity, Akash must pause one second to ensure he can move past the second business major. Additionally, if the first business major is on an odd square, Akash must wait a second to get past the first business major.

We can keep a variable curParity representing the parity of the last processed business major. Initially, curParity is set to 0, representing the fact that if the first business major is on an odd square, Akash must wait a second. Also, keep a counter pauses to count how many times Akash must pause.

Then, loop through the array $$$a$$$. If the position of the next business major has a different parity than curParity, then increment pauses by $$$1$$$ and update curParity. Otherwise, Akash does not have to pause, and no action needs to be taken.

Then, we can print $$$n - 1$$$ added to the number of pauses.

import sys
input = sys.stdin.readline
out = []
 
for _ in range(int(input())):
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
 
    for i in range(m - 1):
        if A[i] + 1 == A[i+1]:
            out.append(-1)
            break
    else:
        curPar = 0
        pauses = 0
        for x in A:
            if x % 2 != curPar:
                curPar = x % 2
                pauses += 1
        
        out.append(n - 1 + pauses)
 
print("\n".join(map(str, out)))

Since the limit on $$$n$$$ is quite small, we can afford a solution in $$$O(n^2)$$$. This means we can loop through all possible swaps.

First, let's see how much any given swap adds to the final sum of the heights. Consider swapping $$$a_i$$$ and $$$a_j$$$. Then, after a week, instead of mushrooms with heights $$$ia_i$$$ and $$$ja_j$$$, we get mushrooms of heights $$$ia_j$$$ and $$$ja_i$$$. Thus, the swap contributed

to the final sum.

We can loop through the array and find the two best swaps, by finding the highest and second highest value of $$$(i - j)(a_i - a_j)$$$ over all pairs of indices $$$(i, j)$$$. Let the two best swaps be $$$(i, j)$$$ and $$$(h, k)$$$.

Note that if $$$n = 2$$$, there is only $$$1$$$ possible swap, so we deal with this case separately. Akash's choices are forced, so this should be easy.

If these indices are all distinct, then we just need to perform these two swaps.

Otherwise, the problem is more interesting. WLOG say they share an index, $$$i = h$$$. That is, the two best swaps are $$$(i, j)$$$ and $$$(i, k)$$$. We can be greedy here: the best sequence of swaps will always involve one of these two swaps (reasoning for this given below). Then, we can make each swap, and go through all possible swaps again, and see what combination gives us the best possible increase.

import sys, math
input = sys.stdin.readline
out = []
 
for _ in range(int(input())):
    n = int(input())
    A = list(map(int, input().split()))
    
    if n == 2:
        out.append(A[0] + 2 * A[1])
    else:
        bestScore = -math.inf
        bestPair = (0, 0)
        secBestScore = -math.inf
        secBestPair = (0, 0)
        for i in range(n - 1):
            for j in range(i+1, n):
                score = (A[i] - A[j]) * (j - i)
                if score > bestScore:
                    secBestScore = bestScore
                    secBestPair = bestPair
                    bestScore = score
                    bestPair = (i, j)
                elif score > secBestScore:
                    secBestScore = score
                    secBestPair = (i, j)
 
        s = set((*bestPair, *secBestPair))
        if len(s) == 4:
            i, j = bestPair
            A[i], A[j] = A[j], A[i]
            i, j = secBestPair
            A[i], A[j] = A[j], A[i]
        else:
            h, k = bestPair
            A[h], A[k] = A[k], A[h]
            bS1 = -math.inf
            bP1 = (0, 0)
            for i in range(n - 1):
                for j in range(i+1, n):
                    s = (A[i] - A[j]) * (j - i)
                    if s > bS1:
                        bS1 = s
                        bP1 = (i, j)
            A[h], A[k] = A[k], A[h]
            
            h, k = secBestPair
            A[h], A[k] = A[k], A[h]
            bS2 = -math.inf
            bP2 = (0, 0)
            for i in range(n - 1):
                for j in range(i+1, n):
                    s = (A[i] - A[j]) * (j - i)
                    if s > bS2:
                        bS2 = s
                        bP2 = (i, j)
            A[h], A[k] = A[k], A[h]
 
            if bestScore + bS1 > secBestScore + bS2:
                i, j = bestPair
                A[i], A[j] = A[j], A[i]
                i, j = bP1
                A[i], A[j] = A[j], A[i]
            else:
                i, j = secBestPair
                A[i], A[j] = A[j], A[i]
                i, j = bP2
                A[i], A[j] = A[j], A[i]
 
        t = 0
        for i, x in enumerate(A):
            t += (i+1) * x
        out.append(t)
 
print("\n".join(map(str, out)))

Let the binary representation of the initial investment be $$$2^na_n + 2^{n-1}a_{n-1} + \cdots + 2^2a_2 + 2a_1 + a_0$$$. The final amount will be:

Collecting terms, the coefficient of each $$$a_i$$$ is an alternating sum of powers of $$$2$$$.

Let's try to find a closed form for $$$2^n - 2^{n-1} + 2^{n-2} - \cdots \pm 1$$$. If $$$n$$$ is odd, then this sum ends in $$$- 1$$$. Pair each consecutive pair of powers of $$$2$$$. Their difference is just the smaller power of $$$2$$$. For example, $$$2^n - 2^{n-1} = 2^{n-1}$$$. Thus, the alternating sum is $$$2^{n-1} + 2^{n-3} + \cdots + 1$$$. This is just a sum of powers of $$$4$$$, which can be calculated.

If $$$n$$$ is even, we can multiply the sum for $$$n - 1$$$ by $$$2$$$ and add $$$1$$$.

An easy way to generate these sums is to take the previous sum, multiply it by $$$2$$$, and add or subtract $$$1$$$. Thus, let's create the array P that stores these sums of powers of $$$2$$$. The array is initialized as P = [1]. The largest alternating power sum we need to compute is when $$$n = k$$$, the number of days elapsed. Thus, iterate $$$k$$$ times, appending P[-1] * 2 + 1 or P[-1] * 2 - 1 to P. For reference, here are the first few terms of this array.

We want to find binary coefficients $$$a_n, a_{n-1}, \dots, a_1, a_0$$$ such that $$$a_np_n + a_{n-1}p_{n-1} + \cdots + a_1p_1 + a_0p_0 = x$$$, where $$$p_i$$$ is the $$$i$$$-th element of P and $$$x$$$ is the final amount of the investment.

Note that some numbers do not have a unique such representation; for example, $$$5$$$ can be represented as $$$0\cdot 1 + 0\cdot 1 + 0\cdot 3 + 1\cdot 5.$$$ or $$$1\cdot 1 + 1\cdot 1 + 1\cdot 3 + 0\cdot 5.$$$

We might notice that the "smaller" elements of $$$P$$$ – the elements that were formed by appending P[-1] * 2 - 1 – can be formed in multiple ways. Sums of these "smaller" elements can also be formed in multiple ways.

We can use an inductive argument to show that the following algorithm works, where $$$k = n$$$ initially: - If x is a "smaller" power, then set $$$a_k$$$ to $$$1$$$ and $$$a_{k-1}, a_{k-2}, \dots$$$ to $$$0$$$. Both this number and the number one smaller than this (where $$$a_k = 0$$$ and $$$a_{k-1}, a_{k-2}, \dots = 1$$$) are possible answers. - Otherwise, if P[k] < x, then set $$$a_k = 1$$$ and x -= P[k]. Decrement $$$k$$$ and repeat.

In practice, we might keep a variable val and add a certain power of 2 to val when setting $$$a_k = 1$$$, or store the digits $$$a_i$$$ in an array D (the second approach is implemented below). Also, this algorithm gets finicky at the end, as $$$1$$$ is both a "smaller" and "larger" power. In the implementation below, once $$$x$$$ becomes less than $$$3$$$, we treat it on a case-by-case basis.

import sys, math, random
input = sys.stdin.readline
out = []
 
for _ in range(int(input())):
    k, q = map(int, input().split())
 
    P = [1]
    shift = -1
    for _ in range(k):
        P.append(P[-1] * 2 + shift)
        shift *= -1
    
    O = set(P[3::2])
 
    for _ in range(q):
        n = int(input())
 
        includeOneBefore = False
        D = [(n - 1) // P[-1]]
        n = (n - 1) % P[-1] + 1
        for curP in reversed(P[2:]):
            if n == curP and n in O:
                D.append(1)
                includeOneBefore = True
                break
            else:
                if n >= curP:
                    D.append(1)
                    n -= curP
                else:
                    D.append(0)
 
        else:
            if n == 1:
                D.append(1)
                includeOneBefore = True
            elif n == 2:
                D.append(1)
                D.append(1)
 
        s = D[0] * 2 ** k
        power = 2 ** k
        for dig in D[1:]:
            s += dig * power
            power //= 2
 
        if includeOneBefore:
            out.append(' '.join(map(str, (s-1, s))))
        else:
            out.append(str(s))
 
print("\n".join(out))

Given two elements in the same column, their difference modulo $$$k - 1$$$ is invariant. For them to become $$$0$$$, this difference must be $$$0$$$ modulo $$$k - 1$$$. Thus, all we have to do is check that the elements in each column are equivalent modulo $$$k - 1$$$. It is possible to use an inductive argument to show that any such matrix can be reduced to a zero matrix.

Note, the case when $$$k = 1$$$ must be treated separately.

import sys, math, random
input = sys.stdin.readline
out = []
 
for _ in range(int(input())):
    n, m, k = map(int, input().split())
    A = []
    for _ in range(n):
        A.append(list(map(int, input().split())))
    
    if k == 1:
        for col in range(m):
            r = A[0][col]
            for row in range(1, n):
                if A[row][col] != r:
                    out.append("NO")
                    break
            
            else:
                continue
 
            break
 
        else:
            out.append("YES")
    
    elif k == 2:
        out.append("YES")
 
    else:
        for col in range(m):
            r = A[0][col] % (k - 1)
            for row in range(1, n):
                if A[row][col] % (k - 1) != r:
                    out.append("NO")
                    break
            
            else:
                continue
 
            break
 
        else:
            out.append("YES")
 
print("\n".join(out))

We can find the total number of "good" pairs by PIE. Then, we can find the total number of pairs with simple combinatorics. We can compare probabilities by doing some algebra on these numbers.

Then, we can binsearch on $$$k$$$ – if the function is increasing, then $$$k$$$ must be higher; otherwise, if the function is decreasing, $$$k$$$ must be lower.

Also, $$$k$$$ is optimized when $$$k \equiv -1 \pmod{m}$$$, so we only have to binsearch on these values of $$$k$$$. Actually, binsearch won't work unless we only binsearch on these values of $$$k$$$.

*Technically, this approach is not 100% correct. For example, a test case such as $$$n = 2$$$, $$$m = 4$$$, $$$a = [1, 188]$$$ produces the wrong answer because the function is not smooth. However, such a case is extremely rare and is only possible because of the extreme discrepancy between the two values in the array $$$a$$$. None of the test cases test on such a test case (verified by comparing with a brute force algorithm). Either way, the checker only confirms that the participant's answer has a better than or equal probability than this solution, so all this does is give some leeway on extreme edge cases. To make the problem 100% rigorous, perhaps another constraint on the input, such as each $$$a_i > 10$$$, would solve the issue.

import sys, math, random
input = sys.stdin.readline
out = []
 
def choose2(x):
    return x * (x - 1) // 2
 
def goodPairProbability(A, s, sChoose2, m, k):
    pileSize = s // k
    bigPileCount = s % k
 
    sameDenomination = sum(map(choose2, A))
    samePile = bigPileCount * choose2(pileSize + 1) + \
        (k - bigPileCount) * choose2(pileSize)
 
    overcounted = 0
    for ai in A:
        q = ai // k
        r = ai % k
        overcounted += r * choose2(q + 1) + (k - r) * choose2(q)
 
    return sChoose2 - sameDenomination - samePile + overcounted, choose2(s + k // m)
 
def findMax(A, m):
    s = sum(A)
    sChoose2 = choose2(s)
    
    if m == 1:
        lo = 2
    else:
        lo = 1
    
    if lo * m - 1 >= s:
        return s
 
    hi = (s + 1) // m
 
    while lo < hi:
        mid = lo + (hi - lo) // 2
        good1, total1 = goodPairProbability(A, s, sChoose2, m, mid * m - 1)
        good2, total2 = goodPairProbability(A, s, sChoose2, m, (mid + 1) * m - 1)
        if good1 * total2 < good2 * total1:
            lo = mid + 1
        else:
            hi = mid
 
    if lo == (s + 1) // m:
        good1, total1 = goodPairProbability(A, s, sChoose2, m, lo * m - 1)
        good2, total2 = goodPairProbability(A, s, sChoose2, m, s)
        if good1 * total2 < good2 * total1:
            r = s
        else:
            r = lo * m - 1
    else:
        r = lo * m - 1
 
    return r
 
for _ in range(int(input())):
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
 
    out.append(findMax(A, m))
 
print("\n".join(map(str, out)))