STRPERM - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Soumyadeep Pal
Tester: Takuki Kurokawa
Editorialist: Yash Kulkarni

DIFFICULTY:

2155

PREREQUISITES:

Heaps

PROBLEM:

You are given an integer N. You have to find a permutation of length N that satisfies M conditions of the following form:

  • (X_i, Y_i), denoting that the element X_i\;(1\leq X_i \leq N) must appear in the prefix of length Y_i. Formally, if the index of the element X_i is K_i, then the condition 1\le K_i \le Y_i must hold.

print -1 if no such permutation exists. In the case of multiple permutations, find the lexicographically smallest one.

If two arrays A and B have the same length N, then A is lexicographically smaller than B only if there exists an index i \; (1\leq i \leq N) such that A_1=B_1, A_2=B_2, \ldots, A_{i-1}=B_{i-1}, A_i \lt B_i.

EXPLANATION:

Hint

Try to construct the permutation from back to the front.

Solution

Using the M given conditions we can directly construct a list for each index containing all the elements which must appear at that index or before it. All the elements which don’t have any condition associated with them will appear in the list corresponding to index N. Let us call these collection of lists as V.

Since we want to construct the lexicographically smallest permutation, we can always fill the permutation from the back to the front, starting from the largest elements possible first. It is clear that at the last index (N) only the elements in V in the list corresponding to index N can appear. We will fill the last index with the largest element allowed. This greedy logic can be continued till the first index. We will maintain a priority queue which stores all the allowed elements at any point and this makes it possible to extract the largest element easily. We will keep on adding elements to this priority queue using V as we go from index N to 1.

At any point, if the priority queue is empty this means that there are no elements allowed at that index. This means that the permutation cannot constructed and the answer is -1.

TIME COMPLEXITY:

O(NlogN) for each test case.

SOLUTION:

Setter's solution
using namespace std;

void solve(int tc) {
  int n, m;
  cin >> n >> m;
  vector<int> last(n + 1, n);
  vector<vector<int>> v(n + 1);
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    last[x] = y;
  }
  for (int i = 1; i <= n; i++) {
    v[last[i]].push_back(i);
  }
  vector<int> ans(n + 1);
  priority_queue<int> pq;
  for (int i = n; i >= 1; i--) {
    for (auto &u : v[i]) {
      pq.push(u);
    }
    if (pq.empty()) {
      cout << "-1\n";
      return;
    }
    ans[i] = pq.top();
    pq.pop();
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << ' ';
  }
  cout << '\n';
}

int main() {
  ios_base :: sync_with_stdio(0); 
  cin.tie(0);
  int t = 1;
  cin >> t;
  for (int i = 1; i <= t; i++) solve(i);
  return 0;
}
Editorialist's Solution
using namespace std;

int main() {
	int T;
	cin >> T;
	while(T--){
	    int n,m;
	    cin >> n >> m;
	    vector<int>v[n+1];
	    unordered_map<int,int>ff;
	    for(int i=0;i<m;i++){
	        int x,y;
	        cin >> x >> y;
	        v[y].push_back(x);
	        ff[x]++;
	    }
	    for(int i=1;i<=n;i++){
	        if(ff[i])continue;
	        v[n].push_back(i);
	    }
	    vector<int>ans;
	    priority_queue<int>pq;
	    for(int i=n;i>=1;i--){
	        for(auto j:v[i])pq.push(j);
	        if(pq.empty()){
	            cout << -1 << endl;
	            break;
	        }
	        ans.push_back(pq.top());
	        pq.pop();
	    }
	    if(ans.size()<n)continue;
	    for(int i=0;i<n;i++)cout << ans[n-i-1] << " ";
	    cout << endl;
	}
	return 0;
}
2 Likes

Why am I getting runtime error for all my submissions, I have been trying to figure it out for hours now, pls help

