F. Posterize
event sponsor ICPC 2017 Problem F Posterize Time limit: 2 seconds Pixels in a digital picture can be represented with three integers in the range 0 to 255 that indicate the intensity of the red, green, and blue colors. To compress an image or to create an a...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
Pixels in a digital picture can be represented with three integers in the range 0 to 255 that indicate the intensity of the red, green, and blue colors. To compress an image or to create an artistic effect, many photo-editing tools include a “posterize” operation which works as follows. Each color channel is examined separately; this problem focuses only on the red channel. Rather than allow all integers from 0 to 255 for the red channel, a posterized image allows at most k integers from this range. Each pixel’s original red intensity is replaced with the nearest of the allowed integers. The photo-editing tool selects a set of k integers that minimizes the sum of the squared errors introduced across all pixels in the original image. If there are n pixels that have original red values r1 , . . . , rn , and k allowed integers v1 , . . . , vk , the sum of squared errors is defined as
min (ri − vj )2 .
1≤j≤k
i=1Your task is to compute the minimum achievable sum of squared errors, given parameter k and a description of the red intensities of an image’s pixels.
Input
The first line of the input contains two integers d (1 ≤ d ≤ 256), the number of distinct red values that occur in the original image, and k (1 ≤ k ≤ d), the number of distinct red values allowed in the posterized image. The remaining d lines indicate the number of pixels of the image having various red values. Each such line contains two integers r (0 ≤ r ≤ 255) and p (1 ≤ p ≤ 226 ), where r is a red intensity value and p is the number of pixels having red intensity r. Those d lines are given in increasing order of red value.
Output
Display the sum of the squared errors for an optimally chosen set of k allowed integer values.
Rapid Citysponsor
ICPC 2017Sample Tests
2 1
50 20000
150 10000666700002 2
50 20000
150 1000004 2
0 30000
25 30000
50 30000
255 3000037500000Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Key Observations
Write the structural observations that make the problem tractable.
State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
If the constraints matter, explain exactly which part of the solution they enable.
Algorithm
Describe the data structures and the state maintained by the algorithm.
Explain the processing order and why it is sufficient.
Mention corner cases explicitly if they affect the implementation.
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
State the first key claim.
Proof.
Provide a concise proof.
Lemma 2.
State the next claim if needed.
Proof.
Provide a concise proof.
Theorem.
The algorithm outputs the correct answer for every valid input.
Proof.
Combine the lemmas and finish the argument.
Complexity Analysis
State the running time and memory usage in terms of the input size.
Implementation Notes
Mention any non-obvious implementation detail that is easy to get wrong.
Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
// Fill in the full solution logic for the problem here.
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2017/F-posterize/solution.texC++ implementationcompetitive_programming/icpc/2017/F-posterize/solution.cppStatement textcompetitive_programming/icpc/2017/F-posterize/statement.txtStatement PDFcompetitive_programming/icpc/2017/F-posterize/statement.pdfMetadatacompetitive_programming/icpc/2017/F-posterize/meta.jsonYear packetcompetitive_programming/icpc/2017/contest_problems.pdf