The nearest palette colour
The palette has been found: k colours. What is left is to repaint the picture—replace every pixel with the nearest palette colour—and count how many pixels each colour got. “Nearest” means the ordinary distance in RGB space: for colours (r₁, g₁, b₁) and (r₂, g₂, b₂) we compare (r₁ − r₂)² + (g₁ − g₂)² + (b₁ − b₂)². If two palette colours are equally near, the pixel goes to the one earlier in the list.
The pixels in the tests are real photographs by the site's author.
Input
The first line holds k (1 ≤ k ≤ 16), the second the k palette colours. The third holds the number of pixels n (1 ≤ n ≤ 100,000), the fourth the pixels. Every colour is written as #rrggbb in lower-case hexadecimal digits.
Output
k numbers separated by spaces: how many pixels each palette colour got, in palette order.
Examples
Example 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
Limits
- Time · Python
- 8000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 6 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The direct solution compares every pixel with every palette colour. That is 1.6 million comparisons. Trivial for Go, seconds for Python. Look at the data itself: how many different colours does a photograph have?
2The idea
This is the first step of k-means, “assign”, only the centres no longer move. The answer for a pixel depends only on its colour, and in photographs colours repeat: the sky is thousands of identical or nearly identical pixels. Remember the answer for every colour met in a dictionary, and there will be as many computations as there are different colours. This is memoization in its simplest form.
3Walkthrough
Read the palette, turning #rrggbb into three numbers. For each pixel, look up the answer in the dictionary by the colour string; if it is not there, go through the palette, compute the squared distance in integers and pick the strictly smaller one (so on a tie the colour with the lower number stays), and store it in the dictionary. Increase the counter of the colour found.
No need to take the square root of the sum of squares: the root is monotone, and comparing squares gives the same order. The computation also stays integer and exact—in the second test the pixels sit exactly halfway between palette colours, and any rounding error would settle the tie wrongly.
3+Solution
4Complexity
O(u·k + n), where u is the number of different colours among the pixels. In photographs u is several times smaller than n; in the fifth test the colours are random, u ≈ n, and there is no gain—but almost no loss either.
5Common mistakes
- “≤” instead of “<”. On a tie the pixel goes to the later colour. Caught by the second test.
- Roots and floating point.
math.distreturns a float, and equal distances may come out differently in different languages. Squares of integers are exact. - Re-parsing the palette for every pixel. Parsing the palette's hexadecimal strings again for each pixel is wasted work: do it once.