Ранжирование резюме

1. Идея

Нужно обработать каждого кандидата независимо:

1. проверить, проходит ли он первичный фильтр;
2. если проходит — посчитать его rating;
3. сохранить кандидата для последующей сортировки.

После этого остаётся отсортировать всех прошедших кандидатов:

• по убыванию rating;
• при равенстве рейтинга — по имени в лексикографическом порядке.

Если никто не прошёл, выводим NO CANDIDATES.

2. Наблюдения

Наблюдение 1. Проверка обязательных навыков

У вакансии есть множество обязательных навыков required, а у кандидата — множество его навыков.

Кандидат проходит по навыкам тогда и только тогда, когда каждый навык из required содержится у кандидата.

Для такой проверки удобно хранить навыки кандидата в set:

• в C++ — set<string>;
• в Python — set.

Тогда проверка каждого обязательного навыка выполняется быстро и просто.

Наблюдение 2. Что такое matched_optional

По условию:

matched_optional — это количество навыков кандидата, которые не входят в required.

То есть среди всех навыков кандидата нужно посчитать те, которых нет в обязательном списке.

Так как у кандидата навыки различны, достаточно просто пройти по его списку навыков и увеличить счётчик для каждого навыка, не принадлежащего required.

Наблюдение 3. Как удобно сортировать

Нужно сортировать по убыванию rating, а имя — по возрастанию.

Удобный приём: сохранять пару (-rating, name). Тогда обычная сортировка по возрастанию даст нужный порядок:

• больший rating превращается в меньший -rating, значит окажется раньше;
• при равенстве первого элемента пары имена будут отсортированы по возрастанию автоматически.

Наблюдение 4. Пустая строка во входе

Если r = 0, строка с обязательными навыками всё равно присутствует, но она пустая. Аналогично, если s = 0, строка навыков кандидата тоже пустая.

Эталонные решения читают эти строки через разбиение на слова:

• пустая строка превращается в пустой список;
• это как раз то, что нужно.

3. Алгоритм

1. Считать min_exp, min_score, max_salary, r.
2. Считать список обязательных навыков и сохранить его в множество required.
3. Считать число кандидатов n.

4. Завести список passed для кандидатов, прошедших фильтр.

5. Для каждого кандидата:

   1. считать name, exp, score, salary, s;
   2. считать список его навыков skills;
   3. построить множество skill_set;
   4. проверить базовые условия:
      • exp >= min_exp;
      • score >= min_score;
      • salary <= max_salary;
   5. если они выполнены, проверить наличие всех навыков из required в skill_set;
   6. если кандидат прошёл:
      • посчитать matched_optional — число навыков из skills, которых нет в required;
      • вычислить rating = score * 10 + matched_optional * 5 + exp * 2 - salary // 10000;
      • сохранить пару (-rating, name) в passed.

6. Отсортировать passed.

7. Если passed пуст:
   • вывести NO CANDIDATES.
8. Иначе вывести имена кандидатов по порядку.

4. Почему это работает

Докажем, что алгоритм выводит правильный ответ.

1. Фильтрация выполняется точно по условию

Для каждого кандидата алгоритм отдельно проверяет:

• достаточен ли опыт;
• достаточен ли балл;
• не слишком ли велика зарплата;
• содержатся ли все обязательные навыки среди навыков кандидата.

Это в точности совпадает с определением первичного фильтра из условия.
Значит, кандидат попадает в список passed тогда и только тогда, когда действительно проходит фильтр.

2. matched_optional считается правильно

Алгоритм проходит по всем навыкам кандидата и считает те, которые не входят в required.

По условию именно это и требуется: количество навыков кандидата, не являющихся обязательными.
Следовательно, значение matched_optional вычисляется верно.

3. rating считается по заданной формуле

Для каждого прошедшего кандидата алгоритм вычисляет:

score * 10 + matched_optional * 5 + exp * 2 - salary // 10000

Это полностью совпадает с формулой из условия.
Значит, рейтинг каждого кандидата найден правильно.

