Home » 国际竞赛 » Details

USACO 2022 February Contest, Silver Problem 3. Email Filing

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午5:19

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

M

total folders, numbered

1 \dots M

(

1 \leq M \leq 10^{4})

. His inbox currently contains

N

emails numbered

1 \dots N

(

1 \leq N \leq 10^{5}

); the

i

th email needs to be filed into folder

f_{i}

(

1 \leq f_{i} \leq M

FJ's screen is rather small, so he can only view $K$ ( $1 \leq K \leq min (N, M)$ ) folders and $K$ emails at once. Initially, his screen starts out displaying folders $1 \dots K$ on the left and emails $1 \dots 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 $2 \dots K + 1$ , and then scrolling down one position further it will display folders $3 \dots 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, 5$ are currently displayed and FJ drags email 3 into its appropriate folder, the email list will now show emails $1, 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 $K$ emails in his email list, and he files one of these. In this case, the email list will again show the last $K$ emails that haven't yet been filed, effectively scrolling the top email up by one. If there are fewer than $K$ 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 $T$ ( $1 \leq T \leq 10$ ), the number of subcases in this input, all of which must be solved correctly to solve the input case. The $T$ subcases then follow. For each subcase, the first line of input contains $M$ , $N$ , and $K$ . The next line contains $f_{1} \dots f_{N}$ .It is guaranteed that the sum of $M$ over all subcases does not exceed $10^{4}$ , and that the sum of $N$ over all subcases does not exceed $10^{5}$ .

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

Output $T$ lines, each one either containing either YES or NO, specifying whether FJ can successfully file all his emails in each of the $T$ 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 $M$ over all subcases does not exceed $10^{3}$ .
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 $E$ if the topmost folder currently being looked at will need to have email $E$ 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]