[Solution] Strict Permutation solution codechef

Strict Permutation solution codechef – You are given an integer NN. You have to find a permutation PP of the integers {1,2,,N}{1,2,…,N} that satisfies MM conditions of the following form:

  • (Xi,Yi)(Xi,Yi), denoting that the element Xi(1XiN)Xi(1≤Xi≤N) must appear in the prefix of length YiYi. Formally, if the index of the element XiXi is KiKi (i.e, PKi=XiPKi=Xi), then the condition 1KiYi1≤Ki≤Yi must hold.

Table of Contents

[Solution] Strict Permutation solution codechef

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 AA and BB have the same length NN, then AA is called lexicographically smaller than BB only if there exists an index i(1iN)i(1≤i≤N) such that A1=B1,A1=B1, A2=B2,A2=B2, ,…, Ai1=Bi1,Ai<BiAi−1=Bi−1,Ai<Bi.

Input Format

  • The first line of input will contain a single integer TT, denoting the number of test cases.
  • The first line of each test case contains two space-separated integers NN and MM — the length of permutation and the number of conditions to be satisfied respectively.
  • The next MM lines describe the conditions. The ii-th of these MM lines contains two space-separated integers XiXi and YiYi.

Output Format

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

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

[Solution] Strict Permutation solution codechef

  • 1T1051≤T≤105
  • 1N1051≤N≤105
  • 1MN1≤M≤N
  • 1Xi,YiN1≤Xi,Yi≤N
  • XiXjXi≠Xj for each 1i<jM1≤i<j≤M.
  • The sum of NN over all test cases won’t exceed 21052⋅105.

Sample Input 1 

3 2
2 1
1 2
4 3
1 2
4 1
3 2
4 1
2 3
5 2
5 4
3 2

Sample Output 1 

2 1 3
1 2 3 4
1 3 2 5 4

[Solution] Strict Permutation solution codechef Explanation

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

Test case 22: There is no permutation of length 44 that satisfies all the given conditions.

Test case 33: There are many permutations of length 44 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][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][1,2,3,4] is the lexicographically smallest among them.

For Solution

Click Here

Leave a Comment