CIREQ - Editorial

Here I am using curr as the first index.
suppose you want to make mid number of arrays, then, I am first traversing first index of every array and check I can place that elements there or not and incrementing my curr after every loop of mid.
Exampe:
A=[1,1,1,1,2,2,3,3,3,];
suppose mid is 3
then we have 3 arrays
we can make our arrangements as follows
array1= 1 1 3
array2= 1 2 3
array3= 1 2 3
but this will return false as 2nd element of array1 does not satisfy the condition so we would set low=mid+1.

Now if mid=4
array1 = 1 2 3
array2 = 1 2
array3 = 1 3
array4 = 1 3

this will return true and set high=mid-1.

You can dry run this test case in a notebook and then you will be more clear.

1 Like

Consider this array : 1 1 1 2 2 2 4 4 5 5 5 5 5 5
and consider mid = 3
we have to check whether we can accommodate all the elements in 3 arrays

for element 1 : we can accommodate all 1s in three arrays at index 1

for element 2 : we can also accommodate all 2s in three arrays at index 2

now since element 3 is not present in given array, we will leave those places vacant for now in all the three arrays (till this point, we have 3 vacant places)

for element 4 : there are only two 4s, which will be placed in two of the three arrays. Again we have one vacant place. So till now, we have (3+1 = 4 vacant places).

Till this stage, those three arrays look like:

index:    1   2   3   4   5  

array1:   1   2   _   4   
array2:   1   2   _   4
array3:   1   2   _   _

for element 5 : as we have only three arrays, so we will accommodate only three 5s at index 5 of these three arrays. Now we are left with three 5s and we also have 4 vacant places, so I will accommodate these three remaining 5s in those vacant places. So I will put these remaining 5s at index 3 of these three arrays (we kept those places vacant earlier, now we filled them with 5s). Again we have 1 vacant place which will be used further(if needed).

lastly:

index:    1   2   3   4   5  

array1:   1   2   5   4   5
array2:   1   2   5   4   5
array3:   1   2   5   _   5

Hence we can accommodate all the elements of the given array without violating the condition.

1 Like

/*ॐ नमः शिवाय */
#include<bits/stdc++.h>
#include
typedef long long ll;
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
vectorv(n);
for(int i=0;i<n;i++)
{
cin>>v[i];
}
sort(v.begin(),v.end());
priority_queue<int,vector,greater>pq;
for(int i=0;i<n;i++)
{
pq.emplace(v[i]);
}
int i=1;
int ctr=1;
while(!pq.empty())
{
if(pq.top()>=i)
{
i++;
pq.pop();
}
else
{
ctr++;
i=1;
}
}
cout<<ctr<<endl;
}
return 0;
}
heyy this is my solution can anyone tell me where i am wrong

i am using hashMap approach where I store values and its frequency in hashmap and then
traverse from 1 to n and check which one are gonna increase the arrays , and store them in res , I also taken care of case where (2,3,3,4,5) even if the freq is greater than current but missing elements at start for example 1 in this case cancels out , can anyone tell me what is wrong with my solution and fails for which case , i cant think of any

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc= new Scanner(System.in);
		int T = sc.nextInt();
		for(int i=0;i<T;i++){
		    int n = sc.nextInt();
		    HashMap<Integer,Integer> as = new HashMap<>();
		    for(int j=0;j<n;j++){
		        int num = sc.nextInt();
		        if(as.containsKey(num)){
		            as.put(num , as.get(num)+1);
		        }else{
		            as.put(num, 1);
		        }
		    }
		    
		    int missing = 0;
		    int res =1;
		    
		    for(int j=1;j<=n;j++){
		        if(as.containsKey(j)){
		            int cur=  as.get(j);
		            if(cur<=res){
		                cur=0;
		            }else{
		                cur-=res;
		            }
		            
		            if(cur>=1){
		             cur-=missing;
		             missing=0;
		            }
		            res+=cur;
		            
		        }else{
		            missing++;
		            
		        }
		    }
		    
		    
		    System.out.println(res);
		}
	}
}