[Problem A — Akash and the Fortnite String](https://codeforces.me/gym/512940/problem/A)↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
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))↵
~~~~~↵
</spoiler>↵
↵
[Problem B — Akash and the Lactation Pod](https://codeforces.me/gym/512940/problem/A)↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
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)))↵
~~~~~↵
</spoiler>↵
↵
[Problem C — Akash and the Mycelium Mushrooms](https://codeforces.me/gym/512940/problem/A)↵
↵
<spoiler summary="Solution">↵
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 $$ia_j + ja_i - (ia_i - ja_j) = i(a_j - a_i) + j(a_i - a_j) = (i - j)(a_i - a_j)$$ 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.↵
↵
↵
<spoiler summary="Proof sketch for greedy">↵
AFSOC the best sequence of swaps doesn't involve $(i, j)$ or $(i, k)$.↵
↵
If either of the two other swaps are independent of $(i, j)$ and $(i, k)$, then doing $(i, j)$ and the independent swap is guaranteed to be better.↵
↵
We can make a stronger claim: both swaps must use the index $i$. This is because if one of them does not, then since they cannot be independent, they must share an index $j$ or $k$ (WLOG say the other swap shares $j$).↵
Then doing $i, k$ and this other swap will always be better (or $(i, j$ if they share $k$).↵
↵
Thus, both other swaps have to involve index $i$.↵
↵
Next, note that we cannot have $j < i < k$ or $j > i > k$, since then the swap $(j, k)$ would be best.↵
Thus, $i$ is either the smallest or largest index out of $i, j, k$.↵
If $i$ is the smallest, then WLOG let $j < k$.↵
Let the other swaps be $(i, s)$ and $(i, t)$ where $s < t$.↵
↵
Performing the swaps $(i, s)$ and $(i, t)$ effectively reorders the elements $a_i, a_s, a_t \to a_t, a_i, a_s$.↵
The total increase in the final sum is $$ia_t + sa_i + ta_s - (ia_i + sa_s + ta_t) = i(a_t - a_i) + s(a_i - a_s) + t(a_s - a_t).$$↵
Alternatively, performing the two swaps $(i, j)$ and $(i, s)$ reorders these elements $a_i, a_j, a_s \to a_s, a_i, a_j$, which results in an increase of $$ia_s + ja_i + sa_j - (ia_i + ja_j + sa_s) = i(a_s - a_i) + j(a_i - a_j) + s(a_j - a_s).$$↵
↵
We can translate all indices down $i$ without affecting the increase in the sum.↵
Thus, the increases become↵
$$(s - i)(a_i - a_s) + (t - i)(a_s - a_t)$$↵
and↵
$$(j - i)(a_i - a_j) + (s - i)(a_j - a_s).$$↵
↵
Then, compare the first term of the first expression $(s - i)(a_i - a_s)$ and the second term of the second expression $(s - i)(a_j - a_s)$.↵
Clearly, $a_i - a_s > a_j - a_s$ so the second term is larger.↵
↵
Next, compare the remaining two terms $(t - i)(a_s - a_t)$ and $(j - i)(a_i - a_j)$.↵
Again, it is clear that the second is larger.↵
↵
Thus, swapping $(i, j)$ and $(i, s)$ is always better.↵
↵
Hence, it is impossible for the two best swaps not to include one of $(i, j)$ or $(i, k)$.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
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)))↵
~~~~~↵
</spoiler>↵
↵
[Problem D — Akash and THE WAR ROOM](https://codeforces.me/gym/512940/problem/D)↵
↵
<spoiler summary="Solution">↵
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:↵
↵
$$2^na_n + 2^{n-1}a_{n-1} + \cdots + 2^2a_2 + 2a_1 + a_0$$↵
$$-(2^{n-1}a_n + 2^{n-2}a_{n-1} + \cdots + 2a_2 + a_1)$$↵
$$+2^{n-2}a_n + 2^{n-3}a_{n-1} + \cdots + a_2$$↵
$$\dots$$↵
↵
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.↵
$$P = [1, 1, 3, 5, 11, 21, 43, 85, \dots].$$↵
↵
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.↵
↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
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))↵
~~~~~↵
</spoiler>↵
↵
[Problem E — Akash and the Matrix](https://codeforces.me/gym/512940/problem/E)↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
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))↵
~~~~~↵
</spoiler>↵
↵
[Problem F — Akash and the Coins](https://codeforces.me/gym/512940/problem/F)↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
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)))↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
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))↵
~~~~~↵
</spoiler>↵
↵
[Problem B — Akash and the Lactation Pod](https://codeforces.me/gym/512940/problem/A)↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
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)))↵
~~~~~↵
</spoiler>↵
↵
[Problem C — Akash and the Mycelium Mushrooms](https://codeforces.me/gym/512940/problem/A)↵
↵
<spoiler summary="Solution">↵
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 $$ia_j + ja_i - (ia_i - ja_j) = i(a_j - a_i) + j(a_i - a_j) = (i - j)(a_i - a_j)$$ 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.↵
↵
↵
<spoiler summary="Proof sketch for greedy">↵
AFSOC the best sequence of swaps doesn't involve $(i, j)$ or $(i, k)$.↵
↵
If either of the two other swaps are independent of $(i, j)$ and $(i, k)$, then doing $(i, j)$ and the independent swap is guaranteed to be better.↵
↵
We can make a stronger claim: both swaps must use the index $i$. This is because if one of them does not, then since they cannot be independent, they must share an index $j$ or $k$ (WLOG say the other swap shares $j$).↵
Then doing $i, k$ and this other swap will always be better (or $(i, j$ if they share $k$).↵
↵
Thus, both other swaps have to involve index $i$.↵
↵
Next, note that we cannot have $j < i < k$ or $j > i > k$, since then the swap $(j, k)$ would be best.↵
Thus, $i$ is either the smallest or largest index out of $i, j, k$.↵
If $i$ is the smallest, then WLOG let $j < k$.↵
Let the other swaps be $(i, s)$ and $(i, t)$ where $s < t$.↵
↵
Performing the swaps $(i, s)$ and $(i, t)$ effectively reorders the elements $a_i, a_s, a_t \to a_t, a_i, a_s$.↵
The total increase in the final sum is $$ia_t + sa_i + ta_s - (ia_i + sa_s + ta_t) = i(a_t - a_i) + s(a_i - a_s) + t(a_s - a_t).$$↵
Alternatively, performing the two swaps $(i, j)$ and $(i, s)$ reorders these elements $a_i, a_j, a_s \to a_s, a_i, a_j$, which results in an increase of $$ia_s + ja_i + sa_j - (ia_i + ja_j + sa_s) = i(a_s - a_i) + j(a_i - a_j) + s(a_j - a_s).$$↵
↵
We can translate all indices down $i$ without affecting the increase in the sum.↵
Thus, the increases become↵
$$(s - i)(a_i - a_s) + (t - i)(a_s - a_t)$$↵
and↵
$$(j - i)(a_i - a_j) + (s - i)(a_j - a_s).$$↵
↵
Then, compare the first term of the first expression $(s - i)(a_i - a_s)$ and the second term of the second expression $(s - i)(a_j - a_s)$.↵
Clearly, $a_i - a_s > a_j - a_s$ so the second term is larger.↵
↵
Next, compare the remaining two terms $(t - i)(a_s - a_t)$ and $(j - i)(a_i - a_j)$.↵
Again, it is clear that the second is larger.↵
↵
Thus, swapping $(i, j)$ and $(i, s)$ is always better.↵
↵
Hence, it is impossible for the two best swaps not to include one of $(i, j)$ or $(i, k)$.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
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)))↵
~~~~~↵
</spoiler>↵
↵
[Problem D — Akash and THE WAR ROOM](https://codeforces.me/gym/512940/problem/D)↵
↵
<spoiler summary="Solution">↵
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:↵
↵
$$2^na_n + 2^{n-1}a_{n-1} + \cdots + 2^2a_2 + 2a_1 + a_0$$↵
$$-(2^{n-1}a_n + 2^{n-2}a_{n-1} + \cdots + 2a_2 + a_1)$$↵
$$+2^{n-2}a_n + 2^{n-3}a_{n-1} + \cdots + a_2$$↵
$$\dots$$↵
↵
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.↵
$$P = [1, 1, 3, 5, 11, 21, 43, 85, \dots].$$↵
↵
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.↵
↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
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))↵
~~~~~↵
</spoiler>↵
↵
[Problem E — Akash and the Matrix](https://codeforces.me/gym/512940/problem/E)↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
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))↵
~~~~~↵
</spoiler>↵
↵
[Problem F — Akash and the Coins](https://codeforces.me/gym/512940/problem/F)↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
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)))↵
~~~~~↵
</spoiler>↵
↵
