ARRAYBREAK Editorial

editorial
, ,
1

PROBLEM LINK:

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

Setter: Utkarsh Gupta
Tester: Satyam, Tejas Pandey
Editorialist: Pratiyush Mishra

DIFFICULTY:

1191

PREREQUISITES:

None

PROBLEM:

Chef has an array A of length N. In one operation, Chef can choose any element A_i and split it into two positive integers X and Y such that X+Y = A_i.
Note that the length of array increases by 1 after every operation.

Determine the minimum numbers of operations required by Chef to make parity of all the elements same.

It is guaranteed that parity of all the elements can be made equal after applying the above operation zero or more times.

EXPLANATION:

Observation \;1: We can convert an even number, say x to two odd numbers by splitting into 1 and x-1 but we cannot convert an odd number to two even numbers.

Thus if there is any odd number present in the array we will have to make parity of each element in the array as odd.

Therefore there can be two cases:
Case \; 1: All elements are even
In this case answer would be 0, since parity of each element is same, that is even.

Case \; 2: All elements are not even:
In this case, we will calculate number of even elements and our answer would be the number of even elements since we will apply operation on each even element to split it into two odd elements.

TIME COMPLEXITY:

O(N), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

2

very strange, it seems that my same code which returned false only for task 2 during the competition now works

1 Like
3

yeah i was confused at first too it didn’t return , i thought i was wrong but after checking a bunch of codes and trying again it did return ,

void solve(){

ll n; cin>>n;

int a[n], odd=0, even=0;

for(ll i=0; i<n; i++){

    cin>>a[i];

    if(a[i]%2==0) even++;

    else odd++;

}

// if(odd>=even)   cout<<even<<endl;

// else if(even>odd){

//   //cout<<odd<<endl;  

// }

//cout<<even<<endl;

if(odd == n || even == n) cout<<0<<endl;

//else if(odd>=even) cout<<even<<endl;

//else cout<<even-odd<<endl;

else cout<<even<<endl;

}