Skip to content

CSES Editorial on Searching and Sorting

This is the CSES Editorial Section on Searching and Sorting problems. Entire Problem list can be found here.

Editorials

Distinct Numbers

Problem Link.

Use set to store the distinct numbers. Testcases are designed such a way that the usage of unordered_set creates a \(O(n^2)\) blow-up. Read here.

Code 
int main () {
    int n;
    cin >> n;

    set<int> s;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        s.insert(x);
    }

    cout << s.size() << endl;

    return 0;
}
Apartments

After sorting both the array, use a two pointer approach, do j++ while (j < m and b[j] < a[i] - k), then the first element is the apartment matched with a[i] if b[j] <= a[i] + k still holds true. If that's the case do j++ to select the next apartment and do i++ for the next candidate.

code 
void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int b[m];
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }

    sort(a, a + n);
    sort(b, b + m);

    int assigned = 0;

    for (int i = 0, j = 0; i < n; i++) {
        while (j < m and b[j] < a[i] - k) {
            j++;
        }

        if (j < m and b[j] <= a[i] + k) {
            assigned++; j++;
        }
    }

    cout << assigned << endl;
}
Ferris Wheel

We need to maximize the number of pairs, then the answer would be \(n -\) number of pairs many boats needed. Each boat has \(x\) as the total capacity. We start two pointers at \(i = 0\) and \(j = n - 1\). While we have while (i < j and (p[i] + p[j] > x)) j--; then if i < j then we can choose two pairs, we do pairs++ and j--, i++. At the end we do cout << n - pairs << endl;.

Code 
void solve() {
    int n, x;
    cin >> n >> x;
    int p[n];

    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    sort(p, p + n);

    int pairs = 0;

    for (int i = 0, j = n - 1; i < j;) {
        // maximize the number of pairs
        while (i < j and (p[i] + p[j] > x)) j--;
        if (i >= j) {
            break;
        }

        pairs++; j--; i++;
    }

    cout << n - pairs << endl;
}
Concert Tickets

We need multiset to store the ticket values. As soon as some query comes, we need to give output to the lower_bound from the set and then remove it from the set. For the lower_bound to work properly we need a multiset<int, greater<int>> h;.

Code 
void solve() {
    int n, m;
    cin >> n >> m;

    multiset<int, greater<int>> h;

    int t[m];

    for (int i = 0; i < n; i++) {
        int x; cin >> x; h.insert(x);
    }

    for (int i = 0; i < m; i++) {
        cin >> t[i];
    }

    for (int j = 0; j < m; j++) {
        auto it = h.lower_bound(t[j]);

        if (it != h.end()) {
            cout << *it << endl;
            h.erase(it);
        } else {
            cout << -1 << endl;
        }
    }
}
Restaurant Customers

Add each of the starting and ending time in some list. Then do a +1 for incoming public and a -1 for the outgoing public. This will store the maximum public present at a given time \(t\).

Code 
void solve() {
    int n;
    cin >> n;

    vector<pair<int, int>> time_count;

    for (int i = 0; i < n; i++) {
        pair<int, int> joining;
        cin >> joining.first; joining.second = 1;

        pair<int, int> leaving;
        cin >> leaving.first; leaving.second = -1;

        time_count.push_back(joining);
        time_count.push_back(leaving);
    }

    std::sort(time_count.begin(), time_count.end(), [](const auto a, const auto b) {
        return a.first < b.first;
    });

    int max_count = INT_MIN;
    int total_cnt = 0;

    for (auto pairs:time_count) {
        total_cnt += pairs.second;
        max_count = std::max(total_cnt, max_count);
    }

    cout << max_count << endl;
}
Movie Festival

Simple greedy strategy is enough to solve this. Same problem as interval scheduling on classic algorithms text-books. Sort based on the ending time, then select the earliest finishing movie, and reject conflicting timing movies.

First we count how many removals we need (removals of conflicting movies). In our approch we sort them via their ending time, then we remove the longer event if there is a conflict. We update the removal counter, at the end \(n - \text{removals}\) is our solution.

Code 
void solve() {

    // classic interval scheduling problem,
    // sort based on the ending time and choose the maximum

    unsigned long long int n;
    cin >> n;

    pair<unsigned long long int, unsigned long long int> a[n];

    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }

    std::sort(a, a + n, [](const auto a, const auto b) {
        return a.second < b.second;
    });

    int removals = 0;

    int i = 0;
    while (i < n - 1) {
        if (a[i].second > a[i + 1].first) {
            // this is where there is a conflict
            a[i + 1] = a[i];
            removals++;
        }

        i++;
    }

    std::cout << n - removals << std::endl;
}
Sum of Two Values

Basic two sum - equivalent problem. Create a map and store the <a[i], i> inside if you don't find x - a[i] inside map. Otherwise return i, map[x - a[i]] the first time you find it.

Code 
void solve() {
    int n, x;
    cin >> n >> x;

    int a[n];
    map<int, int> mp;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (mp.find(x - a[i]) == mp.end()) {
            mp.insert({a[i], i});
        } else {
            cout << i + 1 << " " << mp[x - a[i]] + 1 << endl;
            return;
        }
    }

    cout << "IMPOSSIBLE" << endl;
}
Maximum Subarray Sum

