GMARR - Editorial

editorial
1

PROBLEM LINK:

Game Arrangement

Setter- Sarthak Chafle
Tester- Akshit Panday

DIFFICULTY:

Easy

PRE-REQUISITES:

None

PROBLEM:

Chef is a sports teacher and is planning to make the students play a new game, for which he needs the students to be standing in a queue of slots such that no two Students are standing next to each other.

Given an array containing 1′s and 0′s, where 1 means a student and 0 means an empty slot. You need to write a program that calculates whether N more students can be made to stand in the queue without moving any student.

Print YES if N more students can be arranged without violating the no-adjacent student rule else print NO.

EXPLANATION:

For including any student previous and next should also be empty. In case of 0th index we have to check only next index. In case of last index we have to check only previous index.
if any index is included, then next index can’t be part of our solution, so avoid checking that again
if anytime our counter crosses number of students return true immediately no need to check further. Otherwise no more students can be added, return false.

SOLUTION

Setter- imsarthak10 

#include<bits/stdc++.h>
using namespace std;

bool canPlaceStudents(int students[],int n ,int k) {
    if (k == 0) return true;
        for (int i = 0; i < n; i ++) {
            if (students[i] == 0 && (i == 0 || students[i - 1] == 0) && (i == n - 1 || students[i + 1] == 0)) { 
                --k;
                if (k == 0) return true;
                students[i] = 1; 
            }
        }
        return false;
    }
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int arr[n];
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        int k;
        cin>>k;
        if(canPlaceStudents(arr,n,k)){
            cout<<"YES\n";
        }else{
            cout<<"NO\n";
        }
    }
    return 0;
}

Tester- akshitpanday 

t=int(input())
while (t>0):
    n=int(input())
    l = list(map(int, input().split()))
    count =int(input())
    for i in range(n):
        if l[i]==0:
            lf = (i==0) or (l[i-1]==0)
            rf = (i==n-1) or (l[i+1]==0)
            if lf and rf:
                l[i]=1
                count -= 1
                if(count<=0): 
                    break
    if(count<=0):
        print("YES")
    else:
        print("NO")
    t-=1

Time Complexity= O(N)

1 Like