I hope you all enjoyed the contest! Special thanks to:
- damamila, for creating problem G
- chromate00, AG-88301, simplelife, SpyrosAliv, reirugan and damamila for editorials for B-G respectively.
- cry, for helping answer clarifications.
A — The 67th Integer Problem
Many solutions exist here, and they are all trivial to find. Consider the value of $$$\min(x, y)$$$ when $$$x$$$ is constant, and you vary $$$y$$$. When $$$y \gt = x$$$, the value is $$$x$$$, and when $$$y \lt x$$$ the value is $$$y$$$. Therefore, the largest that $$$\min(x, y))$$$ can get for any value of $$$y$$$ is $$$x$$$. Therefore, outputting $$$y$$$ as any integer greater than or equal to $$$x$$$ works.
A common mistake was to output $$$y=x+1$$$, which fails because $$$68$$$ is greater than $$$67$$$, therefore not a valid output.
for _ in range(int(input())):
print(67)
B — The 67th 6-7 Integer Problem
Note how negating 6 out of 7 numbers is equivalent to negating all of them, and then negating one out of 7 numbers. Therefore, you can negate all 7 numbers, and then negate the least one afterwards.
for i in range(int(input())):
nums = list(map(int, input().split()))
print(2 * max(nums) - sum(nums))
C — The 67th Permutation Problem
Observe that the position of an element doesn't really matter: we are only interested in whether an element is a median, a large element or a small element (in its triple).
Since $$$3n$$$ has no elements larger than it, it must be a large element. Similarly, since $$$1$$$ has no elements smaller than it, it must be a small element.
To maximise the sum of medians, we should pick the largest possible median available, which is $$$3n-1$$$. Since $$$1 \lt 3n-1 \lt 3n$$$, this forms a valid triple.
Now we can repeat the process on the subset $$${2, 3, ... 3n-2}$$$, yielding the construction
Let the $$$i^{th}$$$ triple be $$${l_i, m_i, r_i}$$$, with $$$l_i \lt m_i \lt r_i$$$, and wlog let $$$m_1 \lt m_2 \lt \cdots \lt m_n$$$ be the $$$n$$$ medians.
Each median needs an element strictly larger than it not used in any other triple. So there should be at least $$$1$$$ element larger than $$$m_n$$$, at least $$$3$$$ elements larger than $$$m_{n-1}$$$ (namely $$$m_n$$$, $$$r_n$$$, $$$r_{n-1}$$$), and more generally, at least $$$2k - 1$$$ elements larger than $$$m_{n-k+1}$$$.
In the set $$$1 \ldots 3n$$$, there are $$$3n - m_{n-k+1}$$$ elements larger than m_{n-k+1} (namely $$$m_{n-k+1}+1 \ldots 3n$$$), and so we need
Rearranging, we get $$$m_{n-k+1} \leq 3n - 2k + 1$$$, as in the optimal construction.
for _ in range(int(input())):
n = int(input())
k = 3 * n
for i in range(1,n+1):
print(i, k-1, k, end=" ")
k -= 2
print()
D — The 67th OEIS Problem
Think something related to coprime numbers.
There are many ways to construct the array — we will provide two ways to do it.
Let's take $$$n+1$$$ distinct numbers $$$b_1,b_2,\ldots,b_{n+1}$$$.
Now let $$$a_i=b_i\cdot b_{i+1}$$$ for all $$$i$$$.
Now $$$\operatorname{gcd}(a_i,a_{i+1})=b_{i+1}\cdot \operatorname{gcd}(b_i,b_{i+2})$$$.
Now if $$$\operatorname{gcd}(b_i,b_{i+2})=1$$$ for all $$$i$$$, then we can obtain a distinct gcd for each adjacent pair and the construction is valid.
One way to obtain this is to let all $$$b_i$$$ be all primes starting from $$$2,3,5,\ldots$$$. Since all numbers are coprime to each other, their pairwise $$$gcd$$$ is $$$1$$$ and we get a valid construction.
Another way to obtain this to let all $$$b_i$$$ be odd numbers starting from $$$1,3,5,\ldots$$$. Since $$$\operatorname{gcd}(x,x+4)=1$$$ , where $$$x$$$ is odd, this construction is also valid.
for _ in range(int(input())):
n = int(input())
k = 1
for i in range(1,n+1):
print(k * (k+2), end=" ")
k += 2
print()
E — The 67th XOR Problem
What happens after two operations? Does the first operation matter?
Remember the propery that $$$x \oplus x = 0$$$.
We have an array $$$a = [a_1, a_2, a_3, \ldots, a_n]$$$. Suppose we performed the operations from left to right, to see how operations affect the array.
After the first operation, the array becomes: $$$a = [a_2 \oplus a_1, a_3 \oplus a_1, \ldots, a_n \oplus a_1]$$$. Note that the first element was removed.
After the second operation, the array becomes $$$a = [(a_3 \oplus a_1) \oplus (a_2 \oplus a_1), \ldots, (a_n \oplus a_1) \oplus (a_2 \oplus a_1)]$$$. Due to Hint $$$2$$$, this is the same as $$$a = [a_3 \oplus a_2, \ldots, a_n \oplus a_2]$$$.
Note that this new array is independent of $$$a_1$$$. In fact, after any two operations, the value of the element chosen in the first operation does not matter. Taking this a step further: when doing three operations, the elements chosen for the first two operations do not matter. Inductively, the only thing that matters is the element we choose last for an operation (let it be $$$x$$$) and which element we never choose for an operation (let it be $$$y$$$). The final value of the array is going to be $$$x \oplus y$$$.
Since $$$n$$$ is small, it is enough to brute force all possible pairs $$$(x, y)$$$. The answer is the maximum value of $$$a_x \oplus a_y$$$ among all pairs.
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
m = 0
for i in range(n):
for j in range(i+1, n):
m = max(m, a[i] ^ a[j])
print(m)
The problem of finding the integers $$$a$$$ and $$$b$$$ from an array such that $$$a \oplus b$$$ is maximized can be done in $$$O(n \log n)$$$ using a trie.
You can see in detail how this would work on this post. Roughly speaking, we insert the binary representation of each number in the trie. After that, for each number we try to find which other number gives maximum xor, which can be done with a greedy walk on the trie.
F — The 67th Tree Problem
We know that the number of vertices in the entire tree is $$$x+y$$$. Therefore, the subtree of the root has size $$$x+y$$$. So if $$$x+y$$$ is even and $$$x$$$ is zero, there is no valid tree. Similarly, if $$$x+y$$$ is odd and $$$y$$$ is zero, there is no valid tree. From this point onwards, we can now exclude the root by decrementing either $$$x$$$ or $$$y$$$, and only considering the other vertices. The root will be trivially satisfied.
We claim that for any vertex whose subtree has an even size, it must have at least one child with an odd size. Indeed, suppose all of its children have even size. Then the total number of vertices in the subtree will be the sum of some even numbers, plus one, the node itself. By contrapositive, this implies the desired claim.
Therefore, if the number of vertices with an even subtree size is larger than the number of vertices with an odd subtree size (excluding the root), there is no valid tree.
All other cases are possible.
Read the hints.
Now, we will try to make every vertex (excluding the root) have subtree size either $$$1$$$ or $$$2$$$. To do this, we will attach $$$x$$$ disjoint pairs of vertices. Then we will attach each pair, and all of the remaining vertices, to the root. Now, the number of vertices with an even subtree size is exactly $$$x$$$, the parent from each of the pairs, as desired.
for _ in range(int(input())):
x, y = map(int, input().split())
n = x + y
d = y - x
if (x == 0 and n % 2 == 0) or n//2<x:
print("NO")
continue
print("YES")
mm = 2 * x + (d % 2)
for i in range(2, mm + 1):
print(i - 1, i)
for i in range(mm + 1, n + 1):
print(mm, i)
G — The 67th Iteration of "Counting is Fun"
When is there no valid $$$a$$$?
Remember for a person $$$i$$$ with $$$b_i \gt 0$$$ to be able to sit down, one of their neighbours already needs to be sat down.
What do you notice about people where $$$b_i = 0$$$?
If $$$b_i = 0$$$, then $$$a_i$$$ must also equal $$$0$$$.
If a person $$$i$$$ with $$$b_i \gt 0$$$ has no neighbour with a smaller $$$b_i$$$, they would never sit down so there is no valid $$$a$$$ so we output $$$0$$$.
We can observe that all $$$a_i$$$ are independent of each other so long as they are consistent with the array $$$b$$$. This means we can compute the number of possible $$$a_i$$$ for every $$$i$$$ separately.
Let $$$c_t$$$ be the number of people sat down at time $$$t$$$ or earlier. This is all people where $$$b_i \leq t$$$. For a time $$$t$$$, we can calculate $$$c_t$$$ using prefix sums as it is the sum of $$$c_{t-1}$$$ and the number of people that sit down at time $$$t$$$.
For a person to sit down at time $$$t$$$, two conditions had to be met:
At least $$$a_i$$$ people have already sat down strictly before time $$$t$$$.
At least one of their neighbors (person $$$i−1$$$ or $$$i+1$$$, if they exist) has already sat down strictly before time $$$t$$$.
We can now split people into $$$2$$$ types depending on which condition occurs first for them.
Type A: Condition $$$1$$$ is satisfied first. This means they are waiting for one of their neighbours to sit down so they can sit down. A person is of this type if the earliest time one of their neighbours sat down is exactly $$$1$$$ less than the time they sat down. This means their $$$a_i$$$ can be any value between $$$1$$$ and $$$c_{t-1}$$$ inclusive so there are $$$c_{t-1}$$$ possible values.
Type B: Condition $$$2$$$ is satisfied first. This means they are waiting for enough people to have sat down. A person is of this type if the time they sit down is at least $$$2$$$ greater than the earliest time one of their neighbours sat down. Since they did not sit down at time $$$t-1$$$, their $$$a_i$$$ must be greater than $$$c_{t-2}$$$. This means it must be between $$$c_{t-2}+1$$$ and $$$c_{t-1}$$$ inclusive, giving $$$c_{t-1}-c_{t-2}$$$ possibilities.
We can iterate over all people $$$i$$$ and look at the earliest time one of their neighbours sat down to find out which type of person they are, and then compute how many valid $$$a_i$$$ there are for them.
Finally, we can multiply the number of valid $$$a_i$$$ for every person, and output this modulo $$$676767677$$$.
from itertools import accumulate
MOD = 676767677
for _ in range(int(input())):
n, m = map(int, input().split())
b = [*map(int, input().split())]
cnt = [0] * m
for i in range(n):
cnt[b[i]] += 1
p = [0, *accumulate(cnt)]
ans = 1
for i in range(n):
if b[i] > 0:
t = float("inf")
for v in (i-1, i+1):
if v not in range(n): continue
t = min(t, b[v])
t += 1
if b[i] > t:
ans = ans * cnt[b[i] - 1] % MOD
elif b[i] == t:
ans = ans * p[b[i]] % MOD
else:
ans = 0
print(ans % MOD)
