Задачник Базовый курс EN

Ближайший цвет палитры

кластеризация ближайший сосед изображения мемоизация

Палитра уже найдена: k цветов. Осталось раскрасить картинку — каждый пиксель заменить ближайшим цветом палитры — и посчитать, сколько пикселей досталось каждому цвету. «Ближайший» — по обычному расстоянию в пространстве RGB: для цветов (r₁, g₁, b₁) и (r₂, g₂, b₂) сравниваем (r₁ − r₂)² + (g₁ − g₂)² + (b₁ − b₂)². Если два цвета палитры одинаково близки, пиксель достаётся тому, что раньше в списке.

Пиксели в тестах — настоящие фотографии автора сайта.

Вход

В первой строке k (1 ≤ k ≤ 16), во второй — k цветов палитры. В третьей — число пикселей n (1 ≤ n ≤ 100 000), в четвёртой — пиксели. Каждый цвет записан как #rrggbb строчными шестнадцатеричными цифрами.

Выход

k чисел через пробел: сколько пикселей досталось каждому цвету палитры, в порядке палитры.

Примеры

Пример 1

Вход

6
#24260f #504d23 #777260 #c2c3cb #748fab #37709a
43
#0b74ae #1673ac #2a75ad #477cb2 #437cb2 #1870a9 #1e71a7 #0b6ca4 #0067a1 #0f6ca3 #106aa1 #196ba1 #106aa0 #00669d #0e679e #1d689f #1d689f #266b9f #2c6ba0 #517aab #748db3 #909cbd #94a0be #9fa8c1 #b0b3c9 #babbcd #bcbecd #c0c0cf #c0c0ce #c0c3d0 #c7c7d3 #c1c3cf #bcbfcc #bdc0cc #c0c2cd #b8bccb #afb6c9 #abb1c8 #a6afc3 #b2b8c8 #ffffff #000000 #4a6b8a

Выход

1 0 0 18 3 21

Ограничения

Время · Python: 8000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 6 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Прямое решение — сравнить каждый пиксель со всеми цветами палитры. Это 1,6 миллиона сравнений. Для Go это пустяк, а для Python — секунды. Посмотрите на сами данные: сколько в фотографии разных цветов?

2Идея

Это первый шаг k-средних, «отнести», только центры уже не двигаются. Ответ для пикселя зависит лишь от его цвета, а в фотографиях цвета повторяются: небо — это тысячи одинаковых или почти одинаковых пикселей. Запоминаем ответ для каждого встреченного цвета в словаре, и разных вычислений становится столько, сколько разных цветов. Это мемоизация в самом простом виде.

3Разбор

Читаем палитру, переводим #rrggbb в три числа. Для каждого пикселя ищем ответ в словаре по строке цвета; если нет — перебираем палитру, считаем квадрат расстояния в целых числах и выбираем строго меньший (так при равенстве остаётся цвет с меньшим номером), записываем в словарь. Увеличиваем счётчик найденного цвета.

Корень из суммы квадратов считать не нужно: корень монотонен, и сравнение квадратов даёт тот же порядок. Заодно расчёт остаётся целочисленным и точным — во втором тесте пиксели стоят ровно посередине между цветами палитры, и любая погрешность решила бы спор неправильно.

3+Решение

4Сложность

O(u·k + n), где u — число разных цветов среди пикселей. На фотографиях u в разы меньше n; в пятом тесте цвета случайные, u ≈ n, и выигрыша нет — но и проигрыша почти нет.

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

«≤» вместо «<». При равенстве пиксель уходит к более позднему цвету. Ловится вторым тестом.
Корни и плавающая точка. math.dist возвращает float, и на равных расстояниях можно получить разные результаты в разных языках. Квадраты целых чисел — точные.
Пересчёт палитры на каждом пикселе. Разбирать шестнадцатеричные строки палитры для каждого пикселя заново — лишняя работа: сделайте это один раз.

Алгоритмы задачи

ML Алгоритм k-средних Делит точки на k групп так, чтобы точки были поближе к центру своей группы. O(n · k · d) за шаг 2 задачи TEC Приём Мемоизация Запомнить ответ функции для каждого набора аргументов, чтобы не считать его заново: экспонента превращается в многочлен. O(число разных аргументов × работа на один вызов) 2 задачи