Official

C - Robot Factory Editorial by en_translator

One can prove that, if he can assemble \(K\) robots that do not fall over, then the objective can be achieved in the following way:

  • Choose the \(K\) lightest head parts and \(K\) heaviest body parts, and destroy all the others.
  • Pair the remaining parts from the lightest from each group.

Proof

Let \((i,j)\) denote pairing the \(i\)-th lightest head part and \(j\)-th lightest body part. (Also we assume that the head parts and body parts are sorted in ascending order of their weights and simply call them head \(i\) etc.)

Take a possible combination of \(K\) robots that do not fall over: \((a _ 1,b _ 1),(a _ 2,b _ 2),\ldots,(a _ K,b _ K)\ (a _ 1\lt a _ 2\lt\cdots\lt a _ K)\).

Since \(i\le a _ i\), combination \((1,b _ 1),(2,b _ 2),\ldots,(K,b _ K)\) is also a valid set of \(K\) robots.

When there is an \(i\) with \(b _ i\gt b _ {i+1}\), we claim that we can swap \((i,b _ i)\) and \((i+1,b _ {i+1})\) into \((i+1,b _ i)\) and \((i,b _ {i+1})\) without losing the validity.

Proof

Due to how we assigned numbers to the parts, and the property that robots \((i,b _ i)\) and \((i+1,b _ {i+1})\) do not fall over, we see that:

  • Head \(i\) is not heavier than head \(i+1\).
  • Head \(i+1\) is not heavier than body \(b_{i+1}\).
  • Since \(b _ i\gt b _ {i+1}\), body \(b_{i+1}\) is not heavier than body \(b _ i\).

Hence, the robots assembled as \((i+1,b _ i)\) and \((i,b _ {i+1})\) do not fall over neither.

Thus, for the sequence \(b ^ \prime=(b ^ \prime _ 1,b ^ \prime _ 2,\ldots,b ^ \prime _ K)\) obtained by sorting \(b=(b _ 1,b _ 2,\ldots,b _ K)\) in ascending order, the \(K\) robots obtained as \((1,b ^ \prime _ 1),(2,b ^ \prime _ 2),\ldots,(K,b ^ \prime _ K)\) do not fall over.

Since \(b ^ \prime _ i\le i-K+N\), we can assemble \(K\) robots that do not fall over as \((1,N-K+1),(2,N-K+2),\ldots,(K,N)\). \(\quad\Box\)

Thus, if any of the \(K\) robots obtained that way falls over, then we may print No; otherwise, we may print Yes.

The following is sample code.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> H(N), B(M);
    for (auto&& h : H)
        cin >> h;
    for (auto&& b : B)
        cin >> b;

    // Sort from lighter to heavier
    ranges::sort(H);
    ranges::sort(B);

    // Inspect the first K heads and last K bodies in order.  Any pair has heavier head than body, print No; otherwise print Yes.
    cout << (transform_reduce(begin(H), begin(H) + K, end(B) - K, false, logical_or{}, greater{}) ? "No" : "Yes") << endl;
    return 0;
}

N, M, K = map(int, input().split())

H = list(map(int, input().split()))
B = list(map(int, input().split()))

# Sort from lighter to heavier
H.sort()
B.sort()

# Inspect the first K heads and last K bodies in order.  Any pair has heavier head than body, print No; otherwise print Yes.
if all(h <= b for h, b in zip(H[:K], B[-K:])):
    print('Yes')
else:
    print('No')

posted:
last update: