Разбор задачи «Коллекция для витрины»

Идея задачи

Нам дан массив a. Можно переставить его элементы в любом порядке. После этого красота массива определяется как

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

Требуется максимизировать это значение.

На первый взгляд задача выглядит необычно: обычно LIS ищут в уже фиксированном массиве, а здесь массив можно переставить как угодно. Значит, нужно не искать подпоследовательность в данном порядке, а понять, какой вклад в ответ дают разные значения в зависимости от их количества.

Главное наблюдение

Пусть некоторое число встречается:

• ровно один раз;
• хотя бы два раза.

Именно это и определяет его роль в ответе.

Случай 1. Число встречается хотя бы два раза

Тогда одну его копию можно использовать для роста подпоследовательности слева направо, а вторую — для роста подпоследовательности справа налево.

Иначе говоря, такое значение может «помочь» сразу обеим сторонам.

Значит, каждое различное значение, встречающееся хотя бы два раза, гарантированно даёт вклад +1 в ответ.

Случай 2. Число встречается ровно один раз

Такое значение можно отдать только одной стороне:

• либо в возрастающую подпоследовательность слева направо,
• либо в возрастающую подпоследовательность справа налево.

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

Поэтому все такие значения нужно делить между двумя сторонами как можно более равномерно. Если одиночных значений one, то в минимум из двух сторон попадёт

ceil(one / 2).

В целочисленной арифметике это записывается так:

(one + 1) / 2 для C++ и (one + 1) // 2 для Python.

Формула ответа

Обозначим:

• two — количество различных значений, которые встречаются не меньше двух раз;
• one — количество различных значений, которые встречаются ровно один раз.

Тогда ответ равен:

two + ceil(one / 2)

или, что то же самое:

two + (one + 1) / 2.

Почему формула верна

Разберём это аккуратно.

Шаг 1. Все значения с частотой не меньше двух всегда выгодны

Если значение встречается хотя бы дважды, мы можем использовать две его копии в разных «ролях»:

• одна поддерживает рост для одной LIS,
• вторая — для другой.

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

Их вклад — two.

Шаг 2. Одиночные значения конфликтуют между сторонами

Если значение одно, то использовать его для двух направлений одновременно нельзя. Значит, одиночные значения придётся делить.

Чтобы максимум у минимума был наибольшим, делить нужно как можно поровну.

Например:

• если одиночных значений 4, то можно распределить их как 2 и 2, вклад в минимум будет 2;
• если одиночных значений 5, то лучшее распределение — 3 и 2, вклад в минимум будет 3.

Именно это и есть ceil(one / 2).

Шаг 3. Вместе получаем итог

Сначала обе стороны получают по всем «хорошим повторяющимся» значениям: это two.

Потом к ним добавляется равномерно распределённая часть одиночных значений: это ceil(one / 2).

Итак,

answer = two + ceil(one / 2).

Как это реализовать

Нужно для каждого теста:

1. посчитать частоты всех чисел;
2. пройти по этим частотам;
3. если частота равна 1, увеличить one;
4. если частота не меньше 2, увеличить two;
5. вывести two + (one + 1) / 2.

Сделать это можно:

• либо через сортировку массива;
• либо через словарь / map / Counter.

Оба способа подходят.

Разбор на примерах

Пример 1

[1, 1, 2, 3]

• число 1 встречается два раза → two = 1
• числа 2 и 3 встречаются по одному разу → one = 2

Ответ:

1 + ceil(2 / 2) = 1 + 1 = 2

Пример 2

[1, 1, 1, 1]

• только одно значение, и оно встречается не меньше двух раз → two = 1
• одиночных нет → one = 0

Ответ:

1 + 0 = 1

Пример 3

[1, 2, 3]

• все значения одиночные → one = 3
• значений с частотой хотя бы 2 нет → two = 0

Ответ:

0 + ceil(3 / 2) = 2

Решение на C++

Ниже приведена эталонная реализация через сортировку.

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

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

        int one = 0;
        int two = 0;

        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && a[j] == a[i]) {
                j++;
            }

            int cnt = j - i;
            if (cnt == 1) {
                one++;
            } else {
                two++;
            }

            i = j;
        }

        cout << two + (one + 1) / 2 << '\n';
    }

    return 0;
}

Решение на Python

В Python удобно использовать Counter.

from collections import Counter


t = int(input())

for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))

    cnt = Counter(a)

    one = 0
    two = 0

    for x in cnt.values():
        if x == 1:
            one += 1
        else:
            two += 1

    print(two + (one + 1) // 2)

Почему этого достаточно

Мы нигде не строим саму перестановку. Это и не нужно.

Задача спрашивает только максимальное возможное значение красоты, а оно полностью определяется тем,

• сколько значений встречается ровно один раз;
• сколько значений встречается не меньше двух раз.

То есть конкретный порядок нам не важен — важны только частоты.

Оценка сложности

C++-версия через сортировку

Сортировка работает за O(n log n), дальнейший проход — за O(n).

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

O(n log n)

Python-версия через Counter

Подсчёт частот работает в среднем за O(n), проход по словарю — тоже O(n).

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

O(n) в среднем.

Память в обоих случаях — O(n).

Типичные ошибки

Ошибка 1. Считать количество элементов, а не количество различных значений

Нам важно не сколько всего элементов встречается дважды или один раз, а сколько различных чисел имеют такую частоту.

Например, если массив [5, 5, 5, 5], то это не четыре полезных элемента, а одно значение с частотой не меньше двух.

Ошибка 2. Писать one / 2 вместо округления вверх

Если one нечётно, нужно округлять вверх.

Например, при one = 3 вклад равен 2, а не 1.

Поэтому правильно:

• в C++: (one + 1) / 2
• в Python: (one + 1) // 2

Ошибка 3. Пытаться реально строить перестановку

Это лишнее усложнение. Для ответа достаточно только частот.

Итог

Ключевая идея задачи очень компактная:

• каждое значение, встречающееся хотя бы два раза, приносит 1 в ответ;
• одиночные значения делятся между двумя сторонами, поэтому дают ceil(one / 2);
• итоговая формула:

answer = two + ceil(one / 2)

Это и даёт простое и эффективное решение.