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