Problem A — Akash and the Fortnite String
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))
Problem B — Akash and the Lactation Pod
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)))
Problem C — Akash and the Mycelium Mushrooms
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.
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
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
We can translate all indices down $$$i$$$ without affecting the increase in the sum. Thus, the increases become
and
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)$$$.
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)))
Problem D — Akash and THE WAR ROOM
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))
Problem E — Akash and the Matrix
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))
Problem F — Akash and the Coins
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$$$.
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)))
