REC19C- Editorial

editorial
, ,
1

PROBLEM C : Astral Universe
SETTER : lamda_cdm_10
TESTER : mpsprasnath

QUICK EXPLANATION

We will try to minimize the count of Type 1 stars as much as we can . By following a greedy strategy .

Difficulty

Easy-Medium

PREREQUISITES

Greedy, Arrays

Detailed Explanation

We will follow these 2 strategies for getting the optimal answer

  • First we will traverse through the array and for each Type 2 star we will try to engulf any Type 1 star which is present to it’s left or right , since Type 2 stars are immobile and invincible.
  • Second , we will again traverse through the array and for any position we find a Type 1 star we jump 3 steps forward since we can combine any Type 1 star present in between .
SETTER'S CODE

C++:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long 
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    ll t;
    cin >> t;
    while (t--)
    {
        int n;cin>>n;
        ll arr[n];
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
        }
        int count_2=0;
        for(int i=0;i<n;i++)
        {
            if(arr[i]==2)
            {
                if(i-1>=0&&arr[i-1]==1)
                {
                    arr[i-1]=0;
                }
                if(i+1<n&&arr[i+1]==1)
                {
                    arr[i+1]=0;
                }
                count_2++;
                arr[i]=0;
            }
        }
        int count_1=0;
        for(int i=0;i<n;i++)
        {
            if(arr[i]==1)
            {
                count_1++;
                i+=2;
            }
        }
        cout<<count_2+count_1<<endl;
    }
    return 0;
}
TESTER'S CODE

C++:

#include <iostream>
#include<assert.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	assert(t>=1&&t<=1000);
	
	while(t--)
	{
	    int n;
	    cin>>n;
	    assert(n>=1&&n<=1000000);
	    int a[n];
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	        assert(a[i]>=0&&a[i]<=2);
	    }
	    for(int i=0;i<n;i++)
	    {
	        if(a[i]==1)
	        {
	            if(i>0&&a[i-1]>0)
	            {
	                a[i-1]++;
	                a[i]=0;
	            }
	            else if(i<n-1)
	            {
	                a[i+1]++;
	                a[i]=0;
	                i++;
	            }
	        }
	    }
	    int cnt=0;
	    for(int i=0;i<n;i++)
	    {
	        if(a[i]>0)cnt++;
	    }
	    cout<<cnt<<"\n";
	}
}