Randomized solutions vs Hacks

Revision ru1, by Um_nik, 2017-08-25 02:52:56

I think that most of us know about situation with problem 843B - Interactive LowerBound. The intended solution (and it looks like all possible solutions) was randomized and it generates huge amount of hacks based on fixed randseeds.

I want to mention that I'm not against good randomized problems and I even set one myself.

But for me it seems that hacks can ruin such type of problems. The only thing author's solution is better than contestant's is that it is invisible during the competition. I can even imagine that some tester's solutions (maybe not the solution which is used to generate judge answers) was broken by some hacks.

I think that it breaks the problem as art piece and breaks the contest format too. You solved the problem just like authors wanted and now... it depends on is there a hacker in your room. It also breaks the idea of hacking. There is no bug in my solution, why should I be hacked? And why should the guy get 100 points for hacking me? He didn't crack my solution, he abused CF 'Run' tab.

And for me it looks like authors didn't think about that bug/feature and now they try to protect themselves in comments. For me it could be a good enough reason not to use this problem on CF round. This problem would be a good problem in ACM contest and I know that these guys do ACM contests. But maybe there were a way to prevent such abuse of hack system?

What about forbidding hacking this particular problem? It has two obvious flaws (maybe more).
1. After this post it can give a hint that you should use randomized solution — Yes, this is a problem.
2, All problems should be equal! You are taking away our sacred right to hack!!!1! — Are they? There are a lot of problems with no hacks on CF. There can be many reasons: the problem was too easy, or too hard, or it has no corner cases, or it can be solved only in one way, or, or... You can say that I propose unnatural way to prohibit hacking and in those cases it was prohibited by the problem itself. But (in my opinion) such randomized problem also naturally prohibits hacks because hacks can ruin the problem.

And it is also not true that all problems were 'equal' in this sense before. There were some problems with multitests which allow to hack with only one test in multitest. There can be a bug in handling multitesting but we cannot hack this bug.

This brings us to less cardinal solution: make some bounds on hacks. Like n ≤ 100 or (in this particular problem) let only choose values in list, but not their order.

Anyway, I think that problemsetters and coordinator should think about these matters in the future.

Tags hacks

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian Um_nik 2017-08-25 02:52:56 2665 Первая редакция (опубликовано)