2012 =
* 503
“Might be useful tomorrow.” – MG
PotW Solution
int dp(int pos, int k) {
if (k > lim) return -(1 << 30);
if (pos == n) return 0;
int res = mem[pos][k];
if (res != -1) return res;
res = 0;
int cur = k % 2;
int stay = (s[pos] ==
res = max(res, dp(pos
int flip = (s[pos] ==
res = max(res, dp(pos
return res;
'0' + (1 - cur));
+ 1, k) + stay);
'0' + (cur));
+ 1, k + 1) + flip);
Gunn Programming Contest
• Feb. 25, 9AM – 3PM
• ProCo-like contest at Gunn High School
o Teams of up to 3
o 2 hour round, 12 problems
o “A good number” of the problems at APCS A level, with more advanced
problems also included
• Will be worth PotW credit (exact credit TBA)
• Register at
• Other dates:
o March 17 – Harker Programming Contest
o May 19 – Stanford ProCo
February USACO!
• Today’s the last day to take the February USACO!
o Take it if you haven’t already! (Even though AMC is tomorrow…)
• 5 points PotW credit for participating (as usual)
• Representing data with smaller amounts of data
o Note that all data is essentially binary
• There are various file formats for compressed files
General files: "zip", "tgz", "tar"
In fact, "jar"s are really just augmented "zip" files
Images: "jpg", "png", "gif"
Sound: "mp3", "wav", "wma"
Movies: "so many we're not even going to try to list some of them here"
Executables, 3D Models, etc.
• Two distinct variations: lossless and lossy
• Compress the data so that the
process is reversible
• No scheme can guarantee decrease in file size
o One-to-one mapping between possible file input/output makes this
• Instead, schemes often take advantage of
repetition in data
o Text files often repeat certain letters more frequently
o Images might feature certain colors
o Neighboring pixels are often close in color
• Examples: ".png", most general formats
Simple Encoding Algorithms
• Run-Length Encoding
o Scan left to right on the data
o Group identical elements that
appear consecutively
o Store the first element + a count
• Huffman Trees
o Depending on how often a
certain character or word
appears, assign it a binary id
o More common words should be
assigned more bits
o However, no id can be a prefix
of another
• Take advantage of "unnoticeable" imperfections in
o Audio, image, and movie files depend on this technique
• Often use differencing techniques
o E.g.: In a movie, each successive frame can be differenced from the
previous one to reduce data storage
• Often have ability to specify quality
• Specialized optimizations are designed to trick the
human eye
o ".jpg" files are notorious for their blockiness and failure to preserve sharp
o ".gif' files omit colors and then use a dithering technique to emulate
shades of color
PotW – Silly Compression
As part of a new compression algorithm, Bessie is
trying to modify a sequence of data of length N so
that it contains at most K distinct values. However, it
costs |a - b| additional bits to change an integer a
into an integer b. Tell her the optimal sequence she
should modify the original sequence into. If there are
multiple solutions, output any.
For 30 points, solve for N < 20.
For 50 points, solve for N < 100.
For bragging rights, solve for N < 1000.
Time Limit: 2 seconds.
Note: The second and third tasks are very difficult
Silly Compression (cont.)
Sample Input #1:
3 2 (N K)
7 6 3 (elements of the original sequence)
1 (minimal cost is 1)
6 6 3 (7 7 3 is another option)
Sample Input #2:
3 4 5 6 9 10 11
4 4 4 4 10 10 10 (5 5 5 5 10 10 10 is another option)
• Note that an optimal sequence always exists such
o Each element of the original sequence should be shifted to its closest
relative in the new sequence
o Each element of the new sequence should appear in the original
o Thus, the first task can be solved with a exponential-time brute force
• Try all n choose k possibilities
• 20 choose 10 fits well within time limit
• Second task:
o Note that the element of a sequence that minimizes the total distance to
the other elements is the median
o Use dynamic programming after sorting

similar documents