USACO 2022 February Contest Silver Division - Email Filing

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We notice that for each folder, we cannot scroll above it if there are still emails to be put in that folder that we have not taken. We sweep the vector in two ways: from left to right using frequency arrays to remember the last \(k\) emails that were not taken, while increasing the index of the folder we are on. If at the end we still have emails that were not taken, we sweep from right to left, this time remembering the last \(k\) emails that were not taken. When we have no more emails/we cannot put emails in folders, we stop and have an answer.

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>
using namespace std;

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

    vector<int> emails(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> emails[i];
    }

    vector<int> frq(m+1);
    for (int i = 1; i <= n; i++) {
        frq[emails[i]]++;
    }

    int fi = 1;

    multiset<pair<int, int> > remaining_mails, inverted;
    set<pair<int, int> > leftovers;

    for (int i = 1; i <= k; i++) {
        remaining_mails.insert({emails[i], i});
        inverted.insert({i, emails[i]});
    }

    int pos = k+1;

    bool bad = 0;

    while (true) {
        bool oki = 0;

        // progress with folders
        while (fi + k - 1 < m && frq[fi] == 0) {
            fi++;
        }

        // remove eligible mails
        auto x = remaining_mails.lower_bound({fi, 0});
        while (x != remaining_mails.end() && (*x).first <= fi + k - 1) {
            frq[(*x).first]--;
            pair<int, int> px = *x;
            remaining_mails.erase(x);
            swap(px.first, px.second);
            inverted.erase(px);
            oki = 1;
            while (fi + k - 1 < m && frq[fi] == 0) {
                fi++;
            }
            x = remaining_mails.lower_bound({fi, 0});
        }
        // move forward with mails
        while (pos <= n && remaining_mails.size() < k) {
            remaining_mails.insert({emails[pos], pos});
            inverted.insert({pos, emails[pos]});
            pos++;
            oki = 1;
        }
        // if we have too many mails, we need to move down with mouse
        if (!inverted.empty() && remaining_mails.size() == k && oki == 0) {
            pair<int, int> px = *inverted.begin();
            leftovers.insert(px);
            inverted.erase(px);
            swap(px.first, px.second);
            remaining_mails.erase(px);
            oki = 1;
        }
        // simulating scrolling up
        while (pos == n+1 && remaining_mails.size() < k && !leftovers.empty() && ((*leftovers.rbegin()).second) >= fi && ((*leftovers.rbegin()).second) <= fi + k - 1) {
            pair<int, int> px = *leftovers.rbegin();
            leftovers.erase(px);
            frq[px.second]--;
            while (fi + k - 1 < m && frq[fi] == 0) {
                fi++;
            }
            oki = 1;
        }

        if (!oki) {
            break;
        }
    }

    if (pos <= n || remaining_mails.size() || leftovers.size()) {
        bad = 1;
    }
    cout << (bad == 1 ? "NO" : "YES") << '\n';
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }
    return 0;
}