4. Сортировка даёт нужный порядок

В список сохраняется пара (-rating, name).

При стандартной сортировке пар:

• сначала сравнивается -rating, поэтому кандидаты с большим рейтингом идут раньше;
• если рейтинги равны, сравниваются имена, поэтому раньше идёт лексикографически меньшее имя.

Это ровно тот порядок, который требуется в задаче.

Из пунктов 1–4 следует, что алгоритм выводит всех и только тех кандидатов, которые должны быть выведены, и в правильном порядке.

5. Сложность

Пусть:

• n — число кандидатов;
• r — число обязательных навыков;
• s — число навыков у текущего кандидата.

Для одного кандидата:

• чтение и построение множества навыков: O(s log s) для set в C++ и в среднем O(s) для set в Python;
• проверка всех обязательных навыков: O(r log s) в C++ и в среднем O(r) в Python;
• подсчёт matched_optional: O(s log r) в C++ и в среднем O(s) в Python.

Так как по условию r <= 20 и s <= 20, это очень мало, и решение легко укладывается в ограничения.

Сортировка прошедших кандидатов занимает O(k log k), где k — количество прошедших кандидатов, k <= n.

Итоговая сложность:

• в C++: O(n * (r + s) * log 20 + k log k), что на практике фактически O(n + k log k);
• в Python: в среднем O(n * (r + s) + k log k).

По памяти:

• O(k) на хранение прошедших кандидатов.

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    int min_exp, min_score, r;
    long long max_salary;
    cin >> min_exp >> min_score >> max_salary >> r;

    set<string> required;
    for (int i = 0; i < r; i++) {
        string skill;
        cin >> skill;
        required.insert(skill);
    }

    int n;
    cin >> n;

    vector<pair<long long, string>> passed;

    for (int i = 0; i < n; i++) {
        string name;
        int exp, score, s;
        long long salary;
        cin >> name >> exp >> score >> salary >> s;

        vector<string> skills(s);
        set<string> skill_set;
        for (int j = 0; j < s; j++) {
            cin >> skills[j];
            skill_set.insert(skills[j]);
        }

        bool ok = true;
        if (exp < min_exp) ok = false;
        if (score < min_score) ok = false;
        if (salary > max_salary) ok = false;

        if (ok) {
            for (const string& need : required) {
                if (skill_set.find(need) == skill_set.end()) {
                    ok = false;
                    break;
                }
            }
        }

        if (ok) {
            int matched_optional = 0;
            for (const string& skill : skills) {
                if (required.find(skill) == required.end()) {
                    matched_optional++;
                }
            }

            long long rating = 1LL * score * 10 + 1LL * matched_optional * 5 + 1LL * exp * 2 - salary / 10000;
            passed.push_back({-rating, name});
        }
    }

    sort(passed.begin(), passed.end());

    if (passed.empty()) {
        cout << "NO CANDIDATES\n";
    } else {
        for (const auto& p : passed) {
            cout << p.second << "\n";
        }
    }

    return 0;
}

7. Код на Python 3

min_exp, min_score, max_salary, r = map(int, input().split())

required_line = input().split()
required = set(required_line)

n = int(input())

passed = []

for _ in range(n):
    name, exp, score, salary, s = input().split()
    exp = int(exp)
    score = int(score)
    salary = int(salary)
    s = int(s)

    skills = input().split()
    skill_set = set(skills)

    ok = True
    if exp < min_exp:
        ok = False
    if score < min_score:
        ok = False
    if salary > max_salary:
        ok = False

    if ok:
        for need in required:
            if need not in skill_set:
                ok = False
                break

    if ok:
        matched_optional = 0
        for skill in skills:
            if skill not in required:
                matched_optional += 1

        rating = score * 10 + matched_optional * 5 + exp * 2 - salary // 10000
        passed.append((-rating, name))

passed.sort()

if not passed:
    print("NO CANDIDATES")
else:
    for _, name in passed:
        print(name)