Layered Barcode
Display Editorial

• 64 windows, 192 sheets, 256 items
  • Each item's barcode is a random pattern with exactly 32 blacks
• Design the sheet patterns (white, black, hole) first, then process 1,024 orders one by one
  • Each order is uniformly random among the items other than the previous one
  • One operation: take out a sheet visible through some window and reinsert it at any depth
• Score 2KE + T (smaller is better)
  • One incorrect order (E) costs as much as 384 operations → display every order correctly, then reduce the number of operations T

• The sample program in the problem statement
• Prints item k's pattern as is on sheet k (full-match sheets)
  • With 192 sheets, only items 0–191 get one
• Every sheet covers every window, so only the top sheet can be moved
  • Move the top sheet to the bottom until the ordered sheet comes to the top
  • Orders for items 192–255 (1/4) are incorrect (each costs 384 operations)
• Full-match sheets are meant as a hint toward other solutions

Visualizer: solution 0

• Moves only the top sheet, cycling until the target sheet comes
• Orders for items 192–255, which have no sheet, are left incorrect with no operations

seed=0, all 1,024 orders. Enter an order number to jump
Keys: p play / pause, . / , one operation forward / back,
n / b next order / start of the current order

• For each window j, place a sheet that is white only at window j and one that is black only at window j (128 sheets)
• Window j shows the color of the upper of the two
  • To change a window's color, move the upper sheet just below the lower one (1 operation)
• Operations = windows that differ from the previous item = 32 on average
• Many participants submitted this solution, and their scores tied
• Improving from here was somewhat hard

Visualizer: solution 1

• For each mismatched window, move the upper sheet just below the lower one

seed=0, all 1,024 orders. Enter an order number to jump
Keys: p play / pause, . / , one operation forward / back,
n / b next order / start of the current order

• Combine the full-match sheets of solution 0 with the toggle sheets of solution 1
• Use toggle sheets only for windows 0–62 (126 sheets), and make the other 66 sheets full-match sheets
  • The full-match sheets line up at the bottom, and the head of the line shows in window 63
  • Window 63 is toggled by sending the head of the line to its end
• For each order, choose the cheaper way
  • Toggling: the number of mismatched windows
  • Full-match sheet (if any): its position in the line + 1
• → operations per order

Visualizer: solution 1b

• When a full-match sheet comes to the top, all windows match at once

seed=0, all 1,024 orders. Enter an order number to jump
Keys: p play / pause, . / , one operation forward / back,
n / b next order / start of the current order

• For each block of B windows, place B+1 comb-shaped sheets
  • Sheet i is black at windows 0 to i−1, white at window i, and holes elsewhere
  • Breadth-first search over the (B+1)! orderings
• Given only the statement and left to do everything, AI tends to pick this approach (→ How far AI gets on its own)
• B = 2 gives no gain, and larger B helps only a little
  • → We want one operation to fix many windows

Visualizer: block toggles

• Reorders 5 sheets for each block of 4 windows

seed=0, all 1,024 orders. Enter an order number to jump
Keys: p play / pause, . / , one operation forward / back,
n / b next order / start of the current order

• For each window h, make a bundle of sheets (tier h)
  • A tier-h sheet is opaque only at windows 0 to h, printed with some item's colors there
• Stacking tiers 0, 1, …, 63 in this order, the head (topmost sheet) of tier h shows in window h
• Two kinds of operations
  • Toggle: move the head of tier h just below a sheet of the target color
  • Dig out a sheet that matches the target at windows 0 to h and put it on top. Return it to the head of its tier at the next order
• For each order, choose the sheet that needs the fewest operations (or toggles only)

• Start with 2 sheets per tier, and add sheets one at a time to the tier where the expected operations decrease the most
  • Using a sheet in tier h with l sheets: (l−1)/2 to dig it out, plus (63−h)/2 toggles for the remaining windows
  • Deeper tiers, which cover more windows 0 to h, get more sheets
• operations per order (60% of solution 1)
• The stack on the right: the sheet patterns form a staircase

Visualizer: solution 2

• Putting the dug-out sheet on top fixes windows 0 to h
• The remaining windows are toggled at the tier heads

seed=0, all 1,024 orders. Enter an order number to jump
Keys: p play / pause, . / , one operation forward / back,
n / b next order / start of the current order

• We want a sheet for every item, but 192 sheets < 256 items
• Two similar items share one sheet (64 pair sheets + 128 single sheets)
  • Windows where the two items differ become holes, shown by the head of that window's tier
  • Pair greedily, starting from the pairs with the fewest differing windows
