Slicing (Editorial)

The problem can be shortened to : Given an array $a$ of a_1,a_2,\ldots,a_n , Partition the array into three non-empty contiguous segments such that their sums have different remainders when divided by $3$ , Therefore if we wanted to denote the remainders of the partitions as [S_1,S_2,S_3] The final partition $S$ must be a permutation of \{0,1,2\} , This forces a condition (0+1+2) \bmod 3=0 which implies that a valid partition can exist only when \left ( \sum\limits_{i=1}^n a_i \right ) \bmod 3=0 , So once \left ( \sum\limits_{i=1}^n a_i \right ) \bmod 3 \neq 0 the answer is immediately $00$ , Let's denote the prefix remainders as P_i=\left ( \sum\limits_{j=1}^i a_j \right ) \bmod 3 , then S_1=P_x , S_2=(P_y-P_x) \bmod 3 and S_3=(-P_y) \bmod 3 , These three always sum to $0$ modulo $3$ , so they are either all equal or pairwise distinct , Therefore it's enough to ensure S_1 \neq S_2 which is equivalent to (P_x+P_y) \bmod 3 \neq 0 , So for each $y$ from $2$ to n-1 we keep the first index x<y at which each remainder r \in \{0,1,2\} appeared among P_1,\ldots,P_{y-1} , and check if any of them satisfies (r+P_y) \bmod 3 \neq 0 , if we reached the end of the search with no solutions exist , then there is no valid partition for the problem.

Complexity $O(n)$.

def solve():
    n=int(input())
    a=list(map(int,input().split()))
    if(sum(a)%3!=0):
        print(0,0)
        return
    first=[0,0,0]
    p=a[0]%3
    first[p]=1
    for y in range(2,n):
        p=(p+a[y-1])%3
        for r in range(3):
            if(first[r] and (r+p)%3!=0):
                print(first[r],y)
                return
        if(not first[p]):
            first[p]=y
    print(0,0)


for _ in range(int(input())):
    solve()