# LOSTSEQ - Editorial

Setter: Akshit Monga
Tester: Abhinav Sharma
Editorialist: Kanhaiya Mohan

Simple

None

# PROBLEM:

Chef has a sequence of integers A of length N. He creates another sequence B of length 2 \cdot N using sequence A. Initially, B is empty. Chef performs the following process.

For each element A_i (1 \le i \le N) of A:

• Choose any arbitrary integer k (Note that the value of k can be different for different elements).

• Add A_i-k and A_i+k to B.

Chef then shuffles the sequence B randomly after this process.

You’re provided with a sequence B of size 2 \cdot N. You are required to tell if the provided sequence can be achieved from any sequence A of size N using the given process or not.

# QUICK EXPLANATION:

• The answer is YES only if the sum of elements of B is even.

# EXPLANATION:

Observation

Let us suppose we have two integers X and Y. We need to check if there exists an integer Z such that X = Z - k and Y = Z + k.

Assuming X = Z - k and Y = Z + k, the value of X+Y would be 2 \cdot Z. Thus, Z = \frac{X+Y}{2}.
In conclusion, if the value X+Y is even, there exists an integer Z such that X = Z - k and Y = Z + k.

Based on above observation, for an array A (of size N) to exist, we need to divide array B (of size 2 \cdot N) into N pairs such that:

• Each element of B is present in exactly one pair.
• The sum of each pair is even.

If we are able to achieve this, then, we have a possible array A. The elements of array A would be equal to the mean of the pairs formed by elements of array B.

Claim: There exists a possible array A if the sum of the elements of B is even.
Proof: Let X denote the count of odd elements in B and Y denote the count of even elements in B.

• Since the sum of all elements of B is even, X (count of odd elements) must be even.
• Total count of elements in B is 2 \cdot N (which is even) and the count of odd elements is also even. Thus, the count of even elements, Y = (2\cdot N-X) is even.

For the Y even elements, we can divide them into \frac{Y}{2} pairs. Each pair contains 2 even elements. Thus, each of these pairs has an even sum and is a valid pair.
For the X odd elements, we can divide them into \frac{X}{2} pairs. Each pair contains 2 odd elements. Thus, each of these pairs has an even sum and is a valid pair.

Hence proved that we can construct an array A from B if the sum of the elements of B is even.

In conclusion, we only need to check the sum of the elements of B. If the sum of elements is even, the answer is YES, else it is NO.

# TIME COMPLEXITY:

The time complexity is O(N) per test case.

# SOLUTION:

Setter's Solution
for _ in range(int(input())):
n=int(input())
print("NO" if sum(map(int,input().split()))%2 else "YES")

Tester's Solution
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int T=1;
cin >> T;
while(T--){

int n;
cin>>n;
n*=2;
ll sum = 0;
rep(i,n){
int x;
cin>>x;
sum+=x;
}

cout<<((sum%2==0)?"Yes":"No")<<el;
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}

Editorialist's Solution
#include <iostream>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int sum = 0;
for(int i = 0; i<2*n; i++){
int x;
cin>>x;
sum += x;
}
if(sum % 2){
cout<<"No";
}
else{
cout<<"Yes";
}
cout<<endl;
}
return 0;
}

4 Likes
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- != 0){
int n = sc.nextInt();
int c =0;
int[] a = new int[2*n];
for(int i =0;i<2*n;i++){
a[i]=sc.nextInt();
if(a[i]%2 == 1)c++;
}
if(c%2==0)System.out.println("Yes");
else System.out.println("No");
}
}
}


Can anyone please kindly tell me which test case would fail for this solution because its showing WA for this solution.

Think of -ve values

3 Likes

Okay, I get it now
Thank you

1 Like

problem acchi thi but maths weak hai hamari kya karu any tips??

can u give a test case , i still can’t get why this logic is failing . reply ploxx ;

Thanks, man

-5%2=-1 in java and c++

2 Likes

pick any number X and K, now if you make 1st number by X-K and 2nd number by X+K, the both 1st and 2nd will be even or odd. It is not possible that 1st number is even and 2nd number is odd (or vice versa). So, if array contains some even number, then it should contain one more even number also to fulfill condition (that is given in question) and similarly if array contains some odd number then it sholud contain some another odd number also to fulfill the condition. This means that both even numbers and odd numbers in array should occur even number of times. So u just have to count frequency of odds and evens in array and if both are even, answer is yes else answer is no. Thats it.

1 Like

thanks bro

yes bro i used the same logic but i did if num[i]%2==1 then it’s odd which is false if number is negative just changed it to num[i]%2!=0 and now it’s perfectly fine

This is in golang.
It’s working in my compiler but in CodeChef it’s time limit exceeded

Can anybody tell me why this code is not working? The code with the same logic is working in CPP though

package main

import (
"fmt"
)

func main() {
var TestCase int
fmt.Scanln(&TestCase)

for ; TestCase > 0; TestCase-- {
code()
}
}

func code() {
var elem, N, sum int
fmt.Scanln(&N)

sum = 0
for i := 0; i < 2*N-1; i++ {
fmt.Scanf("%d", &elem)
sum += elem
}
fmt.Scanf("%d\n", &elem)
sum += elem

switch {
case sum%2 == 0:
fmt.Println("YES")
default:
fmt.Println("NO")
}
}



Make the iteration i<2*n;
it can work correctly