Cut the Array

The problem looks like it wants you to search for the right two cut points. It really does not.

Let the three part sums modulo $3$ be $s_1,s_2,s_3$. Since the three parts cover the whole array exactly once,

$$s_1+s_2+s_3 \equiv \sum_{i=1}^{n} a_i \pmod 3.$$

Now look at what the condition actually says.

If $s_1,s_2,s_3$ are all the same, then the triple is one of:

$$(0,0,0),\ (1,1,1),\ (2,2,2).$$

Each has sum $0$ modulo $3$.

If $s_1,s_2,s_3$ are all different, then because the only residues modulo $3$ are $0,1,2$, the triple must be some permutation of:

$$(0,1,2).$$

That also has sum $0$ modulo $3$.

So a valid cut can exist only if the total sum of the array is divisible by $3$.

The sneaky part: this condition is also sufficient.

For any three residues modulo $3$, if their sum is $0$ modulo $3$, then they must be either:

• all equal, or
• all different.

There is no third option. If exactly two were equal, say $(x,x,y)$ with $y\ne x$, then the sum would not be $0$ modulo $3$.

So if the total sum is divisible by $3$, literally any valid cut works. Since $n\ge 3$, the cut $l=1$, $r=2$ always makes three non-empty parts:

• $[a_1]$,
• $[a_2]$,
• $[a_3,\dots,a_n]$.

Therefore:

• if $\sum a_i \equiv 0 \pmod 3$, output 1 2;
• otherwise, output 0 0.

Complexity: $O(n)$ per test case, just to compute the sum. Memory: $O(1)$.