I just completed CSES Sorting and Searching section problems. And I didn't find any editorials for this. So I am writing my own approach for the problems.Please do correct me if I made any mistakes and do share your approach for the problems.
My solutions are here
complete editorial for CSES coding platform of all 27 problems in Sorting and Searching section.
1.Distinct Numbers
Just use set to store the elements and answer is the size of set.
int n,x;cin>>n;
set<int>s;
for(int i=0;i<n;++i)
{
cin>>x;
s.insert(x);
}
cout<<s.size()<<endl;
2.Apartments
Two pointer technique-If apartment size is greater than x+k then upper pointer will increase or less than x-k then lower pointer will increase otherwise both the pointer increase along with counter. NB.Don't forget to sort both the arrays.
cin>>n>>m>>k;
V v(n),u(m);
lp(i,n)cin>>v[i];
lp(i,m)cin>>u[i];
srt(v);srt(u);
cnt=0;
i=0,j=0;
while(i<n and j<m)
{
if(v[i]-k>u[j])j++;
else if(v[i]+k<u[j])i++;
else
{
i++,j++,cnt++;
}
}
cout<<cnt<<endl;
3.Ferris Wheel
Two pointer technique-First sort the array. Then we have to minimize the number .So if the pointers value over flow the limit then we decrease the upper pointer. otherwise decrease the number.
cin>>n>>m;
V v(n);
lp(i,n)cin>>v[i];
cnt=n,sum=0,c=0;
srt(v);
i=0,j=n-1;
while(i<j)
{
if(v[i]+v[j]<=m)cnt--,i++,j--;
else j--;
}
cout<<cnt<<endl;
4.Concert Tickets
Here we need the lower bound of the multiset(as the values can be duplicate) each time and erase it from the set. If the iterator points to the end of set that means there is no value to satisfy the condition.
cin>>n>>m;
V v(n),u(m);
lp(i,n)cin>>v[i];
lp(i,m)cin>>u[i];
multiset<int,greater<int>>s;
lp(i,n)s.insert(v[i]);
//joker(s)
lp(i,m)
{
auto it=s.lower_bound(u[i]);
if(it==s.end())cout<<-1<<endl;
else
{
cout<<*it<<endl;
s.erase(it);
}
//joker(s)
}
5.Restaurant Customers
lets consider arrival time +1 and leaving time -1.So we use pair sorting to find the maximum amount of arrival times of the customers.
cin>>n;
VP vp;
lp(i,n)
{
cin>>x>>y;
vp.pb({x,1});
vp.pb({y,-1});
}
ans=0,sum=0;
srt(vp)
for(auto i:vp)
{
sum+=i.second;
ans=max(ans,sum);
}
cout<<ans<<endl;
6.Movie Festival
Here,we sort the pair according to the ending time.Now if there is no overlaps then we increase the count.Always temp value updated to pair second element.
cin>>n;
VP vp;
lp(i,n)
{
cin>>x>>y;
vp.pb({x,y});
}
sort(vp.begin(),vp.end(),as_second);
i=0,ans=0,temp=0;
while(i<n)
{
if(temp<=vp[i].first)
{
temp=vp[i].second;
i++;
ans++;
}
else i++;
}
cout<<ans<<endl;
7.Sum of Two Values
Basic two pointer technique-If the sum is greater than x the upper pointer should be decreased or if less than x then lower pointer should be increased. Here we need to use pair to store the indices of the value.
cin>>n>>m;
VP v(n);
lp(i,n)
{
cin>>x;
v[i]={x,i};
}
srt(v)
i=0,j=n-1;
while(i<j)
{
if(v[i].first+v[j].first>m)
{
j--;
}
else if(v[i].first+v[j].first<m)
{
i++;
}
else
{
cout<<v[i].second+1<<" "<<v[j].second+1<<endl;
return;
}
}
cout<<"IMPOSSIBLE"<<endl;
8.Maximum Subarray Sum
If the sum is increased then we add the value to sum otherwise just take the value. Print the maximum sum.
ll n,sum=0,ma=-9e18;
cin>>n;
vector<ll>v(n);
for(ll &i:v)
{
cin>>i;
sum=max(sum+i,i);
ma=max(ma,sum);
}
cout<<ma<<endl;
9.Stick Lengths
First we have to sort the array. The total distance between the middle element of the array with the rest of the elements is the answer.
int n;cin>>n;
vector<ll>v(n);
for(ll &i:v)
{
cin>>i;
}
sort(v.begin(),v.end());
ll mid=v[n/2],ans=0;
for(ll &i:v)
{
ans+=abs(i-mid);
}
cout<<ans<<endl;
10.Playlist
Geeksforgeeks has a similar artical explaining the problem ,here.you have to use ordered map to get ac here.
ll n;cin>>n;
ll a[mx];
for(ll i=0;i<n;++i)
{
cin>>a[i];
}
map<ll,ll>mp;
ll ans=0;
for(ll i=0,j=0;i<n;++i)
{
j=max(mp[a[i]],j);
ans=max(ans,i-j+1);
mp[a[i]]=i+1;
}
cout<<ans<<"\n";
11.Towers
Here we use multiset to store the values and then everytime check if the upper bound of x is present or not in the set.If present then we erase from the set and insert to set.Finally size of set is the answer.
int n,x;cin>>n;
multiset<int>s;
for(int i=0;i<n;++i)
{
cin>>x;
auto it=s.upper_bound(x);
//cout<<*it<<endl;
if(it==s.end())s.insert(x);
else
{
s.erase(it);
s.insert(x);
}
}
cout<<s.size()<<endl;
12.Traffic Lights
Here we first insert 0 and length of the street x in a set.After we put each traffic light we calculate the difference between both from the 0 and from x as well.And we need to print the maximum value of both this term. As last value of set contains the larger value so it's the answer.
cin >> x >> n;
set<int> s;
s.insert(0);
s.insert(x);
multiset<int> ms;
ms.insert(x);
while(n--)
{
cin >> a;
auto it = s.lower_bound(a);
auto it2 = it;
--it2;
//debug2(*it,*it2)
ms.erase(ms.find(*it - *it2));
ms.insert(a - *it2);
ms.insert(*it - a);
//joker(ms)
//auto last = ms.end()[1];
cout << *--ms.end() << " ";
s.insert(a);
}
13.Room Allocation
Here we used multimap<pair<int,int>,int>mp to store the arrival and departure time along with their indices.We used min heap to check if the previous customer is left the hotel or not.If the customer hadn't left the hotel then we increase the count otherwise get the previous count.Everytime we pushed count to the vector.
int n,cnt=0;cin>>n;
multimap<pair<int,int>,int>mp;
for(int i=0;i<n;++i)
{
int x,y;cin>>x>>y;
mp.insert({{x,y},i});
}
vector<int>v(n);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
for(auto i=mp.begin();i!=mp.end();++i)
{
int a,b,c;
tie(a,b)=i->first;
if(pq.empty() or get<0>(pq.top())>=a)
{
c=++cnt;
}
else
{
c=get<1>(pq.top());
pq.pop();
}
pq.push({b,c});
v[i->second]=c;
}
cout<<cnt<<endl;
for(auto i:v)cout<<i<<" ";
14.Factory Machines
Binary search :We check all the possible outcomes between 0 and 1e18 using binary search. Here the possible outcome can't cross 1e9 so we must take the minimum of sum and 1e9.Similar type of problem:get the container
ll n,m;
ll ar[mx];
bool check(ll p)
{
ll sum=0;
for(int i=0;i<n;++i)
{
sum+=min(p/ar[i],(ll)1e9);
}
return sum>=m;
}
cin>>n>>m;
for(int i=0;i<n;++i)
{
cin>>ar[i];
}
ll low=0,hi=1e18;
while(low<hi)
{
ll mid=low/2+hi/2;
if(check(mid))
{
hi=mid;
}
else low=mid+1;
}
cout<<low<<endl;
15.Tasks and Deadlines
First sort the pair in non decreasing order. Then each time get the difference between the second value with the summation of first value.
ll n;
cin>>n;
vector<pair<ll,ll>>arr;
for(ll i=0;i<n;i++)
{
ll x,y;
cin>>x>>y;
arr.push_back({x,y});
}
sort(arr.begin(),arr.end());
ll sum=0;
ll start=0;
for(ll i=0;i<n;i++)
{
start+=arr[i].first;
sum+=arr[i].second-start;
}
cout<<sum;
16.Reading Books
Here if max>(sum-max) then 2*max otherwise sum is the answer.
ll n;cin>>n;
ll sum=0,ma=INT_MIN;
for(int i=0;i<n;++i)
{
ll x;cin>>x;
sum+=x;
ma=max(ma,x);
}
cout<<(ma>(sum-ma)?2*ma:sum)<<endl;
17.Sum of Three Values
Like the previous one here we can use similar approach to get the third value. If the sum of three value exceeds we decrease upper pointer value or if it subceeds then we increase lower pointer value.
int n,x;cin>>n>>x;
vector<int>a(n);
vector<pair<int,int>>v(n);
for(int i=0;i<n;++i)
{
int xx;
cin>>xx;
a[i]=xx;
v[i]={xx,i+1};
}
sort(v.begin(),v.end());
for(int i=0;i<n;++i)
{
int low=0,hi=n-1;
while(low<hi)
{
if(v[low].second==i+1)low++;
else if(v[hi].second==i+1)hi--;
else if(v[low].first+v[hi].first+a[i]>x)hi--;
else if(v[low].first+v[hi].first+a[i]<x)low++;
else
{
cout<<v[low].second<<" "<<v[hi].second<<" "<<i+1<<endl;return 0;
}
}
}
cout<<"IMPOSSIBLE"<<endl;
18.Sum of Four Values
Here we run two loops one starting i=0,another j=i+1.The other two values we check from j+1 to n-1.As the pair is already sorted the numbers must be lied between these numbers.
int n,x;cin>>n>>x;
vector<int>a(n);
vector<pair<int,int>>v(n);
for(int i=0;i<n;++i)
{
ll xx;
cin>>xx;
a[i]=xx;
v[i]={xx,i};
}
sort(v.begin(),v.end());
for(int i=0;i<n;++i)
{
for(int j=i+1;j<n;++j)
{
int low=j+1,hi=n-1;
while(low<hi)
{
int p=v[i].first,q=v[j].first,r=v[low].first,s=v[hi].first;
if(p+q+r+s==x)
{
cout<<v[i].second+1<<" "<<v[j].second+1<<" "<<v[low].second+1<<" "<<v[hi].second+1<<endl;return 0;
}
else if(p+q+r+s<x)low++;
else hi--;
}
}
}
cout<<"IMPOSSIBLE\n";
19.Nearest Smaller Values
Basic Amortized analysis technique. Better explanation is here in geeksforgeeks.
int n;cin>>n;
vector<int>v(n);
for(int i=0;i<n;++i)
{
cin>>v[i];
}
stack<int>s;
for(int i=0;i<n;++i)
{
while(!s.empty() and v[s.top()]>=v[i])
{
s.pop();
}
if(s.empty())
{
cout<<0<<" ";
}
else
{
cout<<s.top()+1<<" ";
}
s.push(i);
}
20.Subarray Sums I
We can solve it using prefix sum like this.But if we consider negative values then here is another approach-Link(https://www.geeksforgeeks.org/number-subarrays-sum-exactly-equal-k/) in geeks for geeks
ll n,sum;cin>>n>>sum;
vector<ll>v(n);
for(int i=0;i<n;++i)
cin>>v[i];
ll m=0,cnt=0;
map<ll,ll>mp;
for(int i=0;i<n;++i)
{
m+=v[i];
if(m==sum)cnt++;
if(mp.count(m-sum))
{
cnt+=mp[m-sum];
}
mp[m]++;
}
cout<<cnt<<endl;
21.Subarray Sums II
Similar to previous one.
ll n,sum;cin>>n>>sum;
vector<ll>v(n);
for(int i=0;i<n;++i)
cin>>v[i];
ll m=0,cnt=0;
map<ll,ll>mp;
for(int i=0;i<n;++i)
{
m+=v[i];
if(m==sum)cnt++;
if(mp.count(m-sum))
{
cnt+=mp[m-sum];
}
mp[m]++;
}
cout<<cnt<<endl;
22.Subarray Divisibility
geeks for geeks has similar article explained the problem here
ll n,sum=0;cin>>n;
vector<ll>v(n),mod(n,0);
for(ll i=0;i<n;++i)
{
cin>>v[i];
sum+=v[i];
mod[((sum%n)+n)%n]++;
}
ll res=0;
for(ll i=0;i<n;++i)
{
if(mod[i]>1)
{
res+=(mod[i]*(mod[i]-1)/2);
}
}
res+=mod[0];
cout<<res<<endl;
23.Array Division
Simple binary search-Similar type of problem:get the container.
const ll mx = 2e5+5;
ll n,k,hi=0,low=9e18,cnt;
ll v[mx];
bool check(ll tot)
{
ll temp=0,cnt=1;
for(ll i=0;i<n;++i)
{
if(v[i]>tot)return false;
if(v[i]+temp<=tot)temp+=v[i];
else {
temp=v[i];cnt++;
}
}
return cnt<=k;
}
cin>>n>>k;
for(ll i=0;i<n;++i)
{
cin>>v[i];
hi+=v[i];
if(v[i]<low)low=v[i];
}
ll ans=-1;
while(low<=hi)
{
ll mid=(low+hi)/2;
if(check(mid))
{
//cout<<ans<<endl;
ans=mid;
hi=mid-1;
}
else
{
low=mid+1;
}
}
cout<<ans<<endl;
24.Sliding Median
Basic sliding window technique-use queue to maintain the window size constant. To search from the window we have to use ordered multiset as it's searching is faster then other data structure to be exact O(log(n)) time.
int n,m;cin>>n>>m;
int a[n];
for(int i=0;i<n;++i)
{
cin>>a[i];
}
ordered_multiset st;
queue<int>q;
for(int i=0;i<n;++i)
{
if(q.size()==m)
{
if(m&1)
{
cout<<*(st.find_by_order(m/2))<<" ";
}
else cout<<*(st.find_by_order(m/2-1))<<" ";
int p=q.front();
st.erase(st.find_by_order(st.order_of_key(p)));
q.pop();
}
q.push(a[i]);
st.insert(a[i]);
}
if(m&1)
{
cout<<*(st.find_by_order(m/2))<<" ";
}
else
{
cout<<*(st.find_by_order(m/2-1))<<" ";
}
25.Sliding Cost
In this problem,everytime we check for a window of k elements.
First we check for first k elements and store it's mid value in P(capital). Then with each iteration we erase the first value from window and add the next value from the array.
See,if the initial set is 2 3 4 after iteration it's 3 4 5.
After the iteration mid value is p(small).Now after the new value added to set the cost is abs(p-a[i+m]) and the previous cost is abs(P-a[i]).So the change of total cost d is simply the difference between these two.
Now when it's come to even value ,Like this one-
8 4
2 4 3 5 8 1 2 1
Here the previous window is 2 3 4 5 and after 1st iteration 3 4 8 5. P(capital)=3, p(small)=4; Unlike the odd k ,even k has two mid value. So either 1st mid value gives you the min cost or the 2nd mid value. If you notice then P(capital) is 1st mid value, p(small) is 2nd mid value. That's the reason we simply erase the extra value(it's either add to total cost or decreases).
ll n,m;cin>>n>>m;
ll a[n];
for(int i=0;i<n;++i)
{
cin>>a[i];
}
ordered_multiset st;
for(int i=0;i<m;++i)
{
st.insert(a[i]);
}
ll P=*st.find_by_order((m+1)/2-1);
ll d=0;
for(int i=0;i<m;++i)d+=abs(a[i]-P);
cout<<d<<" ";
for(int i=0;i<n-m;++i)
{
st.erase(st.find_by_order(st.order_of_key(a[i])));
st.insert(a[i+m]);
ll p=*st.find_by_order((m+1)/2-1);
d+=abs(p-a[i+m])-abs(P-a[i]);
if(!(m&1))d-=p-P;
P=p;
cout<<d<<" ";
}
26.Movie Festival II
We always check the lower bound of the starting time.If the starting time is already in the set or less then the previous one then we increase the count and push the ending value to the set.
int n,k;cin>>n>>k;
vector<pair<int,int>>v(n);
for(int i=0;i<n;++i)
{
int x,y;cin>>x>>y;
v[i]={y,x};
}
sort(v.begin(),v.end());
multiset<int,greater<int>>s;
s.insert(v[0].first);
for(int i=0;i<k-1;++i)s.insert(0);
int cnt=1;
for(int i=1;i<n;++i)
{
auto it=s.lower_bound(v[i].second);
if((*it)==s.size())
{
if((*it)<=v[i].second and s.find(v[i].second)!=s.end())
{
s.erase(it);
s.insert(v[i].first);
cnt++;
}
}
else
{
s.erase(it);
s.insert(v[i].first);
cnt++;
}
}
cout<<cnt<<endl;
27.Maximum Subarray Sum II
geeks for geeks has similar article given here.
ll n,a,b;cin>>n>>a>>b;
ll ar[n],presum[n];
for(int i=0;i<n;++i)
{
cin>>ar[i];
}
presum[0]=ar[0];
for(int i=1;i<n;++i)
{
presum[i]=presum[i-1]+ar[i];
}
multiset<ll>s;
s.insert(0);
ll ans=-9e18;
ans=max(ans,presum[a-1]);
int flag=0;
for(int i=a;i<n;++i)
{
if(i-b>=0)
{
if(!flag)
{
auto it=s.find(0);
s.erase(it);
flag=1;
}
}
if(i-a>=0)
{
s.insert(presum[i-a]);
}
ans=max(ans,presum[i]-*s.begin());
if(i-b>=0)
{
auto it=s.find(presum[i-b]);
s.erase(it);
}
}
cout<<ans<<endl;
how is this working in 25th problem sliding cost
abs(p-a[i+m])-abs(P-a[i])and if m is even we decrease the extra valuep-Pcan someone explain why the common elements in the the windows are not considered for new cost ? Please explain the math behind it
In this problem,everytime we check for a window of k elements.
First we check for first k elements and store it's mid value in P(capital). Then with each iteration we erase the first value from window and add the next value from the array.
See,if the initial set is
2 3 4after iteration it's3 4 5.After the iteration mid value is p(small).Now after the new value added to set the cost is
abs(p-a[i+m])and the previous cost isabs(P-a[i]).So the change of total cost d is simply the difference between these two.Now when it's come to even value ,Like this one-
Here the previous window is
2 3 4 5and after 1st iteration3 4 8 5. P(capital)=3, p(small)=4; Unlike the odd k ,even k has two mid value. So either 1st mid value gives you the min cost or the 2nd mid value. If you notice then P(capital) is 1st mid value, p(small) is 2nd mid value. That's the reason we simply erase the extra value(it's either add to total cost or decreases).I hope it makes sense.
If you notice then P(capital) is 1st mid value, p(small) is 2nd mid valuethis statement is not always true.You just explained the code, I want some kind of mathematical proof of why this works ? Why changing median doesn't effect cumulative cost of the common elements is the windows ?
Yes a mathematical proof would be helpful.
I guess for question number 10 sliding window concept will be much more intuitive. Here is my ac solution,
Can you share intuition of updating j variable in your solution?
Hi, can you please share with me the expected time complexity of your code and how exactly could you determine if your code could pass the given test cases? It seems to me that complexity would be O(n^2) since there is a while loop inside the outer for loop?
Yet your code seems to pass all the test cases within the accepted time limit, HOW?
the time complexity is $$$\mathcal O(N\log N)$$$ since it uses sliding window and a set. Sliding window uses two loops and takes $$$\mathcal O(N)$$$; notice that $$$j$$$ does not reset to $$$0$$$ and retains it's value every time $$$i$$$ increases.
here is a code that works in O(n)
For 10. Playlist I used two-pointer technique with sliding window concept, It is much more intuitive.
Keep on increasing window length, while we have subarray a with unique numbers. As soon as we find a duplicate, we delete from the array till the subarray does not contain duplicate
... https://cses.fi/paste/0e4683cd4bd40dc3180617/
In problem no 6 why it is necessary to sort elements based on ending time. Why can't we sort elements based on starting time?
Um.. Converting code to English words can't be called an editorial, but good job. Atleast people have some reference point where they can look for solutions.
Can someone explain the proof for 15-> Tasks and Deadlines ?
Let's take the testcase given in the problem and write out all possible combinations:
Observations:
Your solution of Subarray sum is very nice. I was using sliding window but your solution works for negative numbers too!
What exactly you did for creating ordered_multiset in 24th(Sliding Median) ? I created an ordered_set of pair {key,val} & stored some random number(but distinct) as val. Is there any better method to create ordered_multiset ? Btw, thanx for this blog!
How 18 — "Sum of 4 values" is working?, cause I think its complexity is n^3, and according to constraints that should not work. Can anyone explain?
For the O(N^2) solution ,you can refer this Sum Of 4 Values
Why is my solution giving TLE for the question Traffic Lights.
Here is my code...
first, an improvement could be made by adding
ios_base::sync_with_stdio(false); cin.tie(nullptr);
this increases the input speed. Read this: https://usaco.guide/general/fast-io?lang=cpp for more info on fast I/O. Everything else seems to be optimal if not very close to optimal. The solution is also on USACO guide: https://usaco.guide/problems/cses-1163-traffic-lights/solution
Can someone share their code in python language of "CSES: Concert Ticket"? I have used binary search in my code. But still getting TLE.. Don't know how to modify it further.
why does using set in first question gives tle
why does binary searching on a vector along with using the erase function give tle in the problem concert tickets?
nevermind erase function in vector is O(n) and for set its constant
In the E problem, If you're given same Arrival and departure times for more than one customer, this won't work in that case. I actually solved it a little differently, what I did was : It can be proved that the max customers will be only when we're at the departure time, so I traversed through every departure instant and then figured out how many people are there who have already arrived by then. I used binary search for that.
Here is the link to my submission : Accepted
HELP, Can anyone help me why this is giving the wrong answer Submission for the problem Restaurant Customers. I use sorting + binary search.
A few problems are missing like "missing coin sums" , " collecting numbers " . Btw thanks for this .
can someone explain the idea of the solution (27.Maximum Subarray Sum II)
Is it clear to you or need an explanation?
Thank you brother !
Movie Festival """" DP Soltuion """" : https://github.com/Ylandolsi/CSES/blob/main/Movie%20Festival.cpp
In the Concert Ticket Question, I tried to use Binary Search Logic, but got TLE in certain cases. For example in the input we have n = 5, m = 3 0 <= i <= n — 1 prices[i] : 5 3 7 8 5 0 <= j <= m — 1 max_prices[j] : 4 8 3 We sort the prices array and then, 1. We take a loop to iterate over the max_prices array, and check: a. If max_prices[j] is present in prices -> using Binary Search b. If max_prices[j] is not present in prices:(2 cases possible) — Find nearest lowest integer if available — Otherwise, return -1 The Time Complexity should be at max of : N * log(N) + N * log(M+N); for sorting — N * log(N) and the loop to iterate over and do either binary search or find the nearest smallest number. — N * log(M + N)
The code is here for reference:
include<bits/stdc+.h>
using namespace std; ll binSearch(ll target, vector&prices){ ll start = 0; ll end = prices.size(); while(start < end){ ll mid = (start + end)/2; if(prices[mid] == target){ return mid; } else if(prices[mid] < target){ start = mid + 1; } else{ end = mid; } } return -1; }
ll binSearch_on_nearest_number(ll target, vector&prices){ ll start = 0; ll end = prices.size(); ll nearest = -1; while(start < end){ ll mid = (start + end)/2; if(prices[mid] < target){ nearest = mid; start = mid + 1; } else{ end = mid; } } return nearest; }
int main(){ ll n, m; cin >> n >> m; vectorprices; for(ll i = 0; i < n; i++){ ll x; cin >> x; prices.push_back(x); } vectormax_prices; for(ll i = 0; i < m; i++){ ll x; cin >> x; max_prices.push_back(x); } sort(prices.begin(), prices.end()); for(ll i = 0; i < m; i++){ ll ans1 = binSearch(max_prices[i], prices); if(ans1 != -1){ // Answer already present cout << prices[ans1] << "\n"; prices.erase(prices.begin() + ans1); } else{ ll ans2 = binSearch_on_nearest_number(max_prices[i], prices); if(ans2 != -1){ cout << prices[ans2] << "\n"; prices.erase(prices.begin() + ans2); } // Only greater elements are left behind else{ cout << -1 << "\n"; } } } }
This gave me TLE in certain cases, pls let me know the problem in the above.