Judges' Notes for Falling Ice

The judge's solution is initially set to be a legal contest submission. To see graphical output for all judge's data sets, you need to make two changes. In the judge's checking code at the end, initialize the variable hideGraphics to false and uncomment the first if statement in the method dataSetCheck. The alt subdirectory shows a solution with a different algorithm (rolling rather than falling).

Floating Point Issues

With floating point arithmetic and complicated patterns in different algorithms it is notoriously difficult to ensure identical results with different (correct) algorithms. Three kinds of tests were made in the judge's solutions to be sure such problems were avoided.

If the solution is run set to generate summary statistics with the judge's input, the following is produced:

Overall minimums:
Roundoff Leeway: 0.000402; Circle Separation: 0.027864; Badness diff: 0.020083

1. Rounding to many fewer places than full double precision generally gives the same results to different implementations, but this fails if the actual value is too close to a transition between roundoff values. No answer was closer than 0.000402 to a value with a different rounded answer.

2. The entire topology of the solution can change based on numerical inaccuracies if one solution has a circle barely catching on two boundary points while another algorithm has it barely passing without catching. The closeness to this transition was noted for all calculations, and circles either caught or completely missed catching by at least 0.027864. This was further checked by adjusting the separations where a circle was declared to catch or not interfere with another. This was encoded in the variable OkSep, which mathematically should be 0, but it could be adjusted with a command line parameter. The program was run three times:

java falling > falling.out
java falling falling.in 0.01 > falling01.out
java falling falling.in -0.01 > falling-01.out

setting this parameter to 0, 0.01 and -0.01. The three output files are identical.

The sample data has similar statistics, so contestants should be able to reproduce the sample data.

3. The problem claimed the data produces unique best resting places. The solution compared all candidate positions to the lowest chosen, and found no measures closer than 0.020083.

Judge's Input Choices

The last two data sets, 14 and 15, illustrate the need for the test for a clockwise direction: the reference to clockwiseTo in the addCircle function. With that test, the two data sets give different results. With the test omitted, the result for Dataset 15 incorrectly changes to match that of Dataset 14.