 # REC19C- Editorial

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

• 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";
}
}

``````