farmpiggie and Subset Sum

The process looks like a signed subset-sum problem: for every position, we independently choose to add, subtract, or ignore its weight. Trying to analyze all those possibilities would be spectacular overkill. We can make every possible result have the wrong parity instead.

Turning the operations into weights

Define

$a_i=i\cdot p_i.$

At position $i$, the contribution is one of

$-a_i,\quad 0,\quad a_i.$

If every $a_i$ is even, then every possible contribution is even. Therefore their sum is also even, regardless of which operations are chosen. Since $1$ is odd, it can never be the final counter value.

So all we need is a permutation satisfying

$i\cdot p_i\equiv 0\pmod 2$

for every position $i$.

Constructing the permutation

A product is odd only when both factors are odd. Thus:

• At an even position, the product is automatically even.
• At an odd position, we must place an even value.

Because $n$ is even, the permutation contains exactly $n/2$ even values and there are exactly $n/2$ odd positions. They fit perfectly.

The simplest implementation is to reverse every adjacent pair:

$[1,2,3,4,\ldots,n-1,n]\longrightarrow[2,1,4,3,\ldots,n,n-1].$

Equivalently, for every $k$ from $1$ to $n/2$,

$p_{2k-1}=2k,\qquad p_{2k}=2k-1.$

For example, when $n=6$, we print

$[2,1,4,3,6,5].$

Its weights are

=[2,2,12,12,30,30],$$ all of which are even. ### Proof of correctness First, the construction is a permutation: each adjacent pair $(2k-1,2k)$ is merely printed in reverse order, so every number from $1$ through $n$ appears exactly once. Now consider any position: - If $i=2k-1$ is odd, then $p_i=2k$ is even, so $i\cdot p_i$ is even. - If $i=2k$ is even, then $p_i=2k-1$, and the even factor $i$ again makes $i\cdot p_i$ even. Therefore every allowed contribution $x_i\in\{-i\cdot p_i,0,i\cdot p_i\}$ is even. A sum of even integers is even, so every possible $c_{\mathrm{final}}$ is even. Consequently, $c_{\mathrm{final}}$ cannot equal $1$. ### Complexity Printing the permutation takes $O(n)$ time per test case and $O(1)$ auxiliary space.