You can find how the best solution works on some small test case here:
zcontest.ru/2007.02/zdip_bestsol_int_01.php
It works not so good on small noise level but then it increse from
13% to 20% it gives very good result.
On the following page available results for the best solutions from
the Russian version of contest:
zcontest.ru/2007.02/zdip_bestsol.php
Small test case can be found here:
zcontest.ru/2007.02/files/ZDIP.input.zip1
zcontest.ru/2007.02/files/ZDIP.output.zip1