Trilogy innovations conducted online assesment for role of SDE intern on 6 August 2023. Below are my understandings and solutions for the questions in their online assesment.↵
↵
You can refer to [this](https://codeforces.net/blog/entry/119105) blog for the questions.↵
↵
####Problem B. Is It Possible↵
↵
<spoiler summary="Problem Statment">↵
There are A number of days in a year. And you have to perform some type of work↵
in a year. There are M types of work to be performed. And you are given a 2D array ↵
B of size M which represents the description for the different types of work.↵
↵
B[i][0] means the day on which the ith work is given.↵
B[i][1] means the ith work must be completed before this day.↵
B[i][2] denotes the number of days it will take to complete ith work.↵
↵
Now, on any day, one of these three things can be done — ↵
1. Rest day↵
2. This is the deadline date for any work (i.e B[i][1]) (nothing can be done on this day)↵
3. You are performing any one work↵
↵
If in case you cannot perform all work before the deadline return a vector of size 1↵
which is [-1]↵
Else return a vector of size A + 1 whose first element is — 1 and the↵
- ith element is 0 if it is a rest day.↵
- ith elment is M + 1 if this day is a deadline for any type of work.↵
- if any type of work is performed on this day then the ith element will be the type of ↵
that work. (Types are starting from 1 to m)↵
↵
Note — On any day there will be a deadline for a most 1 type of work. If more than↵
one type of work can be performed on any day then perform the one having a deadline↵
first.↵
↵
Problem Constraints: ↵
2 <= A <= 100↵
1 <= M <= A↵
1 <= B[i][0] <= B[i][1] <= A↵
1 <= B[i][2] <= A↵
</spoiler>↵
↵
↵
<spoiler summary="Solution Idea">↵
The basic idea of my solution is to follow a greedy approach and just try to implement what is given. ↵
First marks all the days that are deadlines to certain work with M + 1. They cannot be used anywhere.↵
Then store iterate from day 1 to A. Maintain a minimum priority queue of works that can be done on this day. That is works that have start day on or before this day.↵
Now take the day with smallest deadline(as given in the question) and remove it from priority queue and assign day to this work. Decrease this days duration and if it's still greater than 0 push it back into priority queue.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
//#pragma GCC optimize("Ofast,unroll-loops") ↵
//#pragma GCC target("avx,avx2,avx512,fma") ↵
↵
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }↵
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }↵
void dbg_out() { cerr << endl; }↵
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }↵
#ifdef LOCAL↵
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)↵
#else↵
#define dbg(...)↵
#endif↵
↵
#define ll long long↵
#define ld long double↵
↵
#define PI 3.1415926535897932384626433832795l ↵
↵
// -------------------------<rng>------------------------- ↵
// RANDOM NUMBER GENERATOR↵
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); ↵
#define SHUF(v) shuffle(all(v), RNG); ↵
// Use mt19937_64 for 64 bit random numbers.↵
↵
↵
#define pii pair<int, int>↵
vector<int> solve(int A, vector<vector<int>> &b){↵
int m = b.size();↵
vector<int> start(m + 1), end(m + 1), dur(m + 1);↵
for(int i = 0; i < m; ++i){↵
start[i + 1] = b[i][0];↵
end[i + 1] = b[i][1];↵
dur[i + 1] = b[i][2];↵
}↵
priority_queue<pii, vector<pii>, greater<pii>> pqs, pqe;↵
for(int i = 1; i <= m; ++i){↵
pqs.push({start[i], i});↵
}↵
vector<int> ans(A + 1);↵
ans[0] = -1;↵
bool isPossible = true;↵
for(int day = 1; day <= A; ++day){↵
while(!pqs.empty() && (pqs.top().first <= day)){↵
int id, _;↵
tie(_, id) = pqs.top();↵
pqs.pop();↵
pqe.push({end[id], id});↵
}↵
if(ans[day] == m + 1){↵
continue;↵
}↵
if(!pqe.empty()){↵
int id, _;↵
tie(_, id) = pqe.top();↵
pqe.pop();↵
ans[day] = id;↵
if(end[id] < day){↵
isPossible = false;↵
break;↵
}↵
--dur[id];↵
if(dur[id] != 0){↵
pqe.push({end[id], id});↵
}↵
}↵
}↵
if(!pqe.empty() || !pqs.empty()){↵
isPossible = false;↵
}↵
if(!isPossible){↵
ans.assign(1, -1);↵
}↵
return ans;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0); cout.tie(0);↵
↵
int A, M;↵
cin >> A >> M;↵
vector<vector<int>> B(M, vector<int>(3));↵
for(int i = 0; i < M; ++i){↵
cin >> B[i][0] >> B[i][1] >> B[i][2];↵
}↵
for(int elem : solve(A, B)){↵
cout << elem << ' ';↵
}↵
cout << '\n';↵
↵
return 0;↵
}↵
↵
↵
~~~~~↵
</spoiler>↵
↵
↵
↵
#### Problem C Change Permutation↵
↵
<spoiler summary="Problem Statement">↵
You are given an integer A and an integer array B, which is the permutation of A↵
integers.↵
Now, you have to perform some swap poerations on this permutation B.↵
Now, after this swap operation B should be such that it can be made to identity ↵
permutation by exactly C swaps (which is minimum required)↵
↵
You have to return a 2D array D which denotes the minimum swaaps you have to ↵
perform so that B will become identity after exactly C swaps.↵
D[i][0] adn D[i][1] deontes the index of swap operation you are performing. ↵
Return the lexicographically smallest array D.↵
↵
If you don't need to perform any swap operation then return D = [[-1, -1]]↵
↵
Note — Identity permutation is a permutation where B[i] = i, for each 1 <= i <= A↵
↵
Problem Constraints:↵
1 <= A <= 3000↵
0 <= C < A↵
</spoiler>↵
↵
↵
<spoiler summary="Solution Idea">↵
Please go through this [blog](https://codeforces.net/blog/entry/111187) before continuing if you are new to permutations.↵
The basic idea is that since we want a permutation that can be transformed to identity in exactly C transformations at minimum, then that permutation must have exactly N — C cycles, where N is size of the permutation. ↵
Let r = N — C = required number of cycles.↵
and nc = number of cycles in the given permutation↵
↵
Now there are two cases:↵
↵
↵
**Case 1** : nc >= r↵
In this case we need to merge cycles till we get exactly r cycles. Each merge reduces number of cycles by 1 so we must perform nc — r merges. Now each merge can be performed by swapping two elements in different cycles.↵
What we do is we take the minimum element in each cycle as it's head. Then we swap the two smalles heads for each of teh nc — r merges and remove the second smallest head. I have used priority_queue for this. However it's also possible to do this by simply sorting an array of heads.↵
↵
↵
**Case 2**: nc < r↵
In this case we have to split cycles till we get exactly r cycles. How do we split a cycle ? By swapping two elements in that cycle.↵
↵
↵
To split a cycle, we perform swaps between two elements within the cycle. This splitting process continues until each cycle contains a single element.↵
↵
↵
The key challenge here is to ensure the swaps are performed in a way that generates a lexicographically smallest array of swaps D.↵
↵
↵
To achieve this, we aim to minimize the value of the first element in each cycle, which leads to a lexicographically smaller result.↵
↵
↵
We repeatedly swap the minimum and second minimum elements within a cycle to achieve this goal.↵
Finally we sort the array of swaps and take the first r — nc swaps because we wish to perform only r — nc merges.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
//#pragma GCC optimize("Ofast,unroll-loops") ↵
//#pragma GCC target("avx,avx2,avx512,fma") ↵
↵
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }↵
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }↵
void dbg_out() { cerr << endl; }↵
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }↵
#ifdef LOCAL↵
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)↵
#else↵
#define dbg(...)↵
#endif↵
↵
#define ll long long↵
#define ld long double↵
↵
#define PI 3.1415926535897932384626433832795l ↵
↵
// -------------------------<rng>------------------------- ↵
// RANDOM NUMBER GENERATOR↵
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); ↵
#define SHUF(v) shuffle(all(v), RNG); ↵
// Use mt19937_64 for 64 bit random numbers.↵
↵
vector<vector<int>> getCycles(vector<int> &p){↵
int n = p.size();↵
vector<bool> vis(n);↵
vector<int> ind(n);↵
↵
for(int i = 0; i < n; ++i){↵
--p[i];↵
ind[p[i]] = i;↵
}↵
↵
vector<vector<int>> cycles;↵
for(int i = 0; i < n; ++i){↵
if(vis[i]){↵
continue;↵
}↵
int cur = i;↵
vector<int> c;↵
while(!vis[cur]){↵
vis[cur] = true;↵
c.push_back(cur);↵
cur = ind[cur];↵
}↵
cycles.push_back(c);↵
}↵
for(auto &c : cycles){↵
for(auto &ind : c){↵
++ind;↵
}↵
}↵
return cycles;↵
}↵
↵
vector<vector<int>> solve(vector<int> &p, int k) {↵
int n = p.size();↵
vector<vector<int>> ans;↵
// all cycles cycles↵
vector<vector<int>> cycles = getCycles(p);↵
↵
// req cycles↵
int req_cycles = n - k;↵
int no_cycles = cycles.size();↵
if(req_cycles < no_cycles){↵
ll diff = cycles.size() - req_cycles;↵
priority_queue<int, vector<int>, greater<int>> pq;↵
for(auto c : cycles){↵
pq.push(c.front());↵
}↵
while(diff--){↵
int u = pq.top();↵
pq.pop();↵
int v = pq.top();↵
pq.pop();↵
ans.push_back({u, v});↵
pq.push(u);↵
}↵
}↵
else if(req_cycles > no_cycles){↵
while(!cycles.empty()){↵
vector<int> c = cycles.back();↵
cycles.pop_back();↵
if(c.size() == 1){↵
continue;↵
}↵
if(c.size() == 2){↵
ans.push_back({c[0], c[1]});↵
continue;↵
}↵
int mn_ind = min_element(c.begin() + 1, c.end()) - c.begin();↵
ans.push_back({c[0], c[mn_ind]});↵
vector<int> c1, c2;↵
c1.push_back(c[0]);↵
for(int i = mn_ind + 1; i < no_cycles; ++i){↵
c1.push_back(c[i]);↵
}↵
c2.push_back(c[mn_ind]);↵
for(int i = 1; i < mn_ind; ++i){↵
c2.push_back(c[i]);↵
}↵
cycles.push_back(c1);↵
cycles.push_back(c2);↵
}↵
int diff = req_cycles - no_cycles;↵
sort(ans.begin(), ans.end());↵
ans.resize(diff);↵
}↵
if(ans.empty()){↵
ans = {{-1, -1}};↵
}↵
return ans;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0); cout.tie(0);↵
↵
int n, k;↵
cin >> n >> k;↵
vector<int> p(n);↵
for(int i = 0; i < n; ++i){↵
cin >> p[i];↵
}↵
for(auto v : solve(p, k)){↵
cout << v[0] << ' ' << v[1] << '\n';↵
}↵
↵
return 0;↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
#### Problem D Segment Points↵
↵
<spoiler summary="Problem Statement">↵
You are given an 2D array A which indicates |A| segments covered.↵
ith segment cover integer points from A[i][0] to A[i][1] inclusive.↵
↵
Now, your task is to find the number of integer points that are covered by↵
exactly i number of segments for each 1 <= i <= |A|.↵
↵
Return an arrray B of size |A| + 1, where B[i] denotes the number of integer points that↵
are covered by exactly i segments.↵
↵
Note: B[0] must be equal to 0.↵
↵
Problem Constraints↵
1 <= |A| <= 2 * (10 ** 5)↵
0 <= A[i][0] <= A[i][1] <= 10 ** 18↵
</spoiler>↵
↵
↵
<spoiler summary="Solution Idea">↵
This is a bit of modified version of the prefix sum solution which would work for r <= 10**5. ↵
Other solutions using sweepline algorithms not requiring maps also exist.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
//#pragma GCC optimize("Ofast,unroll-loops") ↵
//#pragma GCC target("avx,avx2,avx512,fma") ↵
↵
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }↵
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }↵
void dbg_out() { cerr << endl; }↵
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }↵
#ifdef LOCAL↵
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)↵
#else↵
#define dbg(...)↵
#endif↵
↵
#define ll long long↵
#define ld long double↵
↵
#define PI 3.1415926535897932384626433832795l ↵
↵
// -------------------------<rng>------------------------- ↵
// RANDOM NUMBER GENERATOR↵
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); ↵
#define SHUF(v) shuffle(all(v), RNG); ↵
// Use mt19937_64 for 64 bit random numbers.↵
↵
↵
vector<ll> solve(vector<vector<ll>> &a) {↵
int n = a.size();↵
vector<ll> ans(n + 1);↵
map<ll, ll> points;↵
↵
for(auto &v : a){↵
ll l = v[0], r = v[1];↵
++points[l];↵
--points[r + 1];↵
}↵
ll cur_points = 0;↵
ll prev_ind = -1;↵
for(auto [ind, p] : points){↵
if(cur_points > 0){↵
ans[cur_points] += ind - prev_ind;↵
}↵
prev_ind = ind;↵
cur_points += p;↵
}↵
return ans;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0); cout.tie(0);↵
int n;↵
cin >> n;↵
vector<vector<ll>> a(n);↵
for(int i = 0; i < n; ++i){↵
ll l, r;↵
cin >> l >> r;↵
a[i] = {l, r};↵
}↵
for(auto u : solve(a)){↵
cout << u << ' ';↵
}↵
↵
return 0;↵
}↵
↵
↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
Please do comment if you find any errors in the logic or implementation.
↵
You can refer to [this](https://codeforces.net/blog/entry/119105) blog for the questions.↵
↵
####Problem B. Is It Possible↵
↵
<spoiler summary="Problem Statment">↵
There are A number of days in a year. And you have to perform some type of work↵
in a year. There are M types of work to be performed. And you are given a 2D array ↵
B of size M which represents the description for the different types of work.↵
↵
B[i][0] means the day on which the ith work is given.↵
B[i][1] means the ith work must be completed before this day.↵
B[i][2] denotes the number of days it will take to complete ith work.↵
↵
Now, on any day, one of these three things can be done — ↵
1. Rest day↵
2. This is the deadline date for any work (i.e B[i][1]) (nothing can be done on this day)↵
3. You are performing any one work↵
↵
If in case you cannot perform all work before the deadline return a vector of size 1↵
which is [-1]↵
Else return a vector of size A + 1 whose first element is — 1 and the↵
- ith element is 0 if it is a rest day.↵
- ith elment is M + 1 if this day is a deadline for any type of work.↵
- if any type of work is performed on this day then the ith element will be the type of ↵
that work. (Types are starting from 1 to m)↵
↵
Note — On any day there will be a deadline for a most 1 type of work. If more than↵
one type of work can be performed on any day then perform the one having a deadline↵
first.↵
↵
Problem Constraints: ↵
2 <= A <= 100↵
1 <= M <= A↵
1 <= B[i][0] <= B[i][1] <= A↵
1 <= B[i][2] <= A↵
</spoiler>↵
↵
↵
<spoiler summary="Solution Idea">↵
The basic idea of my solution is to follow a greedy approach and just try to implement what is given. ↵
First marks all the days that are deadlines to certain work with M + 1. They cannot be used anywhere.↵
Then store iterate from day 1 to A. Maintain a minimum priority queue of works that can be done on this day. That is works that have start day on or before this day.↵
Now take the day with smallest deadline(as given in the question) and remove it from priority queue and assign day to this work. Decrease this days duration and if it's still greater than 0 push it back into priority queue.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
//#pragma GCC optimize("Ofast,unroll-loops") ↵
//#pragma GCC target("avx,avx2,avx512,fma") ↵
↵
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }↵
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }↵
void dbg_out() { cerr << endl; }↵
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }↵
#ifdef LOCAL↵
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)↵
#else↵
#define dbg(...)↵
#endif↵
↵
#define ll long long↵
#define ld long double↵
↵
#define PI 3.1415926535897932384626433832795l ↵
↵
// -------------------------<rng>------------------------- ↵
// RANDOM NUMBER GENERATOR↵
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); ↵
#define SHUF(v) shuffle(all(v), RNG); ↵
// Use mt19937_64 for 64 bit random numbers.↵
↵
↵
#define pii pair<int, int>↵
vector<int> solve(int A, vector<vector<int>> &b){↵
int m = b.size();↵
vector<int> start(m + 1), end(m + 1), dur(m + 1);↵
for(int i = 0; i < m; ++i){↵
start[i + 1] = b[i][0];↵
end[i + 1] = b[i][1];↵
dur[i + 1] = b[i][2];↵
}↵
priority_queue<pii, vector<pii>, greater<pii>> pqs, pqe;↵
for(int i = 1; i <= m; ++i){↵
pqs.push({start[i], i});↵
}↵
vector<int> ans(A + 1);↵
ans[0] = -1;↵
bool isPossible = true;↵
for(int day = 1; day <= A; ++day){↵
while(!pqs.empty() && (pqs.top().first <= day)){↵
int id, _;↵
tie(_, id) = pqs.top();↵
pqs.pop();↵
pqe.push({end[id], id});↵
}↵
if(ans[day] == m + 1){↵
continue;↵
}↵
if(!pqe.empty()){↵
int id, _;↵
tie(_, id) = pqe.top();↵
pqe.pop();↵
ans[day] = id;↵
if(end[id] < day){↵
isPossible = false;↵
break;↵
}↵
--dur[id];↵
if(dur[id] != 0){↵
pqe.push({end[id], id});↵
}↵
}↵
}↵
if(!pqe.empty() || !pqs.empty()){↵
isPossible = false;↵
}↵
if(!isPossible){↵
ans.assign(1, -1);↵
}↵
return ans;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0); cout.tie(0);↵
↵
int A, M;↵
cin >> A >> M;↵
vector<vector<int>> B(M, vector<int>(3));↵
for(int i = 0; i < M; ++i){↵
cin >> B[i][0] >> B[i][1] >> B[i][2];↵
}↵
for(int elem : solve(A, B)){↵
cout << elem << ' ';↵
}↵
cout << '\n';↵
↵
return 0;↵
}↵
↵
↵
~~~~~↵
</spoiler>↵
↵
↵
↵
#### Problem C Change Permutation↵
↵
<spoiler summary="Problem Statement">↵
You are given an integer A and an integer array B, which is the permutation of A↵
integers.↵
Now, you have to perform some swap poerations on this permutation B.↵
Now, after this swap operation B should be such that it can be made to identity ↵
permutation by exactly C swaps (which is minimum required)↵
↵
You have to return a 2D array D which denotes the minimum swaaps you have to ↵
perform so that B will become identity after exactly C swaps.↵
D[i][0] adn D[i][1] deontes the index of swap operation you are performing. ↵
Return the lexicographically smallest array D.↵
↵
If you don't need to perform any swap operation then return D = [[-1, -1]]↵
↵
Note — Identity permutation is a permutation where B[i] = i, for each 1 <= i <= A↵
↵
Problem Constraints:↵
1 <= A <= 3000↵
0 <= C < A↵
</spoiler>↵
↵
↵
<spoiler summary="Solution Idea">↵
Please go through this [blog](https://codeforces.net/blog/entry/111187) before continuing if you are new to permutations.↵
The basic idea is that since we want a permutation that can be transformed to identity in exactly C transformations at minimum, then that permutation must have exactly N — C cycles, where N is size of the permutation. ↵
Let r = N — C = required number of cycles.↵
and nc = number of cycles in the given permutation↵
↵
Now there are two cases:↵
↵
↵
**Case 1** : nc >= r↵
In this case we need to merge cycles till we get exactly r cycles. Each merge reduces number of cycles by 1 so we must perform nc — r merges. Now each merge can be performed by swapping two elements in different cycles.↵
What we do is we take the minimum element in each cycle as it's head. Then we swap the two smalles heads for each of teh nc — r merges and remove the second smallest head. I have used priority_queue for this. However it's also possible to do this by simply sorting an array of heads.↵
↵
↵
**Case 2**: nc < r↵
In this case we have to split cycles till we get exactly r cycles. How do we split a cycle ? By swapping two elements in that cycle.↵
↵
↵
To split a cycle, we perform swaps between two elements within the cycle. This splitting process continues until each cycle contains a single element.↵
↵
↵
The key challenge here is to ensure the swaps are performed in a way that generates a lexicographically smallest array of swaps D.↵
↵
↵
To achieve this, we aim to minimize the value of the first element in each cycle, which leads to a lexicographically smaller result.↵
↵
↵
We repeatedly swap the minimum and second minimum elements within a cycle to achieve this goal.↵
Finally we sort the array of swaps and take the first r — nc swaps because we wish to perform only r — nc merges.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
//#pragma GCC optimize("Ofast,unroll-loops") ↵
//#pragma GCC target("avx,avx2,avx512,fma") ↵
↵
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }↵
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }↵
void dbg_out() { cerr << endl; }↵
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }↵
#ifdef LOCAL↵
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)↵
#else↵
#define dbg(...)↵
#endif↵
↵
#define ll long long↵
#define ld long double↵
↵
#define PI 3.1415926535897932384626433832795l ↵
↵
// -------------------------<rng>------------------------- ↵
// RANDOM NUMBER GENERATOR↵
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); ↵
#define SHUF(v) shuffle(all(v), RNG); ↵
// Use mt19937_64 for 64 bit random numbers.↵
↵
vector<vector<int>> getCycles(vector<int> &p){↵
int n = p.size();↵
vector<bool> vis(n);↵
vector<int> ind(n);↵
↵
for(int i = 0; i < n; ++i){↵
--p[i];↵
ind[p[i]] = i;↵
}↵
↵
vector<vector<int>> cycles;↵
for(int i = 0; i < n; ++i){↵
if(vis[i]){↵
continue;↵
}↵
int cur = i;↵
vector<int> c;↵
while(!vis[cur]){↵
vis[cur] = true;↵
c.push_back(cur);↵
cur = ind[cur];↵
}↵
cycles.push_back(c);↵
}↵
for(auto &c : cycles){↵
for(auto &ind : c){↵
++ind;↵
}↵
}↵
return cycles;↵
}↵
↵
vector<vector<int>> solve(vector<int> &p, int k) {↵
int n = p.size();↵
vector<vector<int>> ans;↵
// all cycles cycles↵
vector<vector<int>> cycles = getCycles(p);↵
↵
// req cycles↵
int req_cycles = n - k;↵
int no_cycles = cycles.size();↵
if(req_cycles < no_cycles){↵
ll diff = cycles.size() - req_cycles;↵
priority_queue<int, vector<int>, greater<int>> pq;↵
for(auto c : cycles){↵
pq.push(c.front());↵
}↵
while(diff--){↵
int u = pq.top();↵
pq.pop();↵
int v = pq.top();↵
pq.pop();↵
ans.push_back({u, v});↵
pq.push(u);↵
}↵
}↵
else if(req_cycles > no_cycles){↵
while(!cycles.empty()){↵
vector<int> c = cycles.back();↵
cycles.pop_back();↵
if(c.size() == 1){↵
continue;↵
}↵
if(c.size() == 2){↵
ans.push_back({c[0], c[1]});↵
continue;↵
}↵
int mn_ind = min_element(c.begin() + 1, c.end()) - c.begin();↵
ans.push_back({c[0], c[mn_ind]});↵
vector<int> c1, c2;↵
c1.push_back(c[0]);↵
for(int i = mn_ind + 1; i < no_cycles; ++i){↵
c1.push_back(c[i]);↵
}↵
c2.push_back(c[mn_ind]);↵
for(int i = 1; i < mn_ind; ++i){↵
c2.push_back(c[i]);↵
}↵
cycles.push_back(c1);↵
cycles.push_back(c2);↵
}↵
int diff = req_cycles - no_cycles;↵
sort(ans.begin(), ans.end());↵
ans.resize(diff);↵
}↵
if(ans.empty()){↵
ans = {{-1, -1}};↵
}↵
return ans;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0); cout.tie(0);↵
↵
int n, k;↵
cin >> n >> k;↵
vector<int> p(n);↵
for(int i = 0; i < n; ++i){↵
cin >> p[i];↵
}↵
for(auto v : solve(p, k)){↵
cout << v[0] << ' ' << v[1] << '\n';↵
}↵
↵
return 0;↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
#### Problem D Segment Points↵
↵
<spoiler summary="Problem Statement">↵
You are given an 2D array A which indicates |A| segments covered.↵
ith segment cover integer points from A[i][0] to A[i][1] inclusive.↵
↵
Now, your task is to find the number of integer points that are covered by↵
exactly i number of segments for each 1 <= i <= |A|.↵
↵
Return an arrray B of size |A| + 1, where B[i] denotes the number of integer points that↵
are covered by exactly i segments.↵
↵
Note: B[0] must be equal to 0.↵
↵
Problem Constraints↵
1 <= |A| <= 2 * (10 ** 5)↵
0 <= A[i][0] <= A[i][1] <= 10 ** 18↵
</spoiler>↵
↵
↵
<spoiler summary="Solution Idea">↵
This is a bit of modified version of the prefix sum solution which would work for r <= 10**5. ↵
Other solutions using sweepline algorithms not requiring maps also exist.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
//#pragma GCC optimize("Ofast,unroll-loops") ↵
//#pragma GCC target("avx,avx2,avx512,fma") ↵
↵
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }↵
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }↵
void dbg_out() { cerr << endl; }↵
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }↵
#ifdef LOCAL↵
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)↵
#else↵
#define dbg(...)↵
#endif↵
↵
#define ll long long↵
#define ld long double↵
↵
#define PI 3.1415926535897932384626433832795l ↵
↵
// -------------------------<rng>------------------------- ↵
// RANDOM NUMBER GENERATOR↵
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); ↵
#define SHUF(v) shuffle(all(v), RNG); ↵
// Use mt19937_64 for 64 bit random numbers.↵
↵
↵
vector<ll> solve(vector<vector<ll>> &a) {↵
int n = a.size();↵
vector<ll> ans(n + 1);↵
map<ll, ll> points;↵
↵
for(auto &v : a){↵
ll l = v[0], r = v[1];↵
++points[l];↵
--points[r + 1];↵
}↵
ll cur_points = 0;↵
ll prev_ind = -1;↵
for(auto [ind, p] : points){↵
if(cur_points > 0){↵
ans[cur_points] += ind - prev_ind;↵
}↵
prev_ind = ind;↵
cur_points += p;↵
}↵
return ans;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0); cout.tie(0);↵
int n;↵
cin >> n;↵
vector<vector<ll>> a(n);↵
for(int i = 0; i < n; ++i){↵
ll l, r;↵
cin >> l >> r;↵
a[i] = {l, r};↵
}↵
for(auto u : solve(a)){↵
cout << u << ' ';↵
}↵
↵
return 0;↵
}↵
↵
↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
Please do comment if you find any errors in the logic or implementation.
