# PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

# DIFFICULTY:

SIMPLE

# PROBLEM:

Arrays A and B form an **interesting** pair if

- sizes of both arrays are equal,
- each number 1,2,\dots,N occurs in exactly one of the arrays,
- sum of elements in A is equal to the sum of elements in B, and
- sum of first i elements of A is unequal to the sum of first i elements of B, for all 1\le i< \frac N 2.

Determine if any **interesting** pair exists.

# EXPLANATION:

**Claim:** No **interesting** pair exists when N is not divisible by 4.

## Proof

We prove by contradiction.

Let A and B form an **interesting** pair for some N not divisible by 4. The combined sum of their elements is

Now, since the sum of elements of A is equal to the sum of elements of B, the sum of elements of each array is equal to

It is easy to deduce that the above equation is non-integral when N\equiv 0 \pmod 2 and N\not\equiv 0 \pmod 4. But since the elements of the arrays are integral, their sum is also supposed to be integral.

A contradiction and we are done.

Let’s only consider the case where N is divisible by 4. I claim that an **interesting** pair always exists.

## Hint 1

Experimenting helps a lot. Try formulating a solution for N=8. Do you observe any pattern?

## Hint 2

A solution has been given below, for N=8.

Can you generalise the above solution for all valid N?

## Generalised solution

Consider the following sequences for A and B (each array has been divided into two equal length parts for clarity):

I claim they form an **independent** pair, so they should satisfy the 3 constraints given in the problem (or shall I call it question? )

Proving |A|=|B| and \sum A = \sum B in the above sequences is trivial (and left to the reader as an exercise). All we are left to show is that the sum of first i elements of A is unequal to the sum of first i elements of B, for all 1\le i< \frac N 2.

## Proof of criteria 3

From the alternating pattern of elements in A and B, it is easy to see that, for all 1\le i \le \frac N 4

and that for all \frac N 4 < i \le \frac N 2

Now, for all 1\le i < \frac N 2, the extra term on the LHS is non-zero, which implies that the sum of first i elements of A is unequal to the sum of first i elements of B.

Thus proved.

# TIME COMPLEXITY:

Since we iterate from 1 to N once to create the output, the total time complexity is

per test case.

# SOLUTIONS:

Editorialist’s solution can be found here.

**Experimental:** For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

- 1
- 2
- 3
- 4
- 5

0 voters