The reverse of the Collatz conjecture can be written as follows:

• Multiply $$$x$$$ by $$$2$$$ (if $$$2x$$$ was even)
• Subtract $$$1$$$ from $$$x$$$, then divide by $$$3$$$ (if $$$\frac{x-1}{3}$$$ is an integer and is odd).

In this problem, we can ignore the second type completely, because $$$2x$$$ is always an integer and is always even. We can simply print out $$$x\cdot 2^k$$$ as our answer.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n,k = map(int,input().split())
    print(k<<n)

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

We can show that the permutation $$$q$$$ defined by $$$q_i=n+1-p_i$$$ satisfies all required properties.

• Proof $$$q$$$ is a permutation: Since $$$p_i+q_i=n+1$$$ and elements of $$$p$$$ ranges from $$$1$$$ to $$$n$$$, elements of $$$q$$$ will also range from $$$1$$$ to $$$n$$$. Additionally, since $$$p$$$ is a permutation (all elements are distinct), $$$q$$$ must also be a permutation.
• Proof $$$GCD(p_i+q_i, p_{i+1}+q_{i+1})\geq 3$$$: Since $$$n\geq2$$$, $$$n+1\geq 3$$$. The GCD of any number with itself is itself.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = [n - i + 1 for i in a]
    print(*b)

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

First, observe that in order to maximize the sum of two positive numbers given that their product must stay constant, it is optimal to minimize one number as much as possible (and in the process, maximize the other).

Let's do casework on the parity of $$$a$$$ and $$$b$$$:

