HAUNTEDHOUSE- Editorial

editorial
, ,
#1

PROBLEM LINK:

Practice
Tester: Aman Nautiyal
Editorialist: Aman Nautiyal

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Binary search on answer, Math.

PROBLEM:

Ayush’s family and a few other families want to go to a haunted house together. They have to enter the haunted house in a single queue. Ayush is a miser and he wants to maximize the fear of every person by making sure that they are as far as possible from their family members in the queue. Every person in the family has a similar code represented with integers.

Ayush is busy packing his bag so he asks you to help him to calculate the greatest minimum distance between the same family member amongst all possible orders of queue.

EXPLANATION:

Let’s note that if you can find the arrangement with the maximum distance of x then you can also find the maximum distance of x-1. It allows you to use the binary search on the answer.

SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;


void solve()
{
    int n,i,person,ans=0,j;
    cin>>n;
    vector<int> family(n+1),vis(n);
    for(int i=0;i<n;i++) 
    {
        cin>>person;
        family[person]++;//storing the number of persons belong to same family (same family code)
    }
    sort(family.begin(),family.end());
    reverse(family.begin(),family.end());//start fixing the order from largest family to smallest 
    int l=0,r=n-2; //maximum possible distance is at most n-2
    while(l<=r)
    {
        int mid=(l+r)/2;
        bool f=true;
        for( i=0;i<n;i++)vis[i]=0;//all positions are available
        for(i=0;i<n;i++)
        {
            if(vis[i]) continue; // if person is present at index i
            for(j=0;j<family[i] && f;j++) 
            {
                int nextpos=i+(mid+1)*j;
                if(nextpos>=n) f=false;//not possible to maintain mid(units) of distance
                else vis[nextpos]=1;
            }
            if(!f)break;
        }
        if(f) ans=max(ans,mid),l=mid+1;
        else r=mid-1;
    }
    cout<<ans<<endl;
}
int main()
{
    IOS;
    int T=1;
    cin>>T;
    for(int t=1;t<=T;t++)
    {
        solve();
    }
    return 0;
}
#2

The process of trial placement at different spacings is unnecessary. We need to know two things:

  • the largest family size (Q)
  • how many families are that size (C)

Then we can calculate the spacing interval. We can allocate the first C places to one member of each of these large families, and then the interval S is [ (N-C)/(Q-1) ] (rounded down) to place the remaining Q{-}1 blocks of C family members. It is relatively easy to see that all smaller families can be placed in the gaps in a way that doesn’t have a tighter spacing.

The interval S calculated here is 1 more than the spacing distance value required by the problem statement - for example people at positions 1 and 4 are at an interval of 3 but the distance required is one less, so S{-}1 is the desired output.

My Python solution