• Tier h needs both a sheet that is white at window h and one that is black. A pair sheet can go only in a tier where its two items agree at window h
• For each order, dig out the item's sheet, put it on top, and toggle the windows it does not cover

Visualizer: solution 3

• Each order digs out the item's sheet and puts it on top
• The tier heads show the windows where the pair sheet has holes

seed=0, all 1,024 orders. Enter an order number to jump
Keys: p play / pause, . / , one operation forward / back,
n / b next order / start of the current order

• In solution 3, a tier-h sheet fixes only windows 0 to h. The rest are toggled one by one
• Split the windows into two kinds
  • Staircase windows (0–29) form the staircase. A sheet cannot be moved unless it is visible through some window, so these windows are how we grab the tier heads
  • Batch windows (30–63): every item's sheet covers all of them
• Just putting the item's sheet on top fixes all 34 batch windows, and only the staircase windows need toggling
• But we need a way to show the holes of pair sheets at batch windows (windows where the two items differ)

• Goal: fill the batch-window holes of pair sheets using only a few sheets
• Place filler sheets above all tiers, and change the colors of the holes just by reordering them
  • For each batch window, pick 2 filler sheets, one white and one black. The other filler sheets have a hole there
  • Window color = the color of the upper of the two (windows without a hole are covered by the item's sheet)
• 7 sheets were enough
  • Assign the 21 pairs out of 7 sheets to the 34 batch windows in turn (13 windows repeat from the first pair)
  • With 6, too few pairs can be displayed in many cases

Visualizer: solution 4

• 7 filler sheets right below the item's sheet
• Toggles only at staircase windows 0–29

seed=0, all 1,024 orders. Enter an order number to jump
Keys: p play / pause, . / , one operation forward / back,
n / b next order / start of the current order

• Solution 4 packed pair sheets from the deepest tier they can go in
  • Pair sheets are used by two items, so when they gather in one tier, they bury each other and digging costs more
• Put each pair sheet in the allowed tier with the fewest pair sheets (the deeper one on ties)
• Choose the remaining single sheets to balance white and black in each tier (if skewed, toggling finds the target color deeper)

Visualizer: solution 5

• Pair sheets are spread over the tiers, so digging takes fewer operations

seed=0, all 1,024 orders. Enter an order number to jump
Keys: p play / pause, . / , one operation forward / back,
n / b next order / start of the current order

• Move sheet y in tier k to just above the head of tier l (l ≤ k)
  • y comes above the heads of tiers l to k → among windows l to k, those where y is opaque take y's color
• Fixes several mismatched windows in one operation
  • Do it if (windows fixed) − (operations to dig) ≥ 2 (2 operations: lifting, and returning it at the next order)
• → operations per order

Visualizer: solution 6

• Moves a sheet of a deep tier above the head of a shallower tier, fixing several windows at once

seed=0, all 1,024 orders. Enter an order number to jump
Keys: p play / pause, . / , one operation forward / back,
n / b next order / start of the current order

• Doing return → filler sheets → dig → lift → toggle one after another can move the same sheet more than once
• Decide only the final order of the sheets, and rebuild a sequence that moves each moved sheet once
  • Take visible sheets one by one, and move each just above the already placed sheet that is below it in the final order
  • If no visible sheet is left midway, use the original sequence
• → operations per order

An example where sheet A of the previous order, just returned, is moved further down by a toggle. After rebuilding, sheet A goes from the top straight to below sheet B

Visualizer: solution 7

• Within one order, each sheet is moved at most once

seed=0, all 1,024 orders. Enter an order number to jump
Keys: p play / pause, . / , one operation forward / back,
n / b next order / start of the current order

• Up to solution 7, a used sheet was returned to the head of its tier (recently used sheets on top)
  • Orders are independent of each other, so recent use means nothing
• Sort by the number of items that use the sheet (use count), most first → pair sheets are shallower, so digging costs less
  • Sheets moved down from the head by toggles, and sheets returned to tiers whose windows this order's sheet covers, go to their place in use-count order
• But keep the top two sheets of different colors → changing that window's color next time takes 1 operation
• → operations per order

• From the top: 7 filler sheets, then tiers 0–29 (185 sheets)
  • 71 pair sheets, 114 single sheets
  • 30 staircase windows, 34 batch windows
• Sheet design: choose pairs greedily → spread pair sheets over the tiers, balancing each tier's colors with single sheets
• For each order: return → filler sheets → dig → lift → toggle → rebuild
• operations per order. About 21 KB of code

Visualizer: solution 8

• Within a tier, sheets with larger use counts are on top

seed=0, all 1,024 orders. Enter an order number to jump
Keys: p play / pause, . / , one operation forward / back,
n / b next order / start of the current order