A - Unusual-Constraint Knapsack

Hint 1

This is an ordinary knapsack problem with the special constraint $\sum_{j=1}^{i-1}{w_j}\lt w_i$. Think about how to make use of this.

Hint 2

Try deciding whether to choose item $i$ in the order $i = N, N-1, \dots, 1$.

Hint 3

(Although impossible under the constraints,) if $W \lt w_N$, item $N$ cannot be chosen. When $w_N \leq W$, think about what happens in each of the two cases: choosing item $N$ and not choosing it.

Hint 4

If we choose it, the remaining weight becomes $W - w_N$, and we proceed to decide whether to choose item $N-1$. What happens if we do not choose it?

Hint 5

If we do not choose item $N$, then by the constraint we can choose all other items, and the search can be terminated here. Use this property to think about the time complexity.

B - Valid Arrays by K-Divisible Swaps

Hint 1

For various values of $K$, write out the pairs of values $\pmod K$ that can be swapped.

Hint 2

It can be seen that before and after an operation, each element is multiplied by $1$ or $-1$ modulo $K$.

Hint 3

If $A_i \not\equiv \pm A_{i+1} \pmod K$ initially, then no operation swapping $A_i$ and $A_{i+1}$ will ever be performed. Thus, we can split the sequence at such positions and multiply the counts for the subsequences.

Hint 4

Consider cases based on whether $A_i \equiv -A_i \pmod K$. For each case, think about what conditions must be satisfied for a rearrangement to be possible.

Hint 5

If $A_i \equiv -A_i \pmod K$, then the elements within the split subsequence can be freely rearranged.
If $A_i \not\equiv -A_i \pmod K$, then elements with the same value modulo $K$ cannot be swapped with each other, so their relative order is preserved.

C - Whole Product of Pairwise Distances

Hint 1

In problems asking for a remainder after division, the modulus is often a prime such as $998244353$ or $10^9+7$, but here it is $N$. Think about what difference this makes.

Hint 2

What happens if there exist two values among $A_1, A_2, \dots, A_N$ that have the same remainder when divided by $N$?

Hint 3

It suffices to handle the case where each of $0, 1, 2, \dots, N-1$ appears exactly once modulo $N$ (otherwise the answer is $0$). Since the original expression contains absolute values, naively reducing each $A_i$ modulo $N$ changes the answer. How should we handle this?

Hint 4

If we sort $A$ and think of computing $\prod_{1 \leq i \lt j \leq N}{(A_j - A_i)}$, then replacing each element of $A$ by its value modulo $N$ does not change the answer. As the simplest case, consider $A_i = i - 1\;(i = 1, 2, \dots, N)$. How can the answer be computed in this case?

Hint 5

When $A$ is a permutation of $(0, 1, 2, \dots, N-1)$, what does $\prod_{1 \leq i \lt j \leq N}{(A_j - A_i)}$ equal? Think about how this differs from the simple case in Hint 4.

D - Xpectation of Cards in Hand with Laboratory

Hint 1

Let $a$ and $b$ be the number of draw cards and normal cards drawn so far. Express the condition for the operations to terminate as a formula.

Hint 2

Think of paths on a grid where draw cards are replaced by rightward steps and normal cards by upward steps.

Hint 3

Reformulating in terms of paths, the number of vertices where the operations can possibly terminate is $O(A + B)$.

Hint 4

For each vertex, think about the condition under which the operations terminate there.

Hint 5

The condition differs slightly depending on whether the deck is empty or not when the operations terminate.

E - Yin-Yang Two Bits Insertion

Hint 1

If we represent the sequence by the XOR of adjacent elements, what transformation does the operation correspond to?

Hint 2

$0$ is transformed to $101$, and $1$ is transformed to $111$. The original sequence and the transformed sequence have unchanged first and last elements; think about what other invariants exist.

Hint 3

The number of $0$s in the adjacent-XOR sequence is invariant. So, reformulate by splitting at $0$s and listing the number of $1$s in each segment. What transformation does the operation correspond to in this reformulation?

Hint 4

The operation corresponds to:

• Add $1$ to two adjacent terms.
• Add $2$ to a term that is at least $1$.

In most cases, applying the first operation twice can be replaced by the second operation.

Hint 5

When the first operation is applied to the same pair of adjacent terms three or more times, two of those can be replaced by the second operation. What does this imply? Also, using that property, what kind of dynamic programming can be used to determine the answer?

F - Zonal Score Maximization

Hint 1

$f(P)$ is at most the whole sum $\frac{N(N+1)}{2}$, and this can be achieved if $N$ is even. What if $N$ is odd?

Hint 2

If $N$ is odd, it turns out that the optimal division is into one subsequence of length $3$ and $\frac{N-3}{2}$ subsequences of length $2$.

Hint 3

If $N$ is odd, $N - 1$ values can be included in $f(P)$. From $f(P) = X$, we can identify the value that is not included.

Hint 4

The problem reduces to counting permutations $P$ for which $\min(\text{median of } (P_i, P_{i+1}, P_{i+2}) \mid i = 1, 3, \dots, N-2)$ equals some value (call it $p$). The answer can be obtained by subtracting the number of permutations $P$ for which this value is at least $p+1$ from the number for which it is at least $p$.

Hint 5

When counting permutations $P$ for which $\min(\text{median of } (P_i, P_{i+1}, P_{i+2}) \mid i = 1, 3, \dots, N-2)$ is at least $p$, there is no need to distinguish between values less than $p$ and between values at least $p$, so each can be replaced by $0$ or $1$ respectively.

Hint 6

The number of $0$s in the sequence replaced by $0$s and $1$s must be exactly $p - 1$. We want to decide, going from left to right, whether to assign $0$ or $1$ to each position, and run a DP keyed on the number of $0$s assigned so far, but doing this naively takes $O(N^2)$. How can this be sped up?