FREQARRRET - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: munch_01
Preparer: utkarsh_25dec
Testers: iceknight1093, satyam_343
Editorialist: iceknight1093

DIFFICULTY:

1654

PREREQUISITES:

None

PROBLEM:

You are given an array B. Find the lexicographically smallest array A such that B_i equals the frequency of A_i for every i; or report that no such array exists.

EXPLANATION:

As with most tasks that require lexicographic minimization, this one can be solved greedily.

Let’s try to place the 1's, then the 2's, then the 3's, and so on.

Note that we can always set A_1 = 1.
Now, suppose B_1 = x. Then, there are exactly x-1 more 1's in A, and to minimize the final array, we must place them at the leftmost x-1 positions j such that B_j = x.

Then, we can find the first position \gt 1 that is unfilled, place a 2 there, and repeat the same process.
Note that at any step if we are unable to find enough positions to place elements, the answer is immediately -1.
In particular, any x must occur k\cdot x times in B (for some k \geq 0) for the answer to not be -1.

All that needs to be done is to implement this quickly.

Here’s one simple way to do this.
First, build the frequency table of B; let this be freq.
If freq[x] is not a multiple of x for some x, the answer is immediately -1; otherwise we’ll construct a valid array.

Also keep:

  • A variable nxt. Initially, nxt = 1. This denotes the next smallest we are going to use.
  • A second map, say cur, where cur[x] denotes the current value we’re placing that has frequency x.

Let’s iterate i from 1 to N. Suppose A_i = x. Then,

  • If freq[x] is a multiple of x, we must start placing a new element. So, set cur[x] = nxt then increase nxt by 1.
  • Then, set A_i = cur[x] and decrement freq[x] by 1.

It’s easy to see that the array constructed this way is the same one we discussed initially, since we increase cur[x] after placing exactly x instances of the previous value; and this is of course optimal.

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.

CODE:

Setter's code (C++)
#include <iostream>
#include <map>

using namespace std;

map<int,int> F;
pair<int, int> M[100010];
int q, n, B[100010], poss, prev1;

int main()
{
	cin>>q;

	while(q--)
	{
		F.clear();
		poss = 1;
		prev1 = 0;
		cin>>n;
		int cnt = 0;
		for(int i=1;i<=n;i++)
		{
			cin>>B[i];
			F[B[i]]++;
			M[B[i]].first = 0;
			M[B[i]].second = 0;
		}
		
		for(auto it = F.begin(); it != F.end(); it++)
		{
			if( ((it->second)%(it->first))!=0 )
			{
				poss = 0;
				break;
			}
		}
		if(poss==0)
		{
			cout<<-1<<"\n";
			continue;
		}

		for(int i=1;i<=n;i++)
		{
			if( (M[B[i]].first == 0) || (M[B[i]].second == B[i]) )
			{
				prev1++;
				M[B[i]].first = prev1;
				M[B[i]].second = 1;
			}
			else
				M[B[i]].second++;
			cout<<M[B[i]].first;
			if(i<n)
				cout<<" ";
			else
				cout<<"\n";
		}
	}
}
Tester's code (C++)
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;   
using namespace std;  
#define ll long long  
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;    
#define pb push_back                 
#define mp make_pair          
#define nline "\n"                           
#define f first                                          
#define s second                                             
#define pll pair<ll,ll> 
#define all(x) x.begin(),x.end()     
#define vl vector<ll>           
#define vvl vector<vector<ll>>    
#define vvvl vector<vector<vector<ll>>>          
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);  
#endif       
void _print(ll x){cerr<<x;}  
void _print(char x){cerr<<x;}   
void _print(string x){cerr<<x;}    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());   
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";} 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;      
const ll MAX=500500;
void solve(){   
    ll n; cin>>n;
    
    map<ll,vector<ll>> track;
    vector<ll> b(n+5);
    for(ll i=1;i<=n;i++){
        cin>>b[i];
    }
    for(ll i=n;i>=1;i--){
        track[b[i]].push_back(i); 
    }
    vector<ll> a(n+5,-1);
    ll cur=1;  
    for(ll i=1;i<=n;i++){
        if(a[i]==-1){
            ll need=b[i];
            while(need--){
                if(track[b[i]].empty()){
                    cout<<"-1\n";
                    return;
                }
                auto it=track[b[i]].back();
                a[it]=cur;
                track[b[i]].pop_back();
            }
            cur++; 
        }
    }
    for(ll i=1;i<=n;i++){
        cout<<a[i]<<" \n"[i==n];
    }
    return;                                
}                                                   
int main()                                                                                                
{      
    ios_base::sync_with_stdio(false);                          
    cin.tie(NULL);    
    #ifndef ONLINE_JUDGE                    
    freopen("input.txt", "r", stdin);                                              
    freopen("output.txt", "w", stdout);  
    freopen("error.txt", "w", stderr);                        
    #endif                          
    ll test_cases=1;               
    cin>>test_cases;
    while(test_cases--){
        solve();
    } 
    cout<<fixed<<setprecision(10);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
}  
Editorialist's code (Python)
import collections
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	freq = collections.Counter(b)
	curval = {}
	nxt = 1
	a = [-1]*n
	for i in range(n):
		if freq[b[i]]%b[i] == 0:
			curval[b[i]] = nxt
			nxt += 1
		if b[i] not in curval: break
		freq[b[i]] -= 1
		a[i] = curval[b[i]]
	if min(a) == -1: print(-1)
	else: print(*a)
1 Like
#include<bits/stdc++.h>
using namespace std;

#define int long long int
#define ull unsigned long long
#define INF INT_MAX
#define forin for(int i=0;i<n;i++)
#define forjm for(int j=0;j<m;j++)
#define rep(i,x,y) for(int i=x; i<y; i++)
#define pii pair<int,int>
#define vi vector<int>
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define vvpii vector<vector<pair<int,int>>>
#define vvi vector<vector<int>>
#define vpii vector<pair<int,int>>
#define vvvi vector<vector<vector<int>>>

#define gcd __gcd
#define endl '\n'
#define PI acos(-1)
#define lead_zer __builtin_clzll
#define trail_zer __builtin_ctzll
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(long double t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(unsigned long long t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

void pre_process() {
	ios_base::sync_with_stdio(false); // comment out if interactive
	cin.tie(NULL); cout.tie(NULL);  // comment out if interactive
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" : "; _print(x); cerr << endl;
#else
#define debug(x)
#endif
#ifndef ONLINE_JUDGE
	freopen("Error.txt", "w", stderr);
#endif
}

const int M = 1e9 + 7;
const int N = 1e5 + 10;

void solve() {
	int n;
	cin >> n;
	vi f(n);
	map<int, vi> m; // frequency -> index
	vi ans(n, -1);
	rep(i, 0, n) {
		cin >> f[i];
		m[f[i]].pb(i);
	}
	for (auto &pr : m) {
		if (pr.ss.size() % pr.ff != 0) {
			cout << -1 << endl;
			return;
		}
		reverse(all(pr.ss));
	}
	int x = 1;
	//debug(m);
	for (auto val : f) {
		//debug(x);
		vi &vec = m[val];
		if (vec.size()) {
			int r = val;
			while (r--) {
				int ind = vec.back();
				ans[ind] = x;
				vec.ppb();
			}
			x++;
		}
		debug(m);
	}
	rep(i, 0, n) cout << ans[i] << ' ';
	cout << endl;
}

int32_t main() {
	pre_process();
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

anyone please help to find where my solution is wrong

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef{
	static Scanner s = new Scanner(System.in);
	final static int MOD = 1000000007;
	public static void solve(){
		int n = s.nextInt();
		// long[] a = readArray(n,s);
		int[] a = new int[n];
		for(int i = 0;i<n;i++){
			a[i]=s.nextInt();
		}
		Map<Integer, Integer> curr = new HashMap<>();
		Map<Integer, Integer> freq = new HashMap<>();
		Map<Integer, Integer> check = new HashMap<>();
		int[] ans = new int[n];
		int num = 1;
		for(int i = 0;i<n;i++){
			if(!freq.containsKey(a[i])){
				freq.put(a[i], 1);
				curr.put(a[i], num);
				num++;
			}
			else if(freq.get(a[i])%a[i]==0){
				// System.out.println(a[i]+" da");
				curr.put(a[i], num);
				num++;
				freq.put(a[i], freq.get(a[i])+1);
			}
			else{
				freq.put(a[i], freq.get(a[i])+1);
			}
			ans[i]=curr.get(a[i]);
			check.put(ans[i], check.getOrDefault(ans[i],0)+1);
		}
		for(int i = 0;i<n;i++){
			if(check.get(ans[i])!=a[i]){
				System.out.println(-1);
				return;
			}
		}
		for(int i: ans){
			System.out.print(i+" ");
		}
		System.out.println();
	}
	public static void main(String[] args) {
		int t = s.nextInt();
		while(t-->0){
			solve();
		}
	}
	public static long[] readArray(int n, Scanner s){
		long[] ret = new long[n];
		for(int i = 0;i<n;i++){
			ret[i]=s.nextLong();
		}
		return ret;
	}
}

I used the same approach except checking for the cases of -1 but I was getting TLE in last three test cases.

Consider input

1
5
2 2 1 2 2

The answer is 1 1 2 3 3

Java’s default output is very slow, especially when you call System.out.print for each integer (since it flushes the buffer each time).
Simply using the faster PrintWriter will get you AC: submission
You can also write a FastScanner class to take input faster, since the default Scanner is quite slow.
I recommend looking at SecondThread’s submissions for how to write Java code, at least for contest purposes.

1 Like

Thanks bro, i just further needed to check if for a particular index in frequency array its element has already been decided

for (int i = 0; i < n; i++) {
		int val = f[i];
		vi &vec = m[val];
		if (vec.size() && **ans[i] == -1**) {
			int r = val;
			while (r--) {
				int ind = vec.back();
				ans[ind] = x;
				vec.ppb();
			}
			x++;
		}
		debug(m);
	}

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

#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define f(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define pb push_back

using namespace std;

void test(){
int n;
cin>>n;

vector<int> b(n),a(n);
f(i,n)cin>>b[i];

unordered_map<int,int> freq,cur;

f(i,n)freq[b[i]]++;

bool ans=true;
for(auto i:freq){
    if(i.second%i.first!=0)ans=false;
}

if(ans){
    int nxt=1;
    
    f(i,n){
        if(freq[b[i]]%b[i]==0){
            cur[b[i]]=nxt;
            a[i]=cur[b[i]];
            nxt++;
            freq[b[i]]--;
        }
        else{
            a[i]=cur[b[i]];
            freq[b[i]]--;
        }
    }
    f(i,n)cout<<a[i]<<" ";
    cout<<"\n";
}
else cout<<-1<<"\n";

}

int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests=1;
cin>>tests;
while(tests–){
test();
}
}

Why this code is giving runtime error even for Sample 1 , Test cases ?

MY LOGIC :

  • Array A is the given array

  • Created a vector p , which contains the final answer [ lexicographically smallest array ]

  • Created a vector cnt , which is keeping track of number of times a particular Integer has been inserted to vector p

  • Created a pair track

  • track[i].first indicates whether we already have a integer associated with A[i]

  • track[i].second is the actual integer associated with A[i]

  • Integer variable num, is used to push lexicographically smallest integer

  • Integer variable get_out is used for TEST CASES like [ 1 2 4 ] , which tells when to return -1

  • Now,

  • Inside for loop
    * if condition → if trace[A[i]]==0 that means no integer is associated with A[i]
    and we associate an Integer with A[i]
    * else condition → Lexicographically smallest Integer is associated for A[i]
    if condition → Used for TEST CASES like [ 1 1 1 1 1 ] , [ 1 3 2 3 2 2 2 3 ]
    else condition → when Integer is already associated for particular A[i]
    we are just fetching that value from PAIR trace[i].second

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 100001

void freq_array(int a[],int n){
    ll get_out=0;
    vector<ll> p;
    vector<ll> cnt{MAX,0};
    vector<pair<bool,ll>> track(MAX,{0,0});
    int num=1;
    for(int i=0;i<n;i++)
    {
        if(track[a[i]].first==0)
        {
            track[a[i]].first=1;
            track[a[i]].second=num;
            p.push_back(num);
            cnt[a[i]]++;
            num++;
            get_out+=a[i];
        }
        else
        {
            if( cnt[a[i]]==a[i] )
            {
                track[a[i]].first=1;
                track[a[i]].second=num;
                p.push_back(num);
                cnt[a[i]]=1;        // reset
                num++;
                get_out+=a[i];
            }
            else
            {
                p.push_back(track[a[i]].second);
                cnt[a[i]]++;
            }
        }
        if(get_out>n){
            cout<<"-1";
            return;
        }
    }
    
    for(int i=0;i<p.size();i++)
        cout<<p[i]<<" ";
}
int main() {
	int T; cin>>T;
	while(T--){
	    int N;
	    cin>>N;
	    int B[N];
	    for(int i=0;i<N;i++)
	        cin>>B[i];
	    freq_array(B,N);
	    cout<<endl;
	}
	return 0;
}

Can anyone Please help me sort this RUNTIMR ERROR ?

damm this question is a bit tough to crack