ACM ICPC World Finals 2010

Problem B: Barcodes

The main difficulty in this problem appears to have been to categorize the regions as thick or thin. A simple way to do this is to note that the first region is always thin, regardless of whether the code is reversed. Then, everything more than, say, 50% wider than that, must be thick, and the rest of the markings must be thin. Once this classification is done, one can check whether there is a choice of width for the thin regions such that all thin regions are within ±5% of this width and all the thick regions within ±5% of twice that width. Here, it is very important to note that the intended width of a region does not necessarily have to be an integer. An easy way to do the check is as follows: multiply all the thin widths by 2 (to get them on the same scale as the thick widths). Then the widths are OK if the smallest width is at least 95/105 times the largest width.

After this things should be easy. If the second region is thick the code is reversed and we flip direction. Then we simply decode each character (making sure to return bad code if we encounter a pattern which does not correspond to one of the valid characters or if the total number of regions is not of the form 6n − 1), and check whether the C and K checksums are correct.