ODDEVENBS - Editorial

editorial
,
#1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: utkarsh_25dec
Testers: nishant403, satyam_343
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given an array B of length N, where B_i denotes the parity of the number of occurrences of element i in array A, where A has length N.

Does a valid array A exist?

EXPLANATION:

Let’s start with an empty array A and try to build a valid one as we go.

For each i from 1 to N,

  • If B_i = 1, there are an odd number of occurrences of i in A. In particular, A must contain at least one occurrence of i, so let’s add exactly one for now.
  • If B_i = 0, there are an even number of occurrences of i in A. Let’s ignore this i for now.

Our process gives us some array A of length \leq N, since it contains at most one occurrence of each i between 1 and N
Notice that we can extend it to length N by adding some more elements, but in order to maintain parity, we can only add an even number of any element.

So, if the remaining length is even, the answer is “Yes”; otherwise the answer is “No”.

This has a rather simple formulation in terms of the input: the initial length of the array we create is exactly the number of ones in B, which equals sum(B) since B is a boolean array.
So, all that needs to be done is to check whether sum(B) and N have the same parity or not!

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Code (Python) 
for _ in range(int(input())):
    n = int(input())
    b = list(map(int, input().split()))
    print('Yes' if sum(b)%2 == n%2 else 'No')
1 Like
#2

In example it is given that for A=[1,1,2,3] => B=[0,1,1,0]
here clearly 1 occurs twice , 2 occurs once and same for 3.
So shouldn’t B=[0,0,1,1]?
here Also sum(B)%2 == n%2 . But how is B=[0,1,1,0] according to the given conditions?

3 Likes
#3

A more simple observation:-

If number of zeros in array b is even… answer always exist else there is no answer

#4

I also have this doubt .

#5

There isn’t a zero based indexing. ( 1 occurs 2 times , 2 and 3 occurs once and 4 occurs 0 times)

1 Like
#6

I think you (and @one_of_them_00) have misunderstood the statement a bit.

B_i is the parity of the frequency of i, not the frequency of A_i.
So for A = [1, 1, 2, 3]:

  • 1 occurs twice, so B_1 = 0
  • 2 occurs once, so B_2 = 1
  • 3 occurs once, so B_3 = 1
  • 4 occurs zero times, so B_4 = 0
2 Likes
#7

Thanks for clearing the confusion.

#8

the statement language was bad i was confused about that too, came here to see that