Loser_'s blog

CSES Sorting and Searching section editorials
By Loser_, 4 years ago, In English

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

Editorial
idea

2.Apartments

Editorial
idea

3.Ferris Wheel

Editorial
idea

4.Concert Tickets

Editorial
idea

5.Restaurant Customers

Editorial
idea

6.Movie Festival

Editorial
idea

7.Sum of Two Values

Editorial
idea

8.Maximum Subarray Sum

Editorial
idea

9.Stick Lengths

Editorial
idea

10.Playlist

Editorial
idea

11.Towers

Editorial
idea

12.Traffic Lights

Editorial
idea

13.Room Allocation

Editorial
idea

14.Factory Machines

Editorial
idea

15.Tasks and Deadlines

Editorial
idea

16.Reading Books

Editorial
idea

17.Sum of Three Values

Editorial
idea

18.Sum of Four Values

Editorial
idea

19.Nearest Smaller Values

Editorial
idea

20.Subarray Sums I

Editorial
idea

21.Subarray Sums II

Editorial
idea

22.Subarray Divisibility

Editorial
idea

23.Array Division

Editorial
idea

24.Sliding Median

Editorial
idea

25.Sliding Cost

Editorial
idea

26.Movie Festival II

Editorial
idea

27.Maximum Subarray Sum II

Editorial
idea
  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (26)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 value p-P

can someone explain why the common elements in the the windows are not considered for new cost ? Please explain the math behind it

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like 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 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).

    I hope it makes sense.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      If you notice then P(capital) is 1st mid value, p(small) is 2nd mid value this 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 ?

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes a mathematical proof would be helpful.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess for question number 10 sliding window concept will be much more intuitive. Here is my ac solution,

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
	int n;
	cin>>n;
	vector<int>k(n);
	for(int i=0;i<n;i++)
	cin>>k[i];
	set<int>st;
	int ans = 0,j=0;
	for(int i=0;i<n;i++)
	{
		if(st.find(k[i])!=st.end())
		{
			while(!st.empty() && k[j]!=k[i])
			{
			  st.erase(k[j]);
			  j++;	
		    }
		    st.erase(k[j]);
		    j++;
		}
		st.insert(k[i]);
		ans = max(ans,i-j+1);
	}
	cout<<ans;
	return 0;
}

Can you share intuition of updating j variable in your solution?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    here is a code that works in O(n)

    void solve()
{
    ll n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    unordered_map<ll, ll, custom_hash> index;
    ll ans = 0, low = 0;
    for (int i = 1; i <= n; i++)
    {
        if (index[a[i]] != 0)
        {
            low = max(low, index[a[i]]);
        }
        index[a[i]] = i;
        ans = max(ans, i - low);
    }
    cout << ans << nline;
}
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Spoiler
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the proof for 15-> Tasks and Deadlines ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let's take the testcase given in the problem and write out all possible combinations:

    • (10-6) + (12-11) + (15-19) => reward = 1
    • (10-6) + (15-14) + (12-19) => reward = -2
    • (15-8) + (10-14) + (12-19) => reward = -4
    • (15-8) + (12-13) + (10-19) => reward = -3
    • (12-5) + (10-11) + (15-19) => reward = 2
    • (12-5) + (15-13) + (10-19) => reward = 0

    Observations:

    1. We can observe that the deadlines are always positive while calculating the solution.
    2. The other term(consisting of the duration) is the sum of individual durations. For example, the case with reward = 1 can be written as (10-6) + (12-(6+5)) + (15-(6+5+8)). Notice that the i-th duration we choose, gets repeated in calculating all the further terms. So it makes sense to choose the durations sorted in a non-decreasing order.
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your solution of Subarray sum is very nice. I was using sliding window but your solution works for negative numbers too!

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my solution giving TLE for the question Traffic Lights.

Here is my code...

int main(){
    int x, n; 
    cin >> x >> n;

    multiset<int, greater<int>> len;
    len.insert(x);

    map<int, int> light;
    light[0] = x;

    for(int i=0 ; i<n ; i++){
        int p; cin >> p;
        auto it = light.upper_bound(p);
        --it;

        int a = it->first;
        int b = it->second;

        light[a] = p;
        light[p] = b;

        len.erase(len.find(b-a));
        len.insert(p-a);
        len.insert(b-p);

        cout << *len.begin() <<" ";
    }
}
→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had the same problem too. AC code:

    #include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,h,t;
    cin>>n>>m;
    multiset <int> s;
    for(int i=0;i<n;i++){
        cin>>h;
        s.insert(h);
    }
    while(m--){
        cin>>t;
        multiset<int>::iterator it=s.upper_bound(t);
        if(it==s.begin()){
            cout<<"-1\n";
            continue;
        }
        it--;
        cout<<*it<<"\n";
        s.erase(it);
    }
}

    TLE code:

    #include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,h,t;
    cin>>n>>m;
    vector <int> v;
    for(int i=0;i<n;i++){
        cin>>h;
        v.push_back(h);
    }
    sort(v.begin(),v.end());
    while(m--){
        cin>>t;
        auto it=upper_bound(v.begin(),v.end(),t);
        if(it==v.begin()){
            cout<<"-1\n";
            continue;
        }
        it--;
        cout<<*it<<"\n";
        v.erase(it);
    }
}
    → Reply
»
16 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

HELP, Can anyone help me why this is giving the wrong answer Submission for the problem Restaurant Customers. I use sorting + binary search.

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the idea of the solution (27.Maximum Subarray Sum II)

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Movie Festival """" DP Soltuion """" : https://github.com/Ylandolsi/CSES/blob/main/Movie%20Festival.cpp

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply