HDDN - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Kasra Mazaheri

Tester: Arshia

Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Implementation and Resilience would be more than sufficient :stuck_out_tongue:

PROBLEM:

There’s a sequence A of length N containing elements in the range [1, K]. You are given information in the form of M tuples, ith tuple being of form (X_i, Y_i, Z_i) which determines that A_{Z_i} = X_i and there exists Y_i-1 indices j < Z_i such that A_j = X_i

Find any sequence A consistent with the above information or determine no valid sequence does not exist.

QUICK EXPLANATION

  • If there exists two tuples i and j such that Z_i = Z_j but X_i \neq X_j, then no valid sequence can exist.
  • We can consider tuples in increasing order of Z_i, now for each index p, consider all tuples with Z_i = p and check if you can fill empty positions before position p to ensure exactly Y_i-1 occurrences of X_i. If there already are more than Y_i-1 occurrences, we cannot reduce previous occurrences, so no valid sequence exists. We can keep a frequency array for each element in the range [1, K]
  • For finding an empty position in the sequence A, we can use sets or segment tree (handling queries first empty position in suffix [p, N]). We need to choose p so as not to violate previous tuples, so considering all tuples with the same X_i, p is the maximum of their Z_i.
  • If at any point some tuple is not satisfied, no sequence exists. If we manage to satisfy all tuples, then we need to fill the remaining empty positions using any suitable element.

EXPLANATION

The quick explanation says it all, Quickly :smiley:

If there are some tuples with the same Z_i = Z_j have X_i \neq X_j, then these two tuples try to assign different values to the same position, which is, of course, impossible, so no valid sequence exists in such case.

Since a tuple specifies the frequency of X_i in prefix up to position Z_i to be Y_i, tuples with smaller Z_i constraint a smaller prefix. We can try constructing sequence from left to right, filling element only in the following cases

  • For position p, we get a tuple with Z_i = p
  • In order to handle the frequency requirements of an element in prefix.

The first case can altogether be handled by assigning values. So, we assign these values and then consider all tuples in increasing order of Z_i since when considering this tuple, all tuples covering smaller prefix are already considered.

Now, Suppose we are considering a tuple (X_i, Y_i, Z_i) now, all previous tuples are satisfied and possibly some positions in first Z_i elements of sequence may not be assigned yet. For position Z_i, X_i is assigned. All that is left is to make Y_i-1 positions before Z_i to have value X_i. We can maintain a frequency array to keep track of the frequency of each element.

Following cases arise

  • Frequency of X_i in first Z_i-1 is Y_i-1
  • Frequency of X_i in first Z_i-1 is greater than Y_i-1
  • Frequency of X_i in first Z_i-1 is less than Y_i-1

In the first case, nothing needs to be done, as the constraint is already met.
In the second case, nothing can be done, as there’s no way to reduce the frequency of an element without violating some previous tuple, which we cannot do, so no valid sequence exists.
In the third case, we have the option to fill empty positions with X_i such that we can reach the first case.

Now, suppose there is some tuple (X_j, Y_j, Z_j) such that X_j = X_i and Z_j < Z_i, then while considering tuple (X_i, Y_i, Z_i), we assign some empty position p \leq Z_j to X_i, it’ll violate the tuple (X_j, Y_j, Z_j). So, in such case, we can assign X_i to positions after Z_j only.

One such Example

1
5 2 2
1 2 4
1 4 5

We cannot find any sequence satisfying both constraints.

Hence, for each value v, we can keep track of the position where onwards we can assign some position with value v, say last_v, and updating last_{X_i} = Z_i after considering the tuple.

All that is left is to quickly find the first empty position at or after position p, which can be achieved using ordered sets or segment tree (refer editorialist solution for this).

Now, if we manage to satisfy all tuples, we need to find a way to fill empty tuples which is left as an exercise with a similar logic as above.

A case to consider
1
6 2 2
1 2 4
2 2 5

Have fun!

TIME COMPLEXITY

The time complexity is O(N*log(N)+M*log(M)+K) per test case.

SOLUTIONS:

Setter's Solution
// In The Name Of the Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 500005;
int n, m, k, A[N], X[N], Y[N], Z[N], P[N], L[N];
vector < pair < int , int > > V[N];
inline bool CMP(int i, int j)
{
	return (Z[i] < Z[j]);
}
inline void Solve()
{
	scanf("%d%d%d", &n, &k, &m);
	for (int i = 1; i <= k; i ++)
	    V[i].clear(), L[i] = 0;
	for (int i = 1; i <= n; i ++)
	    A[i] = 0;
	bool fail = 0;
	for (int i = 1; i <= m; i ++)
	{
	    scanf("%d%d%d", &X[i], &Y[i], &Z[i]);
	    if (A[Z[i]]) fail = 1;
	    V[X[i]].push_back({Y[i], Z[i]});
	    A[Z[i]] = X[i];
	}
	if (fail) {printf("No\n"); return ;}
	for (int i = 1; i <= k; i ++)
	{
	    sort(V[i].begin(), V[i].end());
	    for (int j = 1; j < (int)V[i].size(); j ++)
	        if (V[i][j].first == V[i][j - 1].first || V[i][j].second < V[i][j - 1].second)
	            {printf("No\n"); return ;}
	}
	iota(P, P + m + 1, 0);
	sort(P + 1, P + m + 1, CMP);
	set < int > ST;
	for (int i = 1; i <= n; i ++)
	    if (!A[i]) ST.insert(i);
	for (int j = 1; j <= m; j ++)
	{
	    int i = P[j];
	    int l = Z[L[X[i]]] + 1;
	    int c = Y[i] - Y[L[X[i]]] - 1;
	    auto it = ST.lower_bound(l);
	    while (c && it != ST.end() && *it < Z[i])
	        A[*it] = X[i], it = ST.erase(it), c --;
	    if (c) {printf("No\n"); return ;}
	    L[X[i]] = i;
	}
	int dummy = 0;
	for (int i = 1; i <= k; i ++)
	    if (!V[i].size()) dummy = i;
	for (int i = 1; i <= n; i ++)
	{
	    if (A[i] && V[A[i]].back().second == i && !dummy)
	        dummy = A[i];
	    if (!A[i] && !dummy)
	        {printf("No\n"); return ;}
	    if (!A[i]) A[i] = dummy;
	}
	printf("Yes\n");
	for (int i = 1; i <= n; i ++)
	    printf("%d ", A[i]);
	printf("\n");
}
int main()
{
	int q;
	scanf("%d", &q);
	for (; q; q --)
	    Solve();
	return 0;
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}

#define ll int
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>

using namespace :: std;


//=======================================================================//
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
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,' ');
}
//=======================================================================//



const ll maxn=5e5+500;
const ll inf=1e9;
ll x[maxn];
ll y[maxn];
ll z[maxn];
ll ans[maxn];

pii vec[maxn];
pair<ll,pii> gh[maxn];
ll cnt[maxn];
ll last[maxn];

void cleann(ll n){
	n+=2;
	fill(vec,vec+n,mp(0,0));
	fill(cnt,cnt+n,0);
	fill(gh,gh+n,mp(0,mp(0,0)));
	fill(ans,ans+n,0);
	fill(last,last+n,-1);
}
void solve(ll n,ll k,ll m){
	for(ll i=0;i<m;i++){
		if(vec[z[i]]!=mp(0,0)){
			cout<<"No\n";
			return;
		}
		gh[i]=mp(z[i],mp(x[i],y[i]));
		vec[z[i]]=mp(x[i],y[i]);
	}
	set<ll> khali;
	for(ll i=1;i<=n;i++){
		if(vec[i]==mp(0,0)){
	        khali.insert(i);
		}
	}
	sort(gh,gh+m);
	for(ll i=0;i<m;i++){
		ll x=gh[i].S.F;
		ll y=gh[i].S.S;
		ll z=gh[i].F;
		ll s;
		if(last[x]==-1){
			s=0;
		}else{
			s=gh[last[x]].F+1;
		}
		last[x]=i;
		while(cnt[x]+1<y){
			auto it=khali.lower_bound(s);
			if(it==khali.end() || (*it)>=z){
				cout<<"No\n";
				return ;
			}
			ans[*it]=x;
			khali.erase(it);
			cnt[x]++;
		}
		ans[z]=x;
		cnt[x]++;
		if(cnt[x]!=y){
			cout<<"No\n";
			return;
		}
	}
	pii o=mp(inf,inf);
	for(ll i=1;i<=k;i++){
		o=min(o,mp(last[i],i));
	}
	ll s=-1;
	if(o.F!=-1)s=gh[o.F].F;
	for(ll i=1;i<=n;i++){
		if(ans[i]==0 && i<s){
			cout<<"No\n";
			return ;
		}
		if(ans[i]==0){
			ans[i]=o.S;
		}
	}


	cout<<"Yes\n";
	for(ll i=1;i<=n;i++){
		cout<<ans[i]<<' ';
	}
	cout<<endl;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll t;
	t=readIntLn(1,(ll)5e5);
	for(ll iii=0;iii<t;iii++){
		ll n,k,m;
		n=readIntSp(1,(ll)5e5);
		k=readIntSp(1,(ll)5e5);
		m=readIntLn(1,(ll)5e5);
		for(ll i=0;i<m;i++){
			x[i]=readIntSp(1,k);
			y[i]=readIntSp(1,n);
			z[i]=readIntLn(1,n);
		}
		ll mxx=max(n,max(k,m));
		cleann(mxx);
		solve(n,k,m);
	}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class HDDN{
	//SOLUTION BEGIN
	int M = 1;
	int[] tr;
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni(), k = ni(), m = ni();
	    Tuple[] t = new Tuple[m];
	    for(int i = 0; i< m; i++)
	        t[i] = new Tuple(ni()-1, ni(), ni()-1);
	    
	    while(M<= n)M <<=1;
	    tr = new int[M<<1];
	    for(int i = 0; i< M; i++)tr[i+M] = -1;
	    for(int i = M-1; i> 0; i--)tr[i] = Math.min(tr[i<<1], tr[i<<1|1]);
	    
	    boolean valid = true;
	    for(int i = 0; i < m && valid; i++)
	        valid &= upd(t[i].z, t[i].x);
	    Arrays.sort(t, (Tuple t1, Tuple t2) -> Integer.compare(t1.z, t2.z));
	    int[] last = new int[k];
	    int ind = 0;
	    int[] cnt = new int[k];
	    for(int i = 0; i< n && valid; i++){
	        while(valid && ind < m && t[ind].z == i){
	            if(cnt[t[ind].x] > t[ind].y-1)valid = false;
	            while(valid && last[t[ind].x] < i && cnt[t[ind].x] < t[ind].y-1){
	                int nxt = getNext(last[t[ind].x]);
	                if(nxt >= i || !upd(nxt, t[ind].x)){
	                    valid = false;
	                    break;
	                }
	                cnt[t[ind].x]++;
	                last[t[ind].x] = nxt;
	            }
	            valid &= cnt[t[ind].x] == t[ind].y-1;
	            if(valid && cnt[t[ind].x] > 0)hold(last[t[ind].x] < i);
	            last[t[ind].x] = t[ind].z;
	            ind++;
	        }
	        if(tr[i+M] != -1)cnt[tr[i+M]]++;
	    }
	    int ii = -1;
	    int p = getNext(0);
	    
	    if(p < n)for(int i = 0; i< k; i++)if((last[i] = getNext(last[i])) <= p && ii == -1)ii = i;
	    if(ii == -1 && p< n)valid = false;
	    if(valid){
	        pn("Yes");
	        p = n;
	        while((p = getNext(0)) < n)
	            upd(p++, ii);
	        for(int i = 0; i< n; i++)p(tr[i+M]+1+" ");pn("");
	    }
	    else pn("No");
	}
	//Assigns Ap = v, returns false if its already assigned some different value
	boolean upd(int p, int v){
	    p+=M;
	    if(tr[p] != -1 && tr[p] != v)return false;
	    tr[p] = v;
	    for(p>>=1; p> 0; p>>=1)tr[p] = Math.min(tr[p<<1], tr[p<<1|1]);
	    return true;
	}
	//Returns minimum position q  >= p such that Aq is not assigned yet
	int getNext(int p){
	    if(tr[p+M] == -1)return p;
	    return ind(p+M, true)-M;
	}
	int ind(int p, boolean up){
	    if(p == 0)return M;
	    if(up){
	        if((p&1)==1 || tr[p^1] >= 0)return ind(p>>1, true);
	        return ind(p^1, false);
	    }else{
	        if(p >= M)return p;
	        if(tr[p<<1] == -1)return ind(p<<1, false);
	        return ind(p<<1|1, false);
	    }
	}
	class Tuple{
	    int x, y, z;
	    public Tuple(int X, int Y, int Z){
	        x = X;
	        y = Y;
	        z = Z;
	    }
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new HDDN().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

1 Like

It can have multiple solutions, right?

For eg.

Input:
1
6 2 2
1 2 3
2 2 4

Output:
1 2 1 2 1 1
OR
1 2 1 2 2 2
etc
1 Like

Nice editorial. Thanks for posting it.

For a long time, my solution was not getting AC and then I found this test case -

1
20 3 3
1 3 5
2 3 10
3 3 15

My program was saying the answer is ‘No’ but the expected answer is

Yes
1 1 2 2 1 3 3 1 1 2 1 1 1 1 3 1 1 1 1 1

  1. First, we will set A[Z[i]] = X[i] for all the M triplets.
  2. We will keep a vector of ‘expected frequency’ at all positions. EF[Z[i]] = Y[i]
  3. Then, we will go through the array elements, one by one.
  4. If the frequency of A[i] < Y[i], then we will put some more A[i] in the array just after the last occurence of A[i] so that no other A[i] is disturbed.
  5. Lastly, we will have to fill in the empty elements with any available element.

Here is my solution

1 Like

what s wrong with my code bro please explain
have a look on this

Coding Blocks IDE