Problem: second_hands (2022 quals)

Sandy's store has \(N\) pre-owned clock parts for sale, where the \(i\)th part is of style \(S_i\). The store also has two display cases, each capable of holding at most \(K\) parts. To maximize the aesthetics of Sandy's secondhand second hands, she'd like to put each of the \(N\) parts into one of the two cases so that neither case ends up with two different parts of the same style, and neither case has more than \(K\) parts total. Can you determine if this is possible?

# Constraints

\(1 \leq T \leq 90\)
\(1 \leq N, K, S_i \leq 100\)


# Input Format

Input begins with an integer \(T\), the number of test cases. For each test case, there is first a line containing \(2\) space-separated integers, \(N\) and \(K\). Then, there is a line containing \(N\) space-separated integers, \(S_1, ..., S_N\).


# Output Format

For the \(i\)th test case, print "`Case #i:` " followed by "`YES`" if it's possible to arrange the \(N\) parts into two cases satisfying the description above, or "`NO`" otherwise.


# Sample Explanation

In the first test case, there are \(3\) parts of styles \(1\), \(2\), and \(2\), with the display cases having capacity \(2\). One solution, depicted below, is to put the first and third parts in one display case, and the second part in the other.

{{PHOTO_ID:459254706243127|WIDTH:500}}

In the second test case, there are \(5\) parts of styles \(1\), \(2\), \(3\), \(3\), \(1\), with the display cases having capacity \(3\). One solution, depicted below, is to put the first three parts in one display case, and the last two in the other.

{{PHOTO_ID:1183048075593188|WIDTH:500}}

In the third test case, there are \(5\) parts, but the display cases can each only hold \(2\). Therefore, there is no solution.

In the fourth test case, style \(1\) will always be duplicated in some display case for any given arrangement. Therefore, there is no solution.




Sample input:
5
3 2
1 2 2
5 3
1 2 3 3 1
5 2
1 2 3 4 5
5 5
1 1 2 2 1
1 1
1


Sample output:
Case #1: YES
Case #2: YES
Case #3: NO
Case #4: NO
Case #5: YES


Solution: If \(N > 2K\), then the answer is "`NO`", because we lack the capacity to hold all the parts.

If there are \(3\) parts of the same style, then the answer is "`NO`". By the pigeonhole principle, any assignment of parts to cases will yield a case with two or more parts of the same style.

Otherwise the answer is "`YES`" using the following strategy: First, for any style we have two parts of, put one in each case. Next, evenly distribute the remaining parts (each being a unique style in the store) between the two cases. Informally, this distributes the parts as close to evenly as possible, so we will have enough room in each case.

Formally, one case will have \(\lfloor N/2 \rfloor \) parts and the other will have \(\lceil N/2 \rceil \) parts. Since \(N \le 2K\), we have \(N/2 \le K\), and thus \( \lceil N/2 \rceil  \le \lceil K \rceil = K\) (inequality preserved since \(\lceil x \rceil\) is a nondecreasing function). Having shown \(\lfloor N/2 \rfloor \le \lceil N/2 \rceil \le K\), we see that neither case will exceed capacity.

[See David Harmeyer's solution video here.](https://youtu.be/8Eg2-HIUP-w)


Code: #include <iostream>
using namespace std;

const int LIM = 105;

int N, K;
int S[LIM];

string solve() {
  if (N > 2*K) {
    return "NO";
  }
  int cnt[LIM+1] = {0};
  for (int i = 0; i < N; i++) {
    if (++cnt[S[i]] == 3) {
      return "NO";
    }
  }
  return "YES";
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
      cin >> S[i];
    }
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}