USACO 2022 February Contest, Silver Problem 3. Email Filing

USACO 2022 February Contest, Silver Problem 3. Email Filing

Farmer John has fallen behind on organizing his inbox. The way his screen is organized, there is a vertical list of folders on the left side of the screen and a vertical list of emails on the right side of the screen. There are MM total folders, numbered 1M1…M (1M104)1≤M≤104). His inbox currently contains NN emails numbered 1N1…N (1N1051≤N≤105); the iith email needs to be filed into folder fifi (1fiM1≤fi≤M).

FJ's screen is rather small, so he can only view KK (1Kmin(N,M)1≤K≤min(N,M)) folders and KK emails at once. Initially, his screen starts out displaying folders 1K1…K on the left and emails 1K1…K on the right. To access other folders and emails, he needs to scroll through these respective lists. For example, if he scrolls down one position in the list of folders, his screen will display folders 2K+12…K+1, and then scrolling down one position further it will display folders 3K+23…K+2. When FJ drags an email into a folder, the email disappears from the email list, and the emails after the one that disappeared shift up by one position. For example, if emails 1,2,3,4,51,2,3,4,5 are currently displayed and FJ drags email 3 into its appropriate folder, the email list will now show emails 1,2,4,5,61,2,4,5,6. FJ can only drag an email into the folder to which it needs to be filed.

Unfortunately, the scroll wheel on FJ's mouse is broken, and he can only scroll downwards, not upwards. The only way he can achieve some semblance of upward scrolling is if he is viewing the last set of KK emails in his email list, and he files one of these. In this case, the email list will again show the last KK emails that haven't yet been filed, effectively scrolling the top email up by one. If there are fewer than KK emails remaining, then all of them will be displayed.

Please help FJ determine if it is possible to file all of his emails.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains TT (1T101≤T≤10), the number of subcases in this input, all of which must be solved correctly to solve the input case. The TT subcases then follow. For each subcase, the first line of input contains MMNN, and KK. The next line contains f1fNf1…fN.It is guaranteed that the sum of MM over all subcases does not exceed 104104, and that the sum of NN over all subcases does not exceed 105105.

OUTPUT FORMAT (print output to the terminal / stdout):

Output TT lines, each one either containing either YES or NO, specifying whether FJ can successfully file all his emails in each of the TT subcases.

SAMPLE INPUT:

6
5 5 1
1 2 3 4 5
5 5 1
1 2 3 5 4
5 5 1
1 2 4 5 3
5 5 2
1 2 4 5 3
3 10 2
1 3 2 1 3 2 1 3 2 1
3 10 1
1 3 2 1 3 2 1 3 2 1

SAMPLE OUTPUT:

YES
YES
NO
YES
YES
NO

SCORING:

 

  • In inputs 2-10, the sum of MM over all subcases does not exceed 103103.
  • In inputs 11-12, no additional constraints.

 

Problem credits: Brian Dean

USACO 2022 February Contest, Silver Problem 3. Email Filing 题解(翰林国际教育提供,仅供参考)

题解请注册登录查看

[/hide]

(Analysis by Nick Wu)

Because we cannot scroll up on the folders, we have some constraints on how far down we must scroll in the emails before we can scroll down on the list of folders. Specifically, we must always scroll down to at least email EE if the topmost folder currently being looked at will need to have email EE filed to it.

Therefore, as long as we do some bookkeeping, we can simulate this process carefully. We'll maintain a collection of emails that have not yet been filed and are currently being scrolled through, as well as the collection of emails that have been skipped so far. We'll also keep track of the earliest point of time when an email can be filed.

We'll loop through the folders in order, keeping track of the topmost folder. We'll also loop through the emails in order until we get to the last email that needs to be filed for the given topmost folder. If having that email on screen would cause the window to overflow, we have to mark the topmost email as skipped. Afterwards, if we can file the email, we should do so immediately. Otherwise, it sits in the window.

In the event we have looped through all the emails, we also have to simulate the behavior of scrolling up through the emails that we previously skipped.

My C++ code:

#include <bits/stdc++.h>
 
using namespace std;
 
