PROBLEM LINK:
Practice
Contest
Video Editorial
Setter: Ritesh Gupta
Tester: Rahul Dugar
Editorialist: Ishmeet Singh Saggu
DIFFICULTY:
Medium
PREREQUISITES:
Two-Pointer and Segment Tree with Lazy Propagation.
PROBLEM:
There are N chefs and M types of dishes, ith chef can cook a dish of type F_i also each chef has K friends. When some chef cooks a dish, he can ask his friends or the chefs who cook the same type to evaluate the dish. The chef cannot evaluate his own dish. You have to count the number of pairs L and R and allow the chefs L, L+1, …, R to cook their dishes and have them evaluated as described above each chef from 1 to N evaluates at least one dish.
QUICK EXPLANATION:
- Suppose if range [L, R] satisfies the condition then all the ranges which contain this range will satisfy the condition. i.e. all the ranges [X, Y] such that X \leq L and Y \geq R.
- So will use the Two-Pointer technique to compute the number of segments by fixing the left border and finding the shortest right border such that segment [L, R] satisfies the condition. And we will add (N-R+1) to our answer.
- We will create a modified array such that all the chefs with dish type 1 are put first, chefs with dish type 2 are put next, chefs with dish type 3 are put next, and so on. In this way, we can update the chefs with the same dish type in O(\log{N}) as they form a continuous segment using segment tree with lazy propagation.
EXPLANATION:
Let us propose a claim. Suppose if range [L, R] satisfies the condition then all the ranges which contain this range will satisfy the condition. i.e. all the ranges [X, Y] such that X \leq L and Y \geq R.(think why?)
Now first try to do this problem with two-pointer in an inefficient way. To count the number of segments we can follow the strategy as :
- Maintain a frequency array which tells the number of times a chef i has been invited. Initially, all values are zero.
- Maintain a count variable which tells the number of which has been invited and it is equal to 0 initially as no chef has been invited yet.
- Let us fix the left border. Suppose for each i where i is the left pointer we count the minimum R, where R is the right pointer such that segment [i, R] satisfies the condition. Then we can add (N-R+1) ranges to our answer(it is the number of ranges starting at i and ending at index \geq R).
- Initially let the right pointer is at 0.
- Iterate over the left border of the range. Suppose we start at index 1. we will add all the chef’s friends and those with the same dish type to the frequency array(except chef itself as he cannot evaluate his own dish).
We will increase the count variable only when the value or frequency for some chef changes from 0 to 1then we increase the right pointer until right pointer hits N or the value of count variable becomes N. Suppose it becomes N when the right pointer is equal to j then we will add (N-j+1) to our answer. Now when we shift our left border from i to i+1 we will subtract all his friends and those with the same dish type as chef iWe will decrease the count variable only when the value or frequency for some chef changes from 1 to 0.Also, note you will not add the friends and other chefs for the chef i+1 until your right pointer > left pointer because we have already invited his friends and chef with dish type same as dish type of chef i+1 as we have moved our right pointer. - In this way we can compute the answer.
Now the only problem in this approach is that the number of chefs with the same dish type as the current chef can be very large which leads it to O(N^2) solution in the worst case. So we need an efficient way to update and check whether all chefs have been invited at least once or not. For this, we will use Segment Tree with Lazy Propagation.
We will create a modified array such that all the chefs with dish type 1 are put first, chefs with dish type 2 are put next, chefs with dish type 3 are put next, and so on. In this way, we can update the chefs with the same dish type in O(\log{N}) as they form a continuous segment, and as the number of friends which (might have different dish type) is \leq 3, so we can do an update for each of them individually. (NOTE! suppose you update the range of dish type for the chef i, then you have to update again for chef i to subtract the effect of the "range dish update" as it is mentioned in the question that chef cannot evaluate his own dish . So basically the indication(depends on the implementation of segment tree) that all chefs have been invited at least once can be done by querying over the whole range. This modification basically converts our previous O(N^{2}) solution to O(N*\log{N}) solution.
TIME COMPLEXITY:
- Both Left and Right Pointer changes O(N) time and each chef i, adding and deleting his friends and other chefs with the same dish type requires O(\log{N}).
- So total time complexity per test case is O(N*\log{N}).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
char input[] = "input/input06.txt";
char output[] = "output/output06.txt";
const int N = 300010;
int a[N], c[N][10], b[N];
int range[N][2], idx[N];
int tree[5*N], lazy[5*N];
void updateRange(int node, int start, int end, int l, int r, int val)
{
// Current segment is not within range [l, r]
if(start > end or start > r or end < l)
return;
// This node needs to be updated
if(lazy[node] != 0)
{
// Update it
tree[node] += lazy[node];
if(start != end)
{
// Mark child as lazy
lazy[node*2] += lazy[node];
// Mark child as lazy
lazy[node*2+1] += lazy[node];
}
// Reset it
lazy[node] = 0;
}
if(start >= l and end <= r)
{
// Segment is fully within range
tree[node] += val;
if(start != end)
{
// Not leaf node
lazy[node*2] += val;
lazy[node*2+1] += val;
}
return;
}
int mid = (start + end) / 2;
// Updating left child
updateRange(node*2, start, mid, l, r, val);
// Updating right child
updateRange(node*2 + 1, mid + 1, end, l, r, val);
// Updating root with min value
tree[node] = min(tree[node*2]+lazy[node*2], tree[node*2+1]+lazy[node*2+1]);
}
int main()
{
// freopen(input, "r", stdin);
// freopen(output, "w", stdout);
int t;
cin >> t;
while(t--)
{
int n,m,k;
cin >> n >> m >> k;
for(int i=1;i<=5*n;i++)
tree[i] = lazy[i] = 0;
vector <int> v[m];
for(int i=0;i<n;i++)
{
cin >> b[i];
b[i]--;
v[b[i]].push_back(i);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<k;j++)
cin >> c[i][j], c[i][j]--;
}
int st = 0;
for(int i=0;i<m;i++)
{
for(int j:v[i])
idx[j] = st++;
range[i][0] = st - v[i].size();
range[i][1] = st-1;
}
// for(int i=0;i<m;i++)
// cout << range[i][0] << " " << range[i][1] << endl;
// for(int i=1;i<=n;i++)
// cout << idx[i] << " ";
// cout << endl;
int i,j;
i = j = st = 0;
long long ans = 0;
while(i < n && tree[1] == 0)
{
for(int l=0;l<k;l++)
{
if(idx[c[i][l]] < range[b[i]][0] || idx[c[i][l]] > range[b[i]][1])
updateRange(1,0,n-1,idx[c[i][l]],idx[c[i][l]],1);
}
updateRange(1,0,n-1,range[b[i]][0],range[b[i]][1],1);
updateRange(1,0,n-1,idx[i],idx[i],-1);
while(j <= i && tree[1] > 0)
{
for(int l=0;l<k;l++)
{
if(idx[c[j][l]] < range[b[j]][0] || idx[c[j][l]] > range[b[j]][1])
updateRange(1,0,n-1,idx[c[j][l]],idx[c[j][l]],-1);
}
updateRange(1,0,n-1,range[b[j]][0],range[b[j]][1],-1);
updateRange(1,0,n-1,idx[j],idx[j],1);
j++;
}
if(j > st)
{
ans += (j - st) * 1ll * (n - i);
st = j;
}
i++;
}
cout << ans << endl;
}
}
Tester's Solution
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
#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);
}
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,' ');
}
const int N=300005;
int f[N];
int friends[N][5];
int last[N];
vector<pii> fuls[N];
vi thistype[N];
vi whosefriend[N];
priority_queue<int,vi,greater<int>> lols[N],lols2[N];
vi rem[N];
int sum_n=0;
void solve() {
// int n,m,k;
// cin>>n>>m>>k;
int n=readIntSp(1,300000);
sum_n+=n;
int m=readIntSp(1,300000);
int k=readIntLn(1,3);
fr(i,1,m) {
thistype[i].clear();
while(lols[i].size())
lols[i].pop();
while(lols2[i].size())
lols2[i].pop();
fuls[i].clear();
}
fr(i,1,n) {
rem[i].clear();
whosefriend[i].clear();
}
fr(i,1,n) {
// cin>>f[i];
if(i!=n)
f[i]=readIntSp(1,m);
else
f[i]=readIntLn(1,m);
thistype[f[i]].pb(i);
}
fr(i,1,n) {
rep(j,0,k) {
// cin>>friends[i][j];
if(j!=k-1)
friends[i][j]=readIntSp(1,n);
else
friends[i][j]=readIntLn(1,n);
whosefriend[friends[i][j]].pb(i);
}
}
fr(i,1,m) {
for(int j=0; j+1<sz(thistype[i]); j++)
fuls[i].pb({thistype[i][j],thistype[i][j+1]});
for(int j:thistype[i]) {
auto it=lower_bound(all(whosefriend[j]),j);
if(it!=whosefriend[j].end())
fuls[i].pb({j,*it});
if(it!=whosefriend[j].begin()) {
it--;
fuls[i].pb({*it,j});
}
}
}
fr(i,1,n) {
last[i]=-infi;
lols[f[i]].push(last[i]);
}
fr(i,1,n) {
rep(jj,0,k) {
int j=friends[i][jj];
lols2[f[j]].push(last[j]);
last[j]=i;
lols[f[j]].push(last[j]);
while(lols2[f[j]].size()&&lols[f[j]].top()==lols2[f[j]].top()) {
lols[f[j]].pop();
lols2[f[j]].pop();
}
if(lols[f[j]].top()!=-infi)
fuls[f[j]].pb({lols[f[j]].top(),i});
}
}
fr(i,1,m) {
sort(all(fuls[i]),[](pii a, pii b){
if(a.fi!=b.fi)
return a.fi<b.fi;
else
return a.se>b.se;
});
vector<pii> res;
for(auto j:fuls[i]) {
while(res.size()&&res.back().se>=j.se)
res.pop_back();
res.pb(j);
}
fuls[i].swap(res);
reverse(all(fuls[i]));
}
int rip=0;
fr(i,1,m) {
if(thistype[i].size()) {
if(fuls[i].empty()) {
cout<<0<<endl;
return;
}
for(auto j:fuls[i])
rem[j.fi+1].pb(i);
rip=max(rip,fuls[i].back().se);
fuls[i].pop_back();
}
}
ll ans=0;
fr(i,1,n) {
// trace(rem[i]);
bool mcb=0;
for(auto j:rem[i]) {
if(fuls[j].empty()) {
mcb=1;
break;
}
rip=max(rip,fuls[j].back().se);
fuls[j].pop_back();
}
if(mcb)
break;
// trace(rip);
ans+=n+1-rip;
}
cout<<ans<<endl;
}
/*
2
3 3 1
1 2 3
3
3
1
6 2 1
1 1 1 2 2 2
2
1
4
3
6
5
*/
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(8);
int t=readIntLn(1,1000);
// int t;
// cin>>t;
while(t--)
solve();
assert(1<=sum_n&&sum_n<=2000000);
assert(getchar()==EOF);
return 0;
}
Video Editorial
Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. 