Strict Permutation Codechef Problem Solution CoderCEO

Strict Permutation Codechef Problem Solution | STRPERM

You are given an integer $N$ . You have to find a permutation $P$ of the integers ${1, 2, \dots, 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}$ (i.e, $P_{K_{i}} = X_{i}$ ), then the condition $1 \leq K_{i} \leq Y_{i}$ must hold.

Print -1 if no such permutation exists. In case multiple permutations that satisfy all the conditions exist, find the lexicographically smallest one.

Note: If two arrays $A$ and $B$ have the same length $N$ , then $A$ is called 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},$ $\dots,$ $A_{i - 1} = B_{i - 1}, A_{i} < B_{i}$

Input Format

The first line of input will contain a single integer $T$ , denoting the number of test cases.
The first line of each test case contains two space-separated integers $N$ and $M$ – the length of permutation and the number of conditions to be satisfied respectively.
The next $M$ lines describe the conditions. The $i$ -th of these $M$ lines contains two space-separated integers $X_{i}$ and $Y_{i}$

Output Format

For each test case, output a single line containing the answer:

If no permutation satisfies the given conditions, print −1.
Otherwise, print $N$ space-separated integers, denoting the elements of the permutation. If there are multiple answers, output the lexicographically smallest one.

Constraints

$1 \leq T \leq 10^{5}$
$1 \leq N \leq 10^{5}$
$1 \leq M \leq N$
$1 \leq X_{i}, Y_{i} \leq N$
$X_{i} \neq X_{j}$ for each $1 \leq i < j \leq M$
$1 \leq i < j \leq M$ The sum of $N$ over all test cases won’t exceed $2 \cdot 10^{5}$

Sample Input 1

Sample Output 1

Explanation

Test case $1$ : The only permutation of length $3$ that satisfies all the conditions is $[2, 1, 3]$

Test case $2$ : There is no permutation of length $4$ that satisfies all the given conditions.

Test case $3$ : There are many permutations of length $4$ that satisfy all the conditions, such as $[1, 2, 3, 4], [1, 4, 2, 3], [1, 3, 2, 4], [2, 1, 4, 3], [2, 1, 3, 4]$ , etc. $[1, 2, 3, 4]$ is the lexicographically smallest among them.

				
					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;
}

Strict Permutation Codechef Problem Solution

Published by Govind Deshmukh on July 20, 2022July 20, 2022