CHEFCWED -Editorial

#Problem link:
[Practice] Contest Page | CodeChef
[Codeyssey] Contest Page | CodeChef

Author: [Akshat Goyal] CodeChef User | CodeChef
Tester: [V Surya Kumar] CodeChef User | CodeChef
Editorialist: [Akshat Goyal] CodeChef User | CodeChef

DIFFICULTY: EASY
# PREREQUISITES: Math

Problem with explanation:

Chef has some guests N out of which K are vip, they have their fixed seats provided.
The guests have to be seated so that no 2 guests are seated side by side so if a guest has to be seated at chair 2 no one should sit at chair 1 & 3. We need to find the minimum number possible for the last guest to be seatead) vip or not.

  • So we take the total guests and vip guests.

  • Take the chair preference of the vip guests.

  • Now subtract the vip guests from total guests to find the normal guests we have to arrange.

  • Now We check from seat 1 to first seat of vip guest say first vip guest is at 5
    So we calculate total available seats in 1&5 on which a guest can be seated so no one can sit at seat 4 due to vip guest present at seat 5. So seat 1 to 3 are available we place a guest at 1 followed by one at 3.

  • Now we check the number of guests which can be seated between the first vip guest and 2nd vip guest. Say second vip guest is at 10 so b/w 5 to 10 we place our normal guests accordingly.
    We do this till either we have seated people between all vip guests or we have seated all of our guest we will achieve this by the while loop which you will see in code of editorialist.

  • After we finish the above process we check whether we have any normal guests left to be seated or not.

  • If left than we just seat them from our last vip guest at a distance of 2 for each guest say our last vip guest was seated at chair 10 and we have 5 more guests to be seated we put them at 10+2*left i,e(12,14,16,18,20). We give 20 as the output.

  • If guests were not left than 10 is our answer since he’s the last guest to be seated.

  • This gives us a solution in O(1) time complexity.

#Solutions:

Editorialist’s Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
  ll n,k;
 cin>>n>>k;
 ll a[k];
 for(int i=0;i<k;i++)
 cin>>a[i];
 sort(a,a+k);
 n-=k;
 ll j=1,i=0,seat=1,diff;
 while(n>0&&i<=k-1)
{
  diff=(a[i]-1)-j;
  seat=ceil(double(diff)/double(2));
  n-=seat;
   j=a[i]+2;
   i++;

}
if(n<=0)
  cout<<a[k-1]<<endl;
else
   cout<<a[k-1]+2*n<<endl;

}

int main() {
  ios_base::sync_with_stdio(false);
  cout.tie(0); cin.tie(0);
  int t;
  cin>>t;
  while(t- -) //remove space b/w ‘-’ to run
    solve();
}

Tester’s Solution

// Created by surya (chief_surya01 || surya-x)
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define rep(i,x,n) for(ll i=x;i<n;i++)
#define endl “\n”;

int solve(){
// solution starts from here
  ll n, k, i, prev = -1, seats;
   bool flag = false;
   cin>>n>>k;
  ll arr[k];
   rep(i,0,k) cin>>arr[i];

if(n<k){
    cout<<arr[k-1]<<endl;
 return 0;
}
rep(i,0,k){
    seats = (arr[i] - prev - 2)/2;
    prev = arr[i];
    n -= seats;
    if(n<=0){
        flag = true;
        break;
     }
}

     if (!flag) {
       n-=k;
       cout << (arr[k - 1] + 2 * n) << “\n”;
}
else
      cout<<arr[k-1]<<endl;
    return 0;
}

int main(){
FASTIO;
ll tt = 1;
cin>>tt;
while(tt–){
solve();
}
return 0;
}

1 Like