void rsolve() {
  int nfolder, nemail, windowsz;
  cin >> nfolder >> nemail >> windowsz;
  vector<int> emailtofolder(nemail);
  vector<vector<int>> foldertoemail(nfolder);
  vector<vector<int>> filetiming(nfolder);
  vector<bool> filed(nemail);
  vector<bool> skipped(nemail);
  vector<bool> inwindow(nemail);
  for(int i = 0; i < nemail; i++) {
    cin >> emailtofolder[i];
    filetiming[max(0, --emailtofolder[i] - windowsz + 1)].push_back(i);
    foldertoemail[emailtofolder[i]].push_back(i);
  }
  int currentemail = 0;
  int lhsemail = 0;
  int numinwindow = 0;
  int rhsemail = nemail-1;
  auto fileemail = [&](int id) -> void {
    if(inwindow[id]) {
      inwindow[id] = false;
      numinwindow--;
    }
    assert(!filed[id]);
    filed[id] = true;
  };
  int bottom = 0;
  for(int i = 0; i < nfolder; i++) {
    // file anything that can be newly filed
    if(i > bottom && i + windowsz <= nfolder) bottom++;
    for(int out: filetiming[i]) if(inwindow[out]) fileemail(out);
    while(foldertoemail[i].size() && currentemail <= foldertoemail[i].back()) {
      // the window is full so in order to consider this email, we must scroll past the current one
      if(numinwindow == windowsz) {
        while(!inwindow[lhsemail]) lhsemail++;
        skipped[lhsemail] = true;
        inwindow[lhsemail] = false;
        numinwindow--;
      }
      if(emailtofolder[currentemail] >= i && emailtofolder[currentemail] <= i + windowsz - 1) {
        // can file
        filed[currentemail++] = true;
        continue;
      }
      inwindow[currentemail++] = true; numinwindow++;
    }
    // scroll through emails that would be implicitly loaded
    while(currentemail < nemail && numinwindow < windowsz) {
      if(emailtofolder[currentemail] >= i && emailtofolder[currentemail] <= i + windowsz - 1) {
        // can file
        filed[currentemail++] = true;
        continue;
      }
      inwindow[currentemail++] = true; numinwindow++;
    }
    // scroll up emails since we've hit the end
    if(currentemail == nemail) {
      while(numinwindow < windowsz) {
        if(rhsemail < 0) break;
        if(!skipped[rhsemail]) {
          rhsemail--;
          continue;
        }
        if(emailtofolder[rhsemail] < bottom) {
          cout << "NO\n";
          return;
        }
        if(emailtofolder[rhsemail] <= bottom + windowsz - 1) {
          filed[rhsemail--] = true;
          continue;
        }
        inwindow[rhsemail--] = true; numinwindow++;
      }
    }
  }
  for(auto out: filed) {
    if(!out) {
      cout << "NO\n";
      return;
    }
  }
  cout << "YES\n";
}
 
void solve() {
  int t;
  cin >> t;
  while(t--) rsolve();
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
}

Danny Mittal's Java code:

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class EmailFiling {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        for (int t = Integer.parseInt(in.readLine()); t > 0; t--) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            int m = Integer.parseInt(tokenizer.nextToken());
            int n = Integer.parseInt(tokenizer.nextToken());
            int k = Integer.parseInt(tokenizer.nextToken());
            tokenizer = new StringTokenizer(in.readLine());
            int[] folder = new int[n];
            int[] rem = new int[m];
            for (int j = 0; j < n; j++) {
                folder[j] = Integer.parseInt(tokenizer.nextToken()) - 1;
                rem[folder[j]]++;
            }
            int firstFolder = 0;
            int firstEmail = 0;
            int lastEmail = k - 1;
            boolean[] filed = new boolean[n];
            PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(j -> folder[j]));
            for (int j = 0; j < k; j++) {
                pq.add(j);
            }
            while (lastEmail < n - 1 && firstFolder < m) {
                if (rem[firstFolder] == 0) {
                    firstFolder++;
                } else if (!pq.isEmpty() && folder[pq.peek()] < firstFolder + k) {
                    int j = pq.remove();
                    if (j >= firstEmail) {
                        filed[j] = true;
                        rem[folder[j]]--;
                        lastEmail++;
                        pq.add(lastEmail);
                    }
                } else {
                    while (firstEmail < n && filed[firstEmail]) {
                        firstEmail++;
                    }
                    firstEmail++;
                    lastEmail++;
                    pq.add(lastEmail);
                }
            }
            String answer = "YES";
            while (firstFolder < m) {
                if (rem[firstFolder] == 0) {
                    firstFolder++;
                } else {
                    if (pq.isEmpty()) {
                        answer = "NO";
                        break;
                    }
                    int j = pq.remove();
                    if (j >= firstEmail && !filed[j]) {
                        if (folder[j] >= firstFolder + k) {
                            answer = "NO";
                            break;
                        }
                        filed[j] = true;
                        rem[folder[j]]--;
                        while (firstEmail > 0) {
                            firstEmail--;
                            if (!filed[firstEmail]) {
                                pq.add(firstEmail);
                                break;
                            }
                        }
                    }
                }
            }
            out.append(answer).append('\n');
        }
        System.out.print(out);
    }
}

[/hide]

翰林国际教育资讯二维码