A - Strange Subset Sum

Hint 1

From the constraint $|A|=\left\lfloor\frac{N}{2}\right\rfloor$, we see that about half of the integers between $1$ and $N-1$ are contained in $A$. Think about what this implies.

Hint 2

For example, if test cases are generated randomly, the answer is $2$ in almost all cases. Why is that?

Hint 3

For $i=1,2,\dots,\left\lfloor\frac{N-1}{2}\right\rfloor$, ask whether $i$ is contained in $A$. Think about how to use the results to determine whether the answer is $2$ with roughly $\frac{N}{4}$ remaining questions.

Hint 4

If it was determined in Hint 3 that the answer is not $2$, all elements of $A$ should have been identified.

Hint 5

In fact, there are not many possible values for the answer.

B - Count of Euclid Function Call

Hint 1

Consider the steps of the Euclidean algorithm in reverse.

Hint 2

The arguments of each call to $f$ can be expressed as $an+bm,cn+dm$. What operation on $(a,b,c,d)$ does tracing the Euclidean algorithm backward correspond to?

Hint 3

Viewing it as an operation on $\begin{pmatrix} a & b\\ c & d \end{pmatrix}$, what quantity is invariant under the operation? Based on that, consider the conditions on $a,b,c,d$.

Hint 4

Fix $c,d$ and consider the $a,b$ that satisfy the conditions found in Hint 3.

Hint 5

Be careful about corner cases in the conditions on $a,b,c,d$ and in the $a,b$ satisfying them.

C - Equal Degree Deletion

Hint 1

Think about the conditions for a tree to be special.

Hint 2

Write on each edge the degree of its endpoints at the moment it is deleted.

Hint 3

Looking at the edges incident to each vertex together, what condition do the written degrees satisfy?

Hint 4

To make a tree in which $d$ is written, at least $2^d$ vertices are needed.

Hint 5

The maximum degree written on an edge is $O(\log N)$.

Hint 6

Root the tree at an arbitrary vertex and do a bottom-up DP keyed by the degree written on the edge going up. How can we make it fast enough?

Hint 7

Making the written degree a certain value requires a corresponding number of vertices, so these can be bounded from above all together. Exploiting this allows us to speed up the DP.

D - Zigzag Code for Cubic Functions

Hint 1

First, ignore the constraint on $|S|$. Also, consider the cases where $f$ is a linear or quadratic function.

Hint 2

When $f$ is linear, $g(S+\mathtt{-+})=g(S)+1$ holds. When $f$ is quadratic, $g(S+\mathtt{+--+})=g(S)+4$ holds. What happens if we extend these to cubic functions?

Hint 3

Think about how to determine, for $i=0,1,\dots,47$, whether $i$ is generable.

Hint 4

Because of the constraint on $|S|$, we need to construct a short $T$ with $g(S+T)=g(S)+48n$ for a reasonably large $n$. Try modifying the strings considered in Hint 2.

Hint 5

What happens if we append the string obtained by repeating each character of $\mathtt{+--+-++-}$ $k$ times and concatenating them?