# FREQFUN Editorial

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.

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 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){
}
long long readIntLn(long long l,long long 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);
while(T--){
g_freq.clear();
for(int i=0;i<n;i++){
A_freq[i]=0;
}
for(int i=0;i<n;i++){
if(i==n-1){
} else {
}
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){
} else {
}
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:

https://www.codechef.com/viewsolution/30544928

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