Kedane's algorithm is to be followed for a \(O(n)\) submission. There will be some edge cases to sort through.

Code 
void solve() {
    long long int n; cin >> n;

    long long int sum = 0;
    long long int max_sum = -1;

    long long int max_elem = LLONG_MIN;

    for (long long int i = 0; i < n; i++) {
        long long int x; cin >> x;
        max_elem = std::max(max_elem, x);

        sum += x;

        if (sum < 0) sum = 0; 
        max_sum = std::max(sum, max_sum);
    }

    long long int ans = max_sum ? (max_sum) : max_elem;
    cout << ans << endl;
}
Stick Lengths

It is an well known problem, we need to change everything to median. Then we find out the cost.

Code 
void solve() {
    long long int n; cin >> n;
    long long int p[n];


    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    sort(p, p + n);

    long long int cost = 0;
    long long int median = p[n / 2];

    for (long long int i = n - 1; i >= 0; i--) {
        cost += abs(median - p[i]);
    }

    cout << cost << endl;
}
Missing Coin Sum

Maintain a variable called looking_for and set it to \(1\), to start with. As the array is sorted if the first element is \(> 1\) then there is no chance we find \(1\), hence \(1\) is the smallest answer.

Then we move on to second element, say the second element is \(x \neq 2\), then \(2\) must be the smallest answer. Suppose \(2\) is present at the second location, then we don't need to look for \(3\), hence we update looking_for += 2 (a[i]). Suppose the next element is again \(2\) then we update the looking_for by \(2 (a[i])\), hence now we'll be looking_for \(5\).

Suppose the next element is \(x_{4}\). Suppose \(x_4 <\) looking_for. That means we don't find this element in the array. So that should be the minimum answer.

Code 
void solve() {
    unsigned long long int n; cin >> n;

    unsigned long long int a[n];

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a, a + n);

    unsigned long long int looking_for = 1;
    for (int i = 0; i < n; i++) {
        if (looking_for < a[i]) {
            cout << looking_for << endl;
            return;
        }

        looking_for += a[i];
    }

    cout << looking_for << endl;
}
Collecting Numbers I

We first store all the element's index as a reverse lookup table. Then we iterate over a variable currently_looking. If currently_looking - 1 is present left of currently_looking then we can include in the current run, then we go to currently_looking + 1,

If we find some currently_looking - 1 is present right of currently_looking that means we hit a break. We resume operation from currently_looking + 1 after updating the correct collection count collections.

Code 
void solve() {
    int n;
    cin >> n;
    long long int a[n];

    map<long long int, int> mp;

    for (int i = 0; i < n; i++) {
        cin >> a[i]; mp.insert({a[i], i});
    }

    int collections = 1;
    int currently_looking = 2;

    while (currently_looking <= n) {
        if (mp[currently_looking] < mp[currently_looking - 1]) {
            collections++;
        }

        currently_looking++;
    }

    cout << collections << endl;
}
Playlist

Use a map<a[i], count(a[i])> for subarray \(a[i \dots j]\) such that all \(a[k] \in (i, j)\) is unique. Leaving each a[i], decrease the count from the map.

Solution 
void solve() {
    int n;
    cin >> n;

    int a[n];

    map<int, int> mp;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int mxcnt = -1;
    for (int i = 0, j = 0; i < n; i++) {
        while (j < n and mp[a[j]] < 1) {
            mp[a[j]]++;
            j++;
        }

        mxcnt = std::max(mxcnt, j - i);
        mp[a[i]]--;
    }

    std::cout << mxcnt << std::endl;
}
Towers

Use a multiset set store each a[i]. Find the upper_bound on the a[i], then either place on top of a bigger a[i] (best is the upper_bound), or start out a new tower, at the end size of the set is the answer.

Solution 
void solve() {
    int n;
    cin >> n; int a[n];

    multiset<int> st;

    for (int i = 0; i < n; i++) {
        cin >> a[i];

        // a[i] is the current cube
        // either place on top of a bigger a[i]
        // or start out a new order
        auto ub = st.upper_bound(a[i]);
        if (ub == st.end()) {
            st.insert(a[i]);
        } else {
            st.erase(ub);
            st.insert(a[i]);
        }
    }

    std::cout << st.size() << std::endl;
}

There is also another solution (quite genious solution), that is to count the LIS of the sequence. Size of the LIS is the answer. Following is the reason, you can push smaller cubes on top of the larger cubes, hence counting the LIS on the size of the cubes will show the number of towers.

Solution #2 
void solve1() {
    int n;
    cin >> n; int a[n];


    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> v;
    for (int i = 0; i < n; i++) {
        int ub = upper_bound(v.begin(), v.end(), a[i]) - v.begin();
        if (ub < v.size()) {
        v[ub] = a[i]; 
        } else {
            v.push_back(a[i]);
        }
    }

    std::cout << v.size() << std::endl;
}
Subarray Sum I, II

We propose one solutions that'll cover both the I and II problems. First we build the perfix sum array. Then for any location \(i\) we find if \(\text{prefix}[i] - \text{target}\) is present in the map or not? If that is present that means from end of that location \(j + 1\) to \(i\) there is an sub-array whoose sum is \(\text{target}\).

Comments

This comments system is powered by GitHub Discussions