FREQFUN Editorial

PROBLEM LINK:

Practice
Contest

Tester: Roman Bilyi
Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

Chef had a sequence S_0,S_1,…,S_{N−1}; each element of this sequence was an integer between 0 and N−1 (inclusive). Unfortunately, he forgot some (possibly zero or all) elements of this sequence. You are given a sequence A_0,A_1,…,A_{N−1}, where for each valid i, A_i=−1 denotes an element Chef forgot and if A_i≠−1, then A_i=S_i.

Before Chef forgot any elements of S, he created a sequence B_0,B_1,…,B_{N−1}, where for each valid i, B_i is the number of occurrences of the value i in S (the number of valid indices j such that S_j=i), and then, he created a third sequence G_0,G_1,…,G_N, where for each valid i, G_i is the number of occurrences of the value i in B. (Note that the elements of B are between 0 and N inclusive.) Unfortunately, Chef also forgot the sequence B, but he remembers G.

Help Chef restore the missing elements of the sequence S. Precisely, find the lexicographically smallest sequence S which is consistent with all the given information or determine that there is no such sequence.

DIFFICULTY:

Easy-Medium

CONSTRAINTS

1 \leq N \leq 10^5

EXPLANATION:

According to the problem statement, B is the array denoting the frequency of each number in S. Formally if B_i=x then the number i occurred x times. Now having G is equivalent to having B BUT without order. So if G_p=q it means that p occurred q times in B, and implying that there are q values where each occurred p times in S.

Obviously if \displaystyle \sum_{i=0}^{i=N} i*G_i \neq N there will be no answer.

Also if \displaystyle \sum_{i=0}^{i=N} G_i \neq N there wil be no answer, simply because it would be an invalid array, because we are recording the frequencies of N distinct values.

Now because there are some elements that he remembers, let’s find a frequency array C such that C_i denotes the number of occurrences of i in A. (Of course, we should omit -1 values). Now notice that C_i \leq B_i for every i.

Now, remember, we had the values of B (but they were unordered or not-indexed). But because we need to find any consistent array, matching every C_i with a value greater than or equal to it from G would solve the problem. That’s true because for every value we would be increasing its occurrences in our array.

Let’s keep the values of B in a multiset. We just loop over elements of G and if G_p=q we insert a number p for q times in the multiset.

To find the lexicographically minimum array, loop over values form N-1 to 0 and now for some value, i find the lower bound of C_i in the multiset and denote it by L. Then we will be having additional L-C_i elements equal to i.

This approach is correct because we need a lexicographically minimal solution, meaning smaller values should be more frequent. So by matching each value of C_i with its lower bound (while moving from biggest value to smallest value) it means that we are leaving higher frequencies to assign them to C_k where k \lt i .

After finding a sequence of missing values just loop over A from left to right and fill it with missing values in ascending order.

Editorialist solution
#include <bits/stdc++.h>
using namespace std;
int atleast[1<<20] ,arr[1<<20] , rep[1<<20];
int main() {
	int T;
	cin >> T;
	while (T--) {
		int n , miss = 0;
		scanf("%d",&n);
		for(int j = 0 ; j < n ; j++)
			atleast[j] = 0;
		for(int j = 0 ; j < n ; j++){
			int x;
			scanf("%d",&x);
			arr[j] = x; 
			if(x != -1)
				++atleast[x];
			else miss++;
		}

		int tot = 0;
		multiset < int > S;
		for(int j = 0 ; j <= n ; j++){
			int rep;
			scanf("%d",&rep);
			tot += j * rep;
			while(rep--){
				S.insert(j);
			}
		}

		bool nosol = 0;
		if(tot != n)
			nosol = 1;


		vector < int > rem;

		for(int j = n - 1 ; j >= 0 ; j--){
			auto it =S.lower_bound(atleast[j]);
			if(it == S.end()){
				nosol = 1;
				break;
			}
			rep[j] = *it;
			S.erase(it);
			for(int i = 0 ; i < rep[j] - atleast[j] ; i++)
				rem.push_back(j);
		}

		sort(rem.begin() , rem.end());

		if(miss != rem.size())
			nosol = 1;

		if(nosol){
			puts("impossible");
			continue;
		}
		int tt = 0;
		for(int j = 0 ; j < n ; j++){
			if(arr[j] == -1)
				arr[j] = rem[tt++];
			printf("%d ",arr[j]);
		}
		puts("");
	}


}
Tester Solution
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <assert.h>
using namespace std;



long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);

			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}


int T;
int n;
int sm_n = 0;
int A[100100];
int A_freq[100100];
int new_freq[100100];
int G[100100];
map<int,int> g_freq;
map<int,int>::iterator itr;

int find_freq(int f){
	itr = g_freq.lower_bound(f);
	if(itr==g_freq.end()){
		return -1;
	}
	int ret =itr->first;
	if(itr->second == 1){
		g_freq.erase(itr);
	} else {
		g_freq[ret]--;
	}
	return ret;
}

int main(){
	//freopen("00.txt","r",stdin);
	//freopen("00o.txt","w",stdout);
	T=readIntLn(1,1000);
	while(T--){
		g_freq.clear();
		n=readIntLn(2,100000);
		for(int i=0;i<n;i++){
			A_freq[i]=0;
		}
		for(int i=0;i<n;i++){
			if(i==n-1){
				A[i]=readIntLn(-1,n-1);
			} else {
				A[i]=readIntSp(-1,n-1);
			}
			if(A[i] != -1){
				A_freq[A[i]]++;
			}
		}
		long long tot=0,tot2=0;
		for(int i=0;i<n+1;i++){
			if(i==n){
				G[i]=readIntLn(0,n);
			} else {
				G[i]=readIntSp(0,n);
			}
			tot += G[i];
			tot2 += G[i] * i;
		}
		if(tot != n || tot2 != n){
			cout<<"impossible"<<endl;
			continue;
		}
		for(int i=0;i<n+1;i++){
			for(int j=0;j<G[i];j++){
				g_freq[i]++;
			}
		}
		bool ok=true;
		for(int i=n-1;i>=0;i--){
			new_freq[i] = find_freq(A_freq[i]);
			if(new_freq[i] == -1){
				ok=false;
				break;
			}
		}
		if(!ok){
			cout<<"impossible"<<endl;
			continue;
		}
		vector<int> new_ele;
		for(int i=n-1;i>=0;i--){
			for(int j=0;j<new_freq[i] - A_freq[i];j++){
				new_ele.push_back(i);
			}
		}
		for(int i=0;i<n;i++){
			if(A[i] == -1){
				A[i] = new_ele.back();
				new_ele.pop_back();
			}
			cout<<A[i]<<" ";
		}
		cout<<endl;
	}
	assert(getchar()==-1);
}
4 Likes
/* greta thunberg sucks */
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <bits/stdc++.h> 
using namespace std;

int main()
{
    long long int T,N;
    long long int i,j,k;
    cin>>T;
    long long int A[100005];
    long long int G[100005];
    for(i=0;i<T;i++)
    {
        //---------------------------------------------------------------------------------------
        //---------------------------------------------------------------------------------------
        //---------------------------------------------------------------------------------------
        //---------------------------------------------------------------------------------------
        //---------------------------------------------------------------------------------------
        //---------------------------------------------------------------------------------------
        map<long long int,long long int> mapb;//contains incomplete B
        map<long long int,long long int> neu;
        
        vector<long long int> v;//contains complete B in shuffled order
        // vector<long long int> B;
        cin>>N;
        long long int poss=0;//possible or not
        for(j=0;j<N;j++)
        {
            cin>>A[j];
            mapb[A[j]]++;//this is a map;
        }
        long long int sum=0;
        for(j=0;j<N+1;j++)
        {
            cin>>G[j];
            poss=poss+j*G[j];
            sum = sum + G[j];
            // cout<<G[j]<<" ";
        }
        // cout<<poss;
        // break;
        if(poss != N || sum != N)
        {
            cout<<"impossible"<<endl;
            continue;
        }
        for(j=0;j<N+1;j++)
        {
            for(k=0;k<G[j];k++)
            {
                v.push_back(j);
            }
        }
        vector<long long int> &temp = v;
        for(auto x = --mapb.end();x != mapb.begin();x--)
        {
            auto lw = lower_bound(temp.begin(),temp.end(),x->second);//itterator long long intemp
            neu[x->first] = *lw;
            temp.erase(lw);
        }//neu map contains the frequency of the elements which chef remembers
        for(j=0;j<N;j++)
        {
            if(temp.size() == 0)
            break;
            auto m = max_element(temp.begin(),temp.end());
            if(neu[j] == 0)
            {
                neu[j] = *m;
                temp.erase(m);
            }
            else if(neu[j] < *m)
            {
                temp.push_back(neu[j]);
                neu[j] = *m;
                temp.erase(m);
            }
        }
        // for(auto x = neu.begin();x != neu.end();x++)
        // {
        //     cout<<x->first<<" "<<x->second<<endl;
        // }
        
        for(j=0;j<N;j++)//removes all the known elements in the original array from the neu map
        {
            if(A[j] == -1)
            {}
            else
            {
                neu[A[j]]--;
                if(neu[A[j]] == 0)
                neu.erase(A[j]);
            }
        }

        // for(auto x = neu.begin();x != neu.end();x++)
        // {
        //     cout<<x->first<<" "<<x->second<<endl;
        // }
        auto x = neu.begin();
        for(j=0;j<N;j++)
        {
            if(A[j] == -1)
            {
                if (x->second == 0)
                x++;
                cout<<x->first<<" ";
                // (*x)--;
                (x->second)--;
            }
            else
            cout<<A[j]<<" ";
        }
        cout<<endl;
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
}

this is giving segmentation fault pls help.
the test cases with the question are running perfectly

    for(auto x = --mapb.end();x != mapb.begin();x--)
    {
        auto lw = lower_bound(temp.begin(),temp.end(),x->second);
        neu[x->first] = *lw;
        temp.erase(lw);
    }

Your code does not consider the case when the temp vector has all value lower than x->second and lower_bound() returns temp.end(). In that case, *lw will give SIGSEGV.
Example of a failing test case:
1
5
1 1 1 1 -1
3 0 1 1 0 0

Hlo ankit_2305…i did not understand the above solution. Can you plz explain in a more clear manner ?

i just observed that setters solution gives answer as impossible whereas the testers solution gives sigabrt. lol​:joy::joy:

https://www.codechef.com/viewsolution/30544928
could you please help me further. getting a TLE

update : found it. It is because of lower_bound.
lower_bound(b.begin(), b.end(), ba[i]) is O(n)
b.lower_bound(ba[i]) is logarithmic

damnn