ADJSUMPAR - EDITORIAL

editorial
,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: abhi_inav
Testers: iceknight1093, tabr
Editorialist: hrishik85

DIFFICULTY:

1013

PREREQUISITES:

None

PROBLEM:

We are given an array B. Elements of B are formed from the elements of array A using the following operation

  • B_{i} = (A_i + A_{i+1}) % 2 for 1 <= i <= N-1
  • B_N = (A_1 + A_N) % 2
  • B_i = 0 OR B_i = 1

Given the array B, can there exist an array A such that B can be formed from A?

EXPLANATION:

When do we get 0’s in B? We will get 0s if both Ai and Ai+1 are even or both are odd. When 2 numbers are even or both numbers are odd, their sum is necessarily even.
When do we get 1’s in B? We will get 1s if either A_i is even and A_{i+1} is odd or vice versa.

Implementation
Lets try and construct the array A from array B given the conditions above. Let the 1st element in array A be [1]
We can iterate across B from i = 1 to i = N - 1.
For each i in B from i = 1 to i = N - 1, if B_i = 0, then we append A_{i+1} = A_i
For each i in B from i = 1 to i = N - 1, if Bi not equal to 0, then we append A_{i+1} = (A_i + 1) basically if A_i is odd, we are appending an even number. If A_i is even, we are appending an odd number

Now, our array A is constructed with N elements and we need to check if the 1st and Nth element of A meet the condition which will create BN. We can do this by checking for the condition
If (A_1 + A_N) % 2 = B_N, then A is a valid array. Correspondingly, B then is also a valid array.
If (A_1 + A_N) % 2 is not equal to B_N, then A is invalid. Hence B cannot be constructed from A

TIME COMPLEXITY:

Time complexity is O(N).

SOLUTION:

Editorialist's Solution 
t=int(input())
for _ in range(t):
    n=int(input())
    brr=list(map(int,input().split()))
    arr=[]
    i=0
    arr.append(1)
    while i<n-1:
        if brr[i]==0:
            arr.append(arr[i])
        else:
            arr.append(arr[i]+1)
        i=i+1
    #print(arr)
    if (arr[0]+arr[n-1])%2==brr[n-1]:
        print('YES')
    else:
        print('NO')
2

actually we can just check if \Sigma B_i \% 2 == 0, because \Sigma B_i = 2\Sigma (A_i \% 2).

2 Likes
3

If array A={1,1,1} then B should be {0,0,0}
Then your condition ÎŁBi=2*ÎŁ(Ai%2) will be wrong
​

4

Look at my solution.

What I have done is :
STEP 1:
First I initialized A[0] with 1
Now I iterated every element of Array B, and did the XOR operation with the corresponding element in array A
1 XOR 1 = 0
1 XOR 0 = 1
0 XOR 1 = 1
0 XOR 0 = 0
This way If you will do parity sum(XOR) of A[i]+A[i+1] you will get B[i].
Example test case
1010
now I will do above operation and construct my array A[] which is a[]={1,0,0,1}
Now if you will check A[i] XOR A[i+1] will be equal to B[i];
for the last element of B[last] = A[last] XOR A[0] (According to the question)

Implementation:

void solve() {

int t ;
cin>>t;
while(t–) {
int size;
cin>>size;
int B[size];
int A[size];

FOR(i,0,size)
cin>>B[i];
A[0] = 1;

FOR(i,0,size-1)
{
if((B[i] ^ A[i])== 0)
A[i+1] = 0;
else
A[i+1] = 1;
}
if(B[size-1] ^ A[size-1] == A[0])
cout<<“Yes”<<nline;
else
cout<<“No”<<nline;
}
}

5

would you mind explaining please…with some examples

6

This relation holds modulo 2, in that the modulo 2 sum of B is twice the modulo 2 sum of A.
Even for your counterexample, sum of A modulo 2 = 3 =1, the double of which is 0 and the sum of B is also 0 modulo 2.

To further explain the preceeding remark, since we double the sum of A mod 2 it doesn’t matter what the sum is because 12=02=0 (mod 2) so it is sufficient to check that the sum of B mod 2 is 0.

7

the simplest solution would be to count the number of 1s in B. if number of 1s are even then print yes otherwise no.

8

We can directly calculate sum of list of elements

My solution

# cook your dish here
for i in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    if sum(l)%2==0:
        print("Yes")
    else:
        print("No")