PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Pavel Shishikhin
Tester: Rahul Dugar
Editorialist: Aman Dwivedi
DIFFICULTY:
Medium
PREREQUISITES:
Hashing, Difference Array
PROBLEM:
You have N cells numbered from 1 to N, each cell contains a single Chef.
You are given Q queries, k-th query contains two integers L_k, R_k (1 \le L_k \le R_k \le n), after that query for each L_k \le i \le R_k a Chef goes from cell i to cell a_i.
After every query, each cell should contain exactly one Chef.
You are also given an integer p such that:
-
If p = 0 you should find a lexicographically minimal array a_1, a_2, \dots, a_n so that the above-mentioned condition is met.
-
If p = 1 you should find a lexicographically maximal array a_1, a_2, \dots, a_n so that the above-mentioned condition is met.
EXPLANATION:
Subtask 1:
Here p=0, that means we need to find a lexicographically minimal array a_1, a_2, \dots, a_n such that above condition is met.
The answer is simple, If a cell is covered by at least 1 query then A_i=i, otherwise A_i=1.
Why ?
- If the cell is not covered by any query, it means the Chef on this cell will never move. Hence, if we assign any number to this cell say X, then Chef won’t be going to cell X ever. As we need to find a lexicographically minimum sequence, so the minimum possible value that can be assigned to this cell will be 1.
Suppose that [L, L+1,\dots, R] are the cells that are governed by the same set of queries. Now, what is the minimum value that can be assigned to cell A_L? Let’s try some values for A_L:
Case: L=X, such that X is less than L (possibly 1).
- In this case, the Chef on cell L will move to cell X. But the Chef on cell X won’t be able to move in some cases as index L and X are not governed by the same set of queries. Hence ending up with more than one Chef on cell X, which violates our condition.
As now L cannot be assigned value less than L, now what is the minimum value that can be assigned to cell L i.e L itself.
Hence If a cell is covered by at least 1 query then A_i=i, otherwise A_i=1.
Now we are only left with finding the cells that are covered by at least one query that can be easily found with the help of the Difference Array.
Time Complexity
O(N+Q) per test case
Solution
// Subtask 1
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t,p;
cin>>t>>p;
while(t--)
{
int n,q;
cin>>n>>q;
int hash[n+2]={};
while(q--)
{
int l,r;
cin>>l>>r;
hash[l]+=1;
hash[r+1]-=1;
}
for(int i=1;i<=n;i++)
{
hash[i]+=hash[i-1];
if(hash[i]==0)
cout<<1<<" ";
else
cout<<i<<" ";
}
cout<<"\n";
}
return 0;
}
Subtask 2:
Here p = 1, 1 \le N \le 10^3, 1 \le Q \le 10^3, sum of N and sum of Q over all test cases does not exceed 10^3
Case 1: If the cell is not at all covered by any query.
- Since the cell is not covered by any query, it means that the Chef on this cell will never move. Hence, if we assign any number to this cell say X, then Chef won’t be going to cell X ever. As we need to find a lexicographically maximum sequence, so the maximum possible value that can be assigned to this cell will be N.
Case 2: Otherwise,
-
Let’s consider cells with indexes b[1], b[2],..., b[k] that are covered by the same set of queries. As we need to find the lexicographically maximal sequence, hence we need to assign b[1] the maximum possible value. We can’t assign values more than b[k] to b[1], it is a similar case when we were trying to assign values less than L in Subtask 1.
-
The maximum value that can be assigned to b[1] is b[k]. Similarly, for b[2], it will be b[k-1] and so on. Hence, the answer will be [b[k]] = b[1], a[b[k-1]] = b[2],\dots, a[b[2]] = b[k-1], a[b[1]] = b[k] i.e we reverse these cells.
To understand which cells are covered by the same set of queries. Let S=[Q_1, Q_2,\dots, Q_i] be the set of queries. Then all the cells that are governed by this set of queries S will be mapped with S. We can directly use set of queries as our map key.
As soon as we knew about the indexes which are covered by the same set of queries. All we need to do is to reverse those indices in our answer.
Time Complexity
O(N*Q) per test case
Solution
// Subtask 1 and 2
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t,p;
cin>>t>>p;
while(t--)
{
int n,q;
cin>>n>>q;
int hash[n+2]={};
int l[q+2],r[q+2];
for(int i=1;i<=q;i++)
{
cin>>l[i]>>r[i];
hash[l[i]]+=1;
hash[r[i]+1]-=1;
}
if(p==0)
{
for(int i=1;i<=n;i++)
{
hash[i]+=hash[i-1];
if(hash[i]==0)
cout<<1<<" ";
else
cout<<i<<" ";
}
cout<<"\n";
}
else
{
vector <int> adj[n+2];
for(int i=1;i<=q;i++)
{
for(int j=l[i];j<=r[i];j++)
{
adj[j].push_back(i);
}
}
map <vector<int>,vector<int>> m1;
for(int i=1;i<=n;i++)
{
m1[adj[i]].push_back(i);
}
for(int i=1;i<=n;i++)
{
if(adj[i].size()==0)
cout<<n<<" ";
else
{
cout<<m1[adj[i]].back()<<" ";
m1[adj[i]].pop_back();
}
}
cout<<"\n";
}
}
return 0;
}
Subtask 3:
Since the value of N and Q are large enough, so we are unable to iterate over all possible values of N for every query.
So, to optimize it and understand which cells are covered by the same set of queries, instead of using set of queries as the map key, we will use the hashed value of queries as the map key. To optimize it further we will use Difference Array for finding out the hashed value of queries for any cell i of an array.
Hashing
One of the ways to calculate the hashed value is using the polynomial rolling hash function technique.
Let us suppose that, the cell X is governed by some queries [Q_1, Q_3, Q_7,\dots, Q_i] such that queries are in increasing order. Then the hashed value of queries for index X will be:
hash(X)=Q_1.z+Q_3⋅z^3+Q_7⋅z^7+...+Q_i⋅z^i \mod m
where, z and m are some chosen, positive numbers.
You can study more about how to choose z and m as well as about hashing here.
Finally, the indexes which have the same hashed value are covered by the same set of queries.
Hashing with the help of Difference Array.
-
Suppose the i^{th} query, contains two integers L_i, R_i (1 \le L_i \le R_i \le n). Now every index [L_i,R_i], endpoints inclusive will be coverned by the i^{th} query. Hence by using the concept of Differnece array and hashing:
- hash[L]=(hash[L] + i⋅z^i) \mod m
- hash[R]=(hash[R] - i⋅z^i) \mod m
When all the queries are processed, we can easily found the hashed query for a particular index of an array by doing prefix addition on our hash array.
Finally, the indexes which have the same hashed value are covered by the same set of queries.
As soon as we knew about the indexes which are covered by the same set of queries. All we need to do is to reverse those indices in our answer.
Time Complexity
O(N+Q) per test case
SOLUTIONS:
Setter
#include <bits/stdc++.h>
using namespace std;
mt19937 gen(666);
void solve0() {
int n, q;
cin >> n >> q;
vector<bool> used(n, false);
vector<int> starts(n, 0), ends(n, 0);
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
--l; --r;
++starts[l];
++ends[r];
}
int balance = 0;
for (int i = 0; i < n; ++i) {
balance += starts[i];
if (balance) used[i] = true;
balance -= ends[i];
}
for (int i = 0; i < n; ++i) {
if (used[i]) cout << i + 1 << ' ';
else cout << 1 << ' ';
}
cout << '\n';
}
void solve1() {
int n, q;
cin >> n >> q;
vector<long long> starts(n, 0), ends(n, 0);
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
--l; --r;
long long hash = gen();
starts[l] += hash;
ends[r] += hash;
}
long long balance = 0;
vector<long long> hashes(n);
for (int i = 0; i < n; ++i) {
balance += starts[i];
hashes[i] = balance;
balance -= ends[i];
}
vector<long long> compressed = hashes;
sort(compressed.begin(), compressed.end());
compressed.resize(unique(compressed.begin(), compressed.end()) - compressed.begin());
vector<vector<int>> indexes(compressed.size());
for (int i = 0; i < n; ++i) {
int hash_id = lower_bound(compressed.begin(), compressed.end(), hashes[i]) - compressed.begin();
if (compressed[hash_id] != 0) indexes[hash_id].emplace_back(i);
}
vector<int> ans(n, n - 1);
for (auto &v : indexes) {
int sz = v.size();
for (int i = 0; i < sz; ++i) {
ans[v[i]] = v[sz - i - 1];
}
}
for (auto x : ans) cout << x + 1 << ' ';
cout << '\n';
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cout << fixed << setprecision(3);
#else
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << fixed << setprecision(15);
#endif
int T, P;
cin >> T >> P;
while (T --> 0) {
if (P == 0) solve0();
else solve1();
}
#ifdef LOCAL
cerr << "proc time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
#endif
return 0;
Tester
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
int p;
int le[200005],ri[200005],ans[200005];
vi li[200005],re[200005];
void solve() {
// int n=readIntSp(1,200'000),q=readIntLn(1,200'000);
int n,q;
cin>>n>>q;
fr(i,1,n) {
li[i].clear();
re[i].clear();
}
while(q--) {
int l,r;
cin>>l>>r;
// int l=readIntSp(1,n),r=readIntLn(l,n);
li[l].pb(r);
re[r].pb(l);
}
set<int> pp;
pp.insert(n+1);
fr(i,1,n) {
for(int j:li[i])
pp.insert(j);
ri[i]=*pp.lower_bound(i);
}
pp.clear();
pp.insert(0);
for(int i=n; i>0; i--) {
for(int j:re[i])
pp.insert(j);
le[i]=*(--pp.upper_bound(i));
}
vector<pii> qq;
fr(i,1,n)
qq.pb({ri[i]-le[i]+1,i});
sort(all(qq));
pp.clear();
fr(i,1,n)
pp.insert(i);
int tol=1+p*(n-1);
for(auto i:qq) {
if(le[i.se]==0)
ans[i.se]=tol;
else {
if(p==0) {
ans[i.se]=*pp.lower_bound(le[i.se]);
pp.erase(ans[i.se]);
} else {
ans[i.se]=*(--pp.upper_bound(ri[i.se]));
pp.erase(ans[i.se]);
}
}
}
fr(i,1,n)
cout<<ans[i]<<" \n"[i==n];
}
signed main() {
// freopen("02","r",stdin);
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(10);
// int t=readIntSp(1,1000);
// p=readIntLn(0,1);
int t=1;
cin>>t>>p;
fr(i,1,t)
solve();
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
Editorialist
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p1=10000019;
const int m=1e9+9;
const int m1=1003162753;
int p_pow=1;
int p_pow1=1;
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t,p;
cin>>t>>p;
while(t--)
{
int n,q;
cin>>n>>q;
int hash[n+2]={};
int l[q+2],r[q+2];
for(int i=1;i<=q;i++)
{
cin>>l[i]>>r[i];
hash[l[i]]+=1;
hash[r[i]+1]-=1;
}
if(p==0)
{
for(int i=1;i<=n;i++)
{
hash[i]+=hash[i-1];
if(hash[i]==0)
cout<<1<<" ";
else
cout<<i<<" ";
}
cout<<"\n";
}
else
{
int hashed[n+2]={};
int hashed1[n+2]={};
p_pow=1;
p_pow1=1;
for(int i=1;i<=q;i++)
{
int temp=(i*p_pow)%m;
hashed[l[i]]=(hashed[l[i]]+temp)%m;
hashed[r[i]+1]=(hashed[r[i]+1]-temp)%m;
while(hashed[r[i]+1]<0)
hashed[r[i]+1]+=m;
hashed[r[i]+1]=hashed[r[i]+1]%m;
p_pow=(p_pow*p1)%m;
int temp1=(i*p_pow1)%m1;
hashed1[l[i]]=(hashed1[l[i]]+temp1)%m1;
hashed1[r[i]+1]=(hashed1[r[i]+1]-temp1)%m1;
while(hashed1[r[i]+1]<0)
hashed1[r[i]+1]+=m1;
hashed1[r[i]+1]=hashed1[r[i]+1]%m1;
p_pow1=(p_pow1*p1)%m1;
}
map <pair<int,int>,vector<int>> map1;
for(int i=1;i<=n;i++)
{
hashed[i]=(hashed[i]+hashed[i-1])%m;
hashed1[i]=(hashed1[i]+hashed1[i-1])%m1;
}
for(int i=1;i<=n;i++)
{
map1[{hashed[i],hashed1[i]}].push_back(i);
}
for(int i=1;i<=n;i++)
{
if(hashed[i]==0 && hashed1[i]==0)
cout<<n<<" ";
else
{
cout<<map1[{hashed[i],hashed1[i]}].back()<<" ";
map1[{hashed[i],hashed1[i]}].pop_back();
}
}
cout<<"\n";
}
}
return 0;
}