• $$$a$$$, $$$b$$$ are both even: in this case, we cannot choose a $$$k$$$ such that $$$\frac{b}{k}$$$ is odd, as $$$a$$$ will stay even, and $$$a+b$$$ will be odd. The optimal $$$k$$$ here is $$$\frac{b}{2}$$$.
• $$$a$$$ is even, but $$$b$$$ is odd: In this case, we should print $$$-1$$$, as it is impossible to make $$$a+b$$$ even.
• $$$a$$$ is odd, $$$b$$$ is divisible by $$$2$$$ and not $$$4$$$: This case is also impossible. No matter what $$$k$$$ we choose, one of $$$a$$$ and $$$b$$$ will always be odd.
• $$$a$$$ is odd, $$$b$$$ is divisible by $$$4$$$: Even though $$$a+b$$$ is initially odd, it is possible to make $$$a+b$$$ even in this case by choosing a $$$k$$$ so that $$$k$$$ and $$$\frac{b}{k}$$$ are both even. Once again, the optimal $$$k$$$ to use is $$$\frac{b}{2}$$$.
• $$$a$$$ and $$$b$$$ are both odd: In this case, the optimal $$$k$$$ to use is $$$b$$$. Note that $$$a+b$$$ will always be even no matter what $$$k$$$ is chosen.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    b,a = map(int,input().split())
    sol = -1
    if (a + b) & 1 == 0: sol = a + b
    if a % 2 == 1 and b % 2 == 1: sol = max(sol, a * b + 1)
    elif a % 2 == 0 and (a % 4 == 0 or b % 2 == 0): sol = max(sol, 2 + (a * b) // 2)
    print(sol)

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

First, we should observe that the number of occurrences of $$$x$$$ in $$$b$$$ must be a multiple of $$$x$$$. This is true because if we have $$$b_i=k$$$, then there are $$$k$$$ occurrences of $$$a_i$$$ in the original array. Suppose we group up all equal elements in the array $$$a$$$. If the number of occurrences of $$$b_i$$$ is not a multiple of $$$b_i$$$, then there is at least one group which doesn't have $$$b_i$$$ elements. This is a contradiction.

If the number of occurrences of $$$b_i$$$ is a multiple of $$$b_i$$$ for all $$$i$$$, then we can construct as follows:

• keep a varible $$$z=1$$$.
• For each $$$x$$$ from $$$1$$$ to $$$n$$$, iterate through the all indices $$$i$$$ with $$$b_i=x$$$. Label the first $$$x$$$ numbers as $$$z$$$, then increase $$$z$$$ by $$$1$$$. Continue until all indices are labeled.

This solution works in $$$O(n)$$$.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    FRQ = [[] for _ in range(n+1)]
    for i in range(n): FRQ[a[i]].append(i)
    b = [0 for _ in range(n)]
    cnt = 1
    for i in range(1,n+1):
        if len(FRQ[i]) % i: print(-1);break
        else:
            c=0
            while c < len(FRQ[i]):
                for v in range(i):
                    b[FRQ[i][c]] = cnt
                    c+=1
                cnt+=1
    else:print(*b)

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let's first determine how to run the operation a single time.

Let $$$m$$$ be the MEX of the array, and let $$$occ_i$$$ be the number of occurrences of the number $$$i$$$. We have these cases:

• If $$$a_i \gt m$$$, then $$$a_i$$$ will become $$$m$$$.
• If $$$occ_{a_i}=1$$$ and $$$a_i \lt m$$$, then $$$a_i$$$ will still be itself after the operation. This is because after we remove $$$a_i$$$ from the array, $$$a_i$$$ will be the new MEX.
• if $$$occ_{a_i} \gt 1$$$ and $$$a_i \lt m$$$, then $$$a_i$$$ will become $$$m$$$. This is because even after removing $$$a_i$$$, there will still be at least one more occurrence of $$$a_i$$$, so $$$a_i$$$ will simply become the MEX of the whole array.

From this, we notice that numbers with frequency $$$1$$$ and less than the MEX will not change, while other numbers will map to the MEX. We now discuss several possible cases:

• If $$$a$$$ is a permutation of $$$[0,1,\ldots,n-1]$$$, then doing operations on $$$a$$$ will not change anything about the array.
• Otherwise, let $$$x$$$ be the smallest number with $$$occ_x \neq 1$$$. If $$$occ_x=0$$$, then $$$x$$$ is the MEX of $$$a$$$. After the first operation, all numbers greater than $$$x$$$ will get mapped to $$$x$$$ while all numbers less than $$$x$$$ will map to themselves (because $$$occ_i=1$$$ for all $$$i\leq n$$$. Now, all occurrences of $$$x$$$ (if there are more than $$$1$$$) will map to $$$x+1$$$. The array will then continuously alter between these two states. Be careful of the edge case $$$[0,1,\ldots,n-2,n]$$$, where it will map to the permutation case and not change again.
• Otherwise, $$$occ_x \gt 1$$$. Let $$$m$$$ be the MEX of $$$a$$$. After the first operation, all numbers less than $$$x$$$ will map to itself, while all occurrences of $$$x$$$ will map to $$$m$$$. This array is now the case of the previous one (where the smallest $$$x$$$ with $$$occ_x \neq 1$$$ will have $$$occ_x=0$$$), meaning that it will continuously alter between two states.

In all cases, after at most two operations, the array will only alter between two states after at most one operation. So it is possible to simulate the operation $$$min(k, k MOD 2 + 2)$$$ times and print out the sum.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n,k = map(int,input().split())
    a = list(map(int,input().split())); l = []; sl = -1
    a.sort()
    while k and l != a:
        k -= 1
        sl = list(l)
        l = list(a)
        F = [0 for _ in range(n+1)]
        for i in a:F[i] += 1
        B = []
        mex = 0
        while F[mex]: mex += 1
        mm = 0
        for i in a:
            if F[i] > 1: B.append(mex)
            else: B.append(mm)
            if i == mm: mm += 1
        B.sort()
        a = B
        if a == sl:
            k &= 1
    print(sum(a))

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

What is the condition for being able to make $$$x_i=y_i$$$? It is always possible if $$$x_i=y_i$$$ already. If $$$x_i \gt y_i$$$, it's only possible if $$$a_i$$$ is not already a prefix maximum. If $$$x_i \lt y_i$$$, it's only possible if there is a prefix maximum in the array before $$$i$$$ that is at least equal to $$$y_i$$$.

Let's formalize the conditions for the last two cases. If $$$x_i \gt y_i$$$, then there must exist an index $$$j \lt i$$$ such that $$$x_j \gt x_i$$$ (as this guarantees $$$a_i$$$ to not be a prefix maximum). If $$$x_i \lt y_i$$$, then there must exist an index $$$j \lt i$$$ such that $$$x_j \geq y_i$$$, as this ensures you can change $$$x_i$$$ to $$$y_i$$$. Let's calculate the correct $$$j$$$ for each $$$i$$$ in the original array $$$a$$$. This can be done in a variety of data structures. I used a set, but it is possible to use a segment tree or a stack as well.

Finally, to find the sum over all subarrays in $$$a$$$, for each index $$$i$$$ we need to calculate the number of subarrays containing $$$i$$$ where we can make $$$a_i=b_i$$$. If $$$x_i=y_i$$$, all subarrays containing $$$i$$$ counts, so we add $$$(i)(n-i+1)$$$ to our answer. Otherwise, let $$$prev_i$$$ be the number we calculated before. We can add $$$(i-prev_i+1)(n-i+1)$$$ to our answer.

import sys
input = sys.stdin.readline
class SparseTarble():
    def __init__(self,arr,op=min):
        self.n = len(arr)
        self.log = self.n.bit_length()
        self.PRE = [0 for _ in range(self.log * self.n)]
        for i in range(self.n):
            lsb = (i+1) & (-i-1)
            v = lsb.bit_length() - 1
            jo = self.n * v
            self.PRE[jo + i] = arr[i]
            for j in range(i+1,min(self.n,i+lsb)):
                self.PRE[jo + j] = op(self.PRE[jo+j-1],arr[j])
            for j in range(i-1, i - lsb, -1):
                self.PRE[jo + j] = op(arr[j],self.PRE[jo+j+1])
        self.op = op
    def query(self,l,r):
        assert(l < r)
        bit = (r ^ l).bit_length() - 1
        return self.op(self.PRE[bit * self.n + l], self.PRE[bit * self.n + r - 1])
for _ in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    sq = SparseTarble(a,max)
    sol = 0
    for i in range(n):
        if a[i] == b[i]: sol += (n * n + n) // 2; continue
        lo = -1; hi = i
        while lo + 1 < hi:
            mid = (lo + hi) // 2
            if sq.query(mid,i) >= max(a[i],b[i]): lo = mid
            else: hi = mid
        lo+=1
        sol += lo * (n - i)
    print(sol)

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let $$$dp_1(i)$$$ be a boolean on whether Cry will win if the token is on node $$$i$$$ and it is currently Cry's turn, and let $$$dp_2(i)$$$ be a boolean on whether Cry will win a game if we are on node $$$i$$$ and it is currently River's turn. Initially, $$$dp_1(i)=1$$$ and $$$dp_2(i)=1$$$ for all $$$1 \leq i \leq n$$$. Assuming we maintain the correct $$$dp$$$ values all the time, queries of the second type is easily answered by looking at the dp state.

How can we maintain the correct $$$dp$$$ values after a node is painted red? Consider BFS on the reverse graph. Suppose node $$$u$$$ was turned red. First, node $$$u$$$ becomes winning for River immediately no matter whose turn it is. Now, if a node becomes losing on Cry's turn, all nodes that are adjacent to that node in the reverse graph becomes winning on River's turn (as River can move the node to a node that loses on Cry's turn). If a node becomes losing on River's turn, consider the set of nodes adjacent on the reverse graph. If all nodes adjacent to that node (on the original graph) is losing on River's turn, then that node is also losing on Cry's turn, as no matter which node he decides to move to, it will be going to a lost node.

Keeping track of the DP states seems like it will be $$$O(n^2)$$$ complexity. However, since each node is visited only twice (once for updating $$$dp_1$$$ and once for updating $$$dp_2$$$, this solution will amortize to $$$O(n+m)$$$. Keep note that we should maintain a third array that counts how many adjacent nodes are losing on River's turn, so we don't have to check manually every time.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n,m,q = map(int,input().split())
    G = [[] for _ in range(n+1)]
    A = [1 for _ in range(n+1)]
    B = [0 for _ in range(n+1)]
    C = [0 for _ in range(n+1)]
    for _ in range(m):
        a,b = map(int,input().split())
        G[b].append(a)
        C[a] += 1
    for _ in range(q):
        a,b = map(int,input().split())
        if a == 2:
            if A[b]: print("yes")
            else: print("no")
        else:
            q = []
            if A[b] == 1: q.append((b,0))
            if B[b] == 0: q.append((b,1)); B[b] = 1
            for x,t in q:
                if t:
                    for c in G[x]:
                        C[c] -= 1
                        if C[c] == 0:
                           q.append((c,0))
                else:
                    if A[x] == 0: continue
                    A[x] = 0
                    for c in G[x]:
                        if B[c]: continue
                        B[c] = 1
                        q.append((c,1))

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve