UNQEQ - Editorial

editorial
, , ,
1

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

1+2+\dots+N = \frac{N*(N+1)}{2}

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

\frac{N*(N+1)}{2}\div2=\frac{N*(N+1)}{4}

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.

A = [1,3,6,8] \\ B = [2,4,5,7]

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):

A = [1,3,\dots,N/2-1]+[N/2+2,\dots,N-2,N]\\ B = [2,4,\dots,N/2]+[N/2+1,\dots,N-3,N-1]

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

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

\sum_x^iA_x+i=\sum_x^i B_x

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

\sum_x^i A_x + (\frac N 2-i) = \sum_x^iB_x

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

O(N)

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

3

i did not find wrong test case for my solution :expressionless:
solution : link CodeChef: Practical coding for everyone

4 
1                   
100000

Edit:

Much the same issue as this: RUMBLING - Editorial - #7 by ssjgz

5

#include<bits/stdc++.h>
using namespace std;
main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
if(n%2==0)
{
if((n*(n+1)/2)%2==0)
{
int a_len=n/2;
int b_len=n/2;
int a[a_len];
int b[b_len];
int first=1,last=n;
for(int i=0;i<n/2;i=i+2)
{
a[i]=first;
a[i+1]=last;
first++;
last–;
}
for(int i=0;i<n/2;i=i+2)
{
b[i]=first;
b[i+1]=last;
first++;
last–;
}

			cout<<"YES"<<endl;
			
			for(int i=0;i<a_len;i++)
			{
				cout<<a[i]<<" ";
			}
			cout<<endl;
			for(int i=0;i<b_len;i++)
			
			{
				cout<<b[i]<<" ";
			}
		}
	
        else
        cout<<"NO"<<endl;
    }
    else
    cout<<"NO"<<endl;
}

}

6 
#include<bits/stdc++.h>
using namespace std;
void half_even(int a[],int low,int high){
    int count = 2*(low+1);
    for(int i = low;i<=high;i++){
        a[i] = count;
        count += 2;
    }
}
void half_odd(int a[],int low,int high){
    int count = 2*(low+1)-1;
    for(int i = low;i<=high;i++){
        a[i] = count;
        count += 2;
    }
}
void print(int a[],int n){
    for(int i = 0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[n/2];
        int b[n/2];
        int total_sum = n*(n+1)/2;
        if(total_sum%2 == 0){
            cout<<"YES\n";
            half_even(a,0,(n/4)-1);
            half_odd(a,(n/4),(n/2)-1);
            half_odd(b,0,(n/4)-1);
            half_even(b,n/4,(n/2)-1);
            print(a,n/2);
            print(b,n/2);
        }
        else {
            cout<<"NO\n";
        }
    }
    return 0;
}