Some codeforces problem + a little puzzle

We are given some array $a$ of length $n$ which is initially populated with only $0$'s. We also have a pointer which starts pointed at the first element of $a$. Given the pointer is at position $i$, we can make the following moves:

• add $1$ to $a[i]$ and move the pointer one to the right, or
• subtract $1$ to $a[i]$ and move the pointer one to the left.

We are given some target array of length $n$. Can we transform $a$ into the target array such that the pointer also ends at the first element in $a$?

We first note that because the pointer must start and end in the first position of $a$, the target array sum must be $0$. Additionally, if we look at what a move is actually doing on the following example:

$a_1, a_2, a_3, a_4, a_5$

+     +     +     + 

       -     -     -     -

The overlapping + and - just cancel out and so the operation actually has the form +...+_____-

We observe that whenever we have a - we must also have at least one + preceding it by the move's anatomy. Thus the prefix sums must be non-negative. It turns out this condition is also sufficient.

Extra puzzle:

Imagine $n$ glasses upside-down on a table. In one move, we can flip any group of $n-1$ glasses. For which values of $n$ can we turn the glasses up? For these values of $n$ devise an algorithm for doing so in the minimum number of moves.

So first we note that when $n=1$ it is clear that it is impossible. For $n=2$ it is trivially possible. For $n\geq 3$, we need to think a little bit.

In order to flip every glass over, we need to flip each glass an odd number of times. Consider the following procedure.

• number the glasses from $1$ to $n$.
• for every $g=1$ to $n$, flip all glasses except for glass $g$.

Fix any glass $g$, it is flipped $n-1$ times by this procedure. Thus if $n$ is even, all glasses will be turned over. The remaining questions are:

1. What about $n>1$ odd? (Conjecture, it is not possible)
2. Is our algorithm for even $n$ optimal. (Conjecture, yes)

Note that we will never flip the same set of $n-1$ glasses twice. Since the second will undo the effects of the first. Thus if it is possible it is always possible in $\leq n$ moves.

Consider odd $n$. At any given moment there must exist at least one upside-down glass. After $1\leq i<n$ moves suppose WLOG we have excluded $1, 2, ..., i$. Each of these glasses will have been flipped $i-1$ times and all others will have been flipped $i$ times. Thus for all $i<n$ we have glasses which are flipped and unflipped. Thus we need at least $n$ moves and it is impossible for odd $n$.