PROBLEM LINK:
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);
}