#include<bits/stdc++.h>
using namespace std;
bool comp(pair<int,int>&x,pair<int,int>&y)
{
	if(x.second<=y.second)
		return 1;
	return 0;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		vector<pair<int,int>>arr(n,{0,0});
		for(int i=0;i<n;i++)
		{
			arr[i].first = i+1;
			arr[i].second = n;
		}
		for(int i=0;i<m;i++)
		{
			int x,y;
			cin>>x>>y;
			arr[x-1].second = y;
		}
		sort(arr.begin(),arr.end(),comp);
		priority_queue<int>q;
		vector<int>res(n,0);
		int cur = n;
		int j = n-1;
		bool f = 0;
		for(int i=n-1;i>=0;i--)
		{
			while(j>=0 && arr[j].second==cur)
			{
				q.push(arr[j].first);
				j--;
			}
			if(q.empty())
				f = 1;
			else
			{
				res[--cur] = q.top();
				q.pop();
			}
		}
		if(f)
			cout<<-1<<endl;
		else
		{
		for(int i=0;i<n;i++)
			cout<<res[i]<<" ";
		cout<<endl;
		}
	}
}

Java TreeSet solution

//package kg.my_algorithms.codechef;

import java.io.*;
import java.util.*;

public class Main {
    private static int k;
    public static void main(String[] args) throws IOException {
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
        FastReader fastReader = new FastReader();
        int test_cases = fastReader.nextInt();
        StringBuilder sb = new StringBuilder();
        for(int test=1;test<=test_cases;test++) {
            int n = fastReader.nextInt();
            int m = fastReader.nextInt();
            int[] conditions = new int[n];
            Arrays.fill(conditions,n-1);
            for(int i=0;i<m;i++) conditions[fastReader.nextInt()-1] = fastReader.nextInt()-1;
            sb.append(fun(n,conditions));
        }
        output.write(sb.toString());
        output.flush();
    }
    private static StringBuilder fun(int n, int[] conditions){
        TreeSet<Integer> setOfIndices = new TreeSet<>();
        for(int i=0;i<n;i++) setOfIndices.add(i);
        int[] answer = new int[n];
        for(int num=n-1;num>=0;num--){
            Integer indexInteger = setOfIndices.floor(conditions[num]);
            if(indexInteger==null) return new StringBuilder("-1\n");
            int index = indexInteger;
            answer[index] = num;
            setOfIndices.remove(index);
        }
        StringBuilder sb = new StringBuilder();
        for(int a: answer) sb.append(a+1).append(" ");
        return sb.append("\n");
    }
}
class FastReader {
    BufferedReader br;
    StringTokenizer st;

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

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

    int nextInt() { return Integer.parseInt(next()); }

    long nextLong() { return Long.parseLong(next()); }

    double nextDouble()
    {
        return Double.parseDouble(next());
    }

    String nextLine()
    {
        String str = "";
        try {
            if(st.hasMoreTokens()){
                str = st.nextToken("\n");
            }
            else{
                str = br.readLine();
            }
        }
        catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

why i am getting runtime error please anyone can help me to solve this?

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t>0)
{
int N=sc.nextInt();
int M=sc.nextInt();
PriorityQueue pq=new PriorityQueue(Collections.reverseOrder());
for(int i=1;i<=N;i++){
pq.add(i);
}
boolean poss=true;
int[] arr=new int[N];
for(int i=0;i<M;i++){
int x,y;
x=sc.nextInt();
y=sc.nextInt();
if(arr[y-1]==0){
arr[y-1]=x;
}
else{
poss=false;
break;
}
pq.remove(x);
}
if(poss){
int k=N-1;
boolean flag=true;
while(k>=0){
if(pq.isEmpty()){
flag=false;
break;
}
pq.add(arr[k]);
int z=pq.poll();
arr[k]=z;
k–;
}
if(flag){

		        for(int nm:arr){
		            System.out.print(nm);
		        }
		        System.out.println();
		    }
		    else{
		        System.out.println(-1);
		    } 
	    }
	   else{
	       System.out.println(-1);
	   }
	    t--;
	}
}

}

1 Like

can you please explain your approach ?