Maximize the number of disjoint subarrays with even sum in an array in at most k swaps .

Question

Time Complexity should be O(N)  .

Example array :

k = 1 (number of swaps allowed)

{1,2,3,4} ..

Without any swaps the answer is : (2) : {2} and {4} are the only even sum disjoint subarrays .

If we do 1 swap of (2,3) , we get : 1,3,2,4 , and the answer is : (3) : {1,3} , {2} , {4} are the three disjoint even sum subarrays!

Answer 1

Ok, so the full solution depends on complicated observations...Lets try to find best answer for zero swaps, to maximize the number of even sum subarrays , we need to keep all even guys alone and merge 2 adjacent odd guys . For example, array a = [2,3,5,6,8,9,11] .

Best answer for this is :

{2},{3,5},{6},{8},{9,11}

I merged the odd guys and kept even guys alone which maximizes our answer .

Answer here is 5 parts.

So we know how to solve for k=0 swaps.

The problem only occurs when the odd guys appear for odd number of times in a continuous subarray .

Example , {3,5,7,2,11,13,15}

After making groups : {3,5} , {7} , {2}, {11} , {13,15}


We can see that 7 and 11 are in-valid guys


They make odd sum subarray we dont like it . 


Using 1 swap, we can fix 2 such odd guys , so using k swaps you can fix 2k odd guys which are invalid .


So just fix the 2k odd guys and you are done!


Answer for 0 swaps is : 3 , but if we do 1 swap of (2,7), answer becomes 4 , {3,5},{2},{7,11},{13,15} . 4 even parts achieved!!

Say , we have : {odd1,even1,.................odd2} . We simply always swap even1 guy with odd2 guy and get : {odd1,odd2,.........even1} and hence 1 quantity of even sum subarray has increased ! Voila ! :-) 

Its a common sense part that even and odd chunks of array gonna alternate , just find the total number of invalid off guys in the array and fix 2*k guys out of them

, the final array which u get is the best possible answer .

 

Code : 

#include <bits/stdc++.h>
using namespace std ;
typedef long long int ll ; 
int main()
{
    
    ll n ; 
    cin>>n ; 
    ll k ; 
    cin>>k ; 
    ll i = 0 ; 
    ll a[n+1] ; 
    while(i<=n-1)
    {
        cin>>a[i] ; 
        i++;
    }
    i=0;ll c = 0 ; ll d = 0 ; 
    ll e = 0 ; ll count = 0 ; 
    while(i<=n-1)
    {
        
        if(a[i]%2!=0)
        {
            c++;
        }
        else
        {
            d++;
            if(c%2!=0)
            {
                count++;
            }
            e = e + c/2;
            c=0;
        }
        
        
        i++;
    }
    
     if(c%2!=0)
            {
                count++;
            }
        e = e + c/2;
    
    ll answer = d + e ; 
   
    ll god = 0 ; 
    god = min(count/2,k);
    answer = answer + god ;
    cout<<answer ; 
    return 0 ; 
}