Skip to main content
11 events
when toggle format what by license comment
Nov 17, 2014 at 23:35 comment added Mark Adler I guess that's better.
Nov 17, 2014 at 23:34 comment added Mark Adler By the way, detecting an optimization for the minority of cases may be extremely subtle. For example, simple choices in the ordering of what is looked at or the numbering of symbols could be optimized to improve performance on the test cases. Again having no impact on the average performance. This is fine loophole to try to close, but be prepared for ambiguity and arguments about whether it applies or not.
Nov 17, 2014 at 23:32 comment added Martin Ender @MarkAdler how about now?
Nov 17, 2014 at 23:32 history edited Martin Ender CC BY-SA 3.0
added 7 characters in body
Nov 17, 2014 at 23:30 comment added Mark Adler With respect to: "but performing very badly for general input", the example that inspired trying to close this loophole permits performing optimally on all cases, yet still permit optimizing for the test cases. In that example, the result is effectively an integer between 0 and 6,670,903,752,021,072,936,959. It is easy to map n test cases to 0.._n_, resulting in compression to a single character (or less) for those cases, while having exactly zero impact on the average performance. So you may want to remove that condition to closing the loophole.
Nov 17, 2014 at 20:15 history edited Martin Ender CC BY-SA 3.0
added 15 characters in body
Nov 17, 2014 at 20:05 history edited Martin Ender CC BY-SA 3.0
added 303 characters in body
Nov 17, 2014 at 18:59 comment added Martin Ender @abligh Yes, larger sets test cases help mitigate that, but even those can be hardcoded. And scoring by worst-case input only really works for fixed-size problems.
Nov 17, 2014 at 18:57 comment added abligh +1, but also I think it would be useful guidance for question setters to either score on the worst-case input, or take such a wide variety of input that it's impossible to optimise. This is because it's hard to see from an answer whether it's been optimised for the test cases or 'happens' to give a good answer for a small amount of test input data.
S Nov 17, 2014 at 18:50 history answered Martin Ender CC BY-SA 3.0
S Nov 17, 2014 at 18:50 history made wiki Post Made Community Wiki by Martin Ender