Lynbrook Computer Science

Announcement: Gunn Programming Contest is coming soon, so sign up now at bit.ly/gunnproco12!

• When: Feb. 25, 9AM – 3PM
• Teams of up to 3
• 2 hour round, 12 problems
• Will be worth PotW credit

The meeting discussion was on data compression. The presentation primarily focused on two different variations: loseless and lossy. Our meeting slides can be found here, and this week’s PotW is as follows:

• 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
• Sample Input #1:
  3 2 (N K)
  7 6 3 (elements of the original sequence)
  Output:
  1 (minimal cost is 1)
  6 6 3 (7 7 3 is another option)
• Sample Input #2:
  7 2
  3 4 5 6 9 10 11
  Output:
  6
  4 4 4 4 10 10 10 (5 5 5 5 10 10 10 is another option)