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