A - Communicate Topological Order

Hint 1

When the graph has no edges, Aoki cannot determine $P$ unless Takahashi tells him $N-1$ terms.

Hint 2

When there is no edge between any two vertices in vertex set $S$, Takahashi needs to tell Aoki $|S|-1$ terms among the vertices in $S$.

Hint 3

Conversely, when the $N$ vertices are partitioned into such vertex sets, Takahashi does not need to tell Aoki one term from each set. However, there are constraints on such partitioning methods. What are they?

Hint 4

The answer to Hint 3 is that the order of the vertex sets must be determined. For example, even if the order of vertices within each vertex set is determined, if the vertex sets are independent in $G$, Aoki cannot determine $P$.

Hint 5

The optimally partitioned vertex sets have a certain property. Let's think about it. Even if you can't come up with it, experimenting with specific cases might make it clear.

Hint 6

Actually, in an optimally partitioned vertex set, the values of $P_i$ for vertex $i$ may form a contiguous interval.

Hint 7

We want to partition the $N$ vertices into as many vertex sets as possible while satisfying the conditions so far. What should we calculate and how?

B - Swap if Equal Length and Sum

Hint 1

The sum of $A$ is invariant under the operations, but there are other invariants as well.

Hint 2

The number of inversions is also an invariant under the operations. In fact, if $A$ and $B$ have the same sum and number of inversions, it is always possible. Let's think about a specific sequence of operations.

Hint 3

By performing operations that swap intervals containing exactly one $1$ $N$ times, we can make $A$ match $B$.

Hint 4

By slightly modifying the operation sequence from Hint 3, we can keep the number of operations to at most $\lfloor\frac{N}{2}\rfloor$.

C - PORALIS

Hints for writer’s solution

Hint 1

Consider the case when $N$ is a power of $2$.

Hint 2

If we set the lower 10 bits of $P_i$ (in binary) to $i-1$, we only need to consider the longest weakly increasing subsequence of the upper 20 bits.

Hint 3

Among the upper 20 bits of $P_i$, let's make at most one bit equal to $1$.

Hint 4

Using Hints 2 and 3, try to achieve as many LIS lengths as possible.

Hint 5

Consider whether you can use the solution for $\displaystyle \frac{N}{2}$.

Hints for tester’s solution

Hint 1

Since $N^3 = \max(P, A)$, we are done if we can more than double $N$ by adding $2$ or $3$ bits.

Hint 2

When $(P, A)$ that achieves the condition for some $N$ can be constructed, try to achieve the condition for $N+1$ by adding one bit.

Hint 3

When $(P, A)$ that achieves the condition for some $N$ can be constructed, what is the LIS length when we $\mathrm{OR}$ each of $A_1, A_2, \dots, A_N$ with $(P_1, P_2, \dots, P_N, P_1 + 2^X, P_2 + 2^X, \dots, P_N + 2^X)$?

Hint 4

In Hint $3$, even LIS lengths can be easily achieved. Add one more bit to achieve all LIS lengths as well.

D - Valid Output for DSU Problems

Hint 1

Consider the conditions on the sequence $A$ obtained when the order of adding edges is fixed.

Hint 2

Consider the timing when the number of pairs of connected vertices first becomes at least the number of $1$s in $A$.

Hint 3

When the order of adding edges is determined, how can we find the number of operations needed to satisfy the condition?

Hint 4

We remove the constraint that the order of adding edges is fixed. What do we need to know to find the number of operations?

Hint 5

We use dynamic programming to check whether such an arrangement is possible. What should we compute to meet the time limit?

E - Delete AB

Hint 1

Replace `A` with $+1$ and `B` with $-1$, and take the cumulative sum.

Hint 2-1

For the cumulative sum considered in Hint $1$, think about the following three things:

• How does it change under the operations?
• Is there anything that doesn't change under the operations?
• What state of the cumulative sum corresponds to being a palindrome?

Hint 2-2

• Under the operation, two elements satisfying a certain condition are deleted.
• The first value, the last value, and the minimum value do not change.
• A necessary and sufficient condition is that the sum of the $i$-th term from the front and the $i$-th term from the back of the cumulative sum is always the same regardless of $i$.

Hint 3

Since the minimum value of the cumulative sum does not change, we need an element corresponding to it.

Hint 4

Fix one pair of the min of the cumulative sum and the element to keep corresponding to it. What is the optimal approach for the inside and outside of this pair?

Hint 5

For the outside of Hint 4, the prefix min (or suffix min) does not change.

Hint 6

When there are multiple candidates for the min of the cumulative sum or the element corresponding to it, which one is optimal to keep?