We hope you enjoyed the contest as much as we enjoyed writing it! Thank you especially to PCTprobability for your very entertaining submissions to problem E.
2246A - farmpiggie and Subset Sum
Try to eliminate a large class of possible sums.
Think about parity. Is it possible to eliminate all odd numbers?
Try to construct the solution iteratively, by adding each new element.
2246C - 0mar and Alternating Sums
For a subsequence to have an alternating sum of zero, it must contain an even number of elements from every group of equal numbers.
The number of ways to pick an even size subsequence is equal to the number of ways to pick an odd size subsequence.
If the array is of size $$$n$$$, there are $$$2^{n-1}$$$ ways to pick an odd size subsequence.
Try to find a simple formula for the case where there are only positive elements.
The formula is $$$2^{n-d}$$$ where $$$d$$$ is the number of distinct elements. This is because you must pick an even size subset from every group of equal numbers, and multiplying all the choices together gives you $$$2^{n-d}$$$.
Do casework on whether or not you select an odd number of $$$-1$$$ elements.
2246C - 0mar and Alternating Sums
First, let's solve the problem for only positive integers (i.e. $$$1 \leq a_i \leq 10^9$$$). For a subsequence to have an alternating sum of zero, it must contain an even number of elements from every group of equal numbers.
The alternating sum of the subsequence $$$b_1, \ldots, b_m$$$ is the sum $$$b_1 - b_2 + b_3 + \ldots + (-1)^{m+1}b_m.$$$ If $$$m$$$ is even, we can pair the terms into the form
Since each of these terms is non-positive, the sum is zero if and only if all the terms are zero, which happens iff the subsequence contains an even number of elements from each group of equal numbers.
If $$$m$$$ is odd, we can group the terms as follows:
Since $$$b_1 \gt 0$$$ and all the other terms are non-negative the alternating sum cannot be zero.
Since the number of odd and even length subsequences of a group are equal, the number of subsequences of the array which contain an even number of elements from each group is the product of $$$2^{(\text{group size} -1)}$$$ over all numbers, which simplifies to $$$2^{(n - d)}$$$, where $$$d$$$ is the number of distinct elements in the array.
Let $$$S = {1,2,\ldots,n}.$$$ Our claim is equivalent to the statement that $$$S$$$ has $$$2^{n-1}$$$ subsets of even size. Let $$$T$$$ be a subset of $$$S$$$ which does not contain $$$1$$$. Then $$$|T \cup {1}| = |T| + 1,$$$ so its size has opposite parity. Furthermore this set is unique for $$$T$$$. Thus there are exactly $$$2^{n-1}$$$ pairs $$$(T, T \cup {1}),$$$ and each pair contains exactly one even size subset, so there are $$$2^{n-1}$$$ subsets of even size.
Now we consider the full problem, with $$$a_i$$$ possibly equal to $$$-1.$$$ In this case there exist subsequences with alternating sum zero which do not contain an even number of elements from each group.
Note that the number of subsequences containing an even number of $$$-1$$$ elements is $$$2^{(n - d)}$$$, since they will cancel each other, hence this reduces to the situation discussed above.
It remains to count the number of subsequences which contain an odd number of $$$-1$$$ elements. Let the total number of $$$-1$$$ elements in the array be $$$c$$$. There are $$$2^{c-1}$$$ ways to pick an odd number of them. Given that our subsequence contains an odd number of $$$-1$$$ elements, the positive elements of the subsequence must have an alternating sum of $$$-1.$$$ This occurs precisely when there exists a pair $$$(v,v+1)$$$ such that both $$$v$$$ and $$$v+1$$$ occur an odd number of times, and the remaining elements all occur an even number of times in the subsequence.
Using the same notation as in the previous proof, we see that $$$b_1, \ldots, b_m$$$ must again be even length since otherwise the alternating sum will be positive.
In the case where $$$b_1, \ldots, b_m$$$ has even length, we need exactly one of the terms $$$(b_i - b_{i+1})$$$ as grouped previously to be equal to $$$-1.$$$ This is precisely the characterization given.
For any value $$$v$$$ such that both $$$v$$$ and $$$v+1$$$ occur, we can choose the pair $$$(v,v+1)$$$ to be the pair with odd counts. This "flip" does not change the number of choices, since in each group the number of odd and even length subsequences are equal.
Therefore, the answer is $$$2^{(n - d)}$$$ if $$$-1$$$ isn't present; otherwise it is $$$2^{(n - d)} \cdot (\ell + 1)$$$, where $$$\ell$$$ is the number of values $$$v$$$ such that both $$$v$$$ and $$$v+1$$$ occur in the array.
2246D - diss_quack and Array Game
Try to solve the problem with no increments.
Do casework on whether or not there is an odd element in the array.
If there is an odd element, the answer is
Otherwise you must first remove the minimum LSB from all the elements and then this answer is forced.
This is true because if there is an odd element Bob can always put it in position 2, and force Alice to operate on each element individually.
Try fixing the minimum LSB over all $$$a_i$$$.
2246E - lce4113 and Security Game
You only need to determine one bit of $$$v$$$ in order to determine $$$b.$$$
The case $$$o = x$$$ needs to be handled carefully.
Try randomization.
2246F - Whoname and Unsorted Array
Consider the inversion count to check whether or not it is possible.
It is not possible if $$$n$$$ is even and the initial inversion count is odd.
Try sorting the elements in the suffix.
There is a clever $$$3$$$-move operation when you can't add the next element to the suffix.
There is a solution that works in $$$\frac{5n}{3}$$$ operations.
Brute force suggests that it is always possible in at most $$$n$$$ moves.
