Remember http://codeforces.me/contest/1039/problem/B or http://codeforces.me/contest/843/problem/B and the hack fiesta with reproducing the pseudorandom sequence?
It might be the case that some of you don't want to be seed hacked. There is a post by neal about the issue. The post is well written but I strongly disagree with the solution described there.
"This should be different every run." I'm fairly sure that it indeed is (well there is still is a small probability of collision but this is kinda obvious). Because of that you are no longer able to conveniently debug you program.
You can hide that under an IFDEF and this fixes the aforementioned problem. However hiding the code under the IFDEF takes 3 lines of code and you may accidentally change something in the IFDEFed part and never notice that locally (the latter is somewhat made up). And I consider IFDEFs ugly but it is a personal thing.
Another way is to obfuscate the generation of the seed. It is definitely against the rules though. There are some grey area ones like hashing a string of tabs and spaces.
There is another way.
template <size_t S>
constexpr bool ls(const char a[S], const char b[S]) {
for (int i = 0; i < S; ++i) {
if (a[i] != b[i]) {
return a[i] < b[i];
}
}
return false;
}
static_assert(ls<8>(__TIME__, "18:50:00") || ls<8>("20:15:00, __TIME__)", "((");
I don't think this requires any further explanation. It does not compile between 18:50 (should be shortly after the submission) and 20:15 (should be the time you expect the contest to end). This was tried on the Educational Codeforces Round 54.
Initially the hacking attempt received something along the lines of "Invalid Verdict". Later the solution and the hacking attempt were ignored and we were deemed "trolls". However, this is somewhere in the grey area. It might be considered an attempt to destabilize the testing system but I assume that the testing system should be fine.
It is not known how will similar submissions be treated in a standard contest. While I do think that hacks are cancer and would never hack myself I understand that in almost every problem the hack is beneficial to the hacked person. Therefore I am not willing to try this code in a Div1 contest unless there is a problem with a randomized solution. However, someone might and I would be curious to see the results.
Irrelevant Fact
The actual reason for my preference of this approach to any other is because it seems like a middle finger one to a person who tries to hack the seed but without resorting to swearing. Feels good man.
Auto comment: topic has been translated by V--o_o--V (original revision, translated revision, compare)
Pretty creative. But such solutions, of course, will be considered a violation of the rules. As they waste my time, I will punish such experimenters. If there are annoying multiple attempts, then I will simply count the hacks on such solutions as successful. Probably, I'll use a compilation cache to reuse binaries from the judgement process.
In my opinion, there is no need for a compilation cache. Here's my argument:
1) A submission survives a hack iff the result of compiling the submitted code and running the program on the given input is the expected output (considering time and memory constraints).
2) Therefore, if compilation fails, the process described above can't possibly print the expected output.
A compilation cache would help the submitter (unjustly, in my opinion), but the rules work fine without adding a special case.
It is of course a violation of the rules, but it aims at a real problem.
Randomized algorithms are recognized by the computer science world as completely valid algorithms, and I hope they can be used in contests. However, hacks on such problems result in a mess. Solving a problem or not depends not only on whether I can invent and code a solution, but also whether I know the quirks of defending against hacks and on having in my room someone who would craft a test (of real frequency of 1 in 10100) that fails my solution. Some of the defending techniques (like obfuscating the constants) are rules violation too.
Of course, we can't allow the above hack, but can we maybe get some other way of defending against crafted tests? Things that come to my mind are:
I don't think it is a real problem. Just adding this to template is enough:
(
random_deviceis not 100% guaranteed to be non-deterministic random, you can use time in milliseconds to be absolutely sure).I personally agree, that solutions with
srand(fixed_value)should pass, but it's very easy for participant to fix such solution (if it's not, when participant will find out something new about how randomized algorithms should work and how to generate good seed) and impossible to find perfect way to "fix" that from the jury side.For example, hacking standard library containers is more serious problem, one can not be defended from that is such a simple way.
random_devicein MinGW produces the same numbers all the time, so you'll be easily hacked (:Ok, didn't know that. Let's use high precision time, it doesn't change any of my points :)
It kind of supports my point though. You are a strong and experienced contestant. You are aware of the possibility to hack a pseudorandom solution that uses standard (and not safe enough) randomness. Yet, your suggestion falls to the same kind of trick.
This is the fallacy I'm describing. A problemsetter hopes to challenge contestants with finding an algorithm, not with knowing the exact specifics of the random_device implementation of MinGW compiler.
My main point is that there is no magic button "do not allow hack which abuses specific pseudo-random generator or some properties of codeforces testing pipeline". Maybe contests would be better with such possibility (or maybe not), but it is not possible to save participants from such traps. For example, all your suggestions do not help if contestant didn't call
srandat all.About random_device: I initially wrote that is not guaranteed to work (forgot that codeforces servers use cool c++ compiler though). If I would be hacked with such code, it would be my problem, not jury problem.
Modern C++, I think, has enough ways to generate unpredictable random numbers. And the second and the fourth methods are not that easy to implement (especially to be used with other languages).
There was a similar discussion (in Russian), not about randomized solutions, but about precision issues. In short: the tests for 404 C were made to fail solutions with
double. The argument was likeBut we write not abstract algorithms, but real programs, so we should know which tricky cases we should care of if we use some techniques or library functions [by the way, does anyone remember this interesting hack of
Arrays.sortin Java? :)]In the ideal, if anyone would be hacked on random that is not random enough, he would go to his favorite search engine and find out the ways to write randomization better. But it's better than your third option, because in it you also need to be aware of a safe way to initialize random (learn about
chrono::steady_clockand friends in my case and about random seed inargv[1]in your case).The first option slows down the process, which is also not good.
So, the best advice I can give is to learn more about the things that you use. Randomized solutions are not only the cases when you can meet with some unexpected hacks (see the examples above, there may be much more of them). Would you want to patch all such cases on Codeforces? :)
The fourth one requires changing system clock to a random date. It doesn't matter which language it uses.
There is a whole computer science field, numerical analysis, which deals with estimating precision of various algorithms doing the same thing and distinguishing the more precise from the less precise ones. In competitive programming it rarely matters (with the exception of using integers when possible to avoid precision issues) but that's because problemsetters rather don't design problems to check this knowledge.
If a problem is designed to check it, it's understood that many people will fail it. But it is possible (and often done) to design a problem that deals with floating point numbers and doesn't require this knowledge. On the other hand, I can't think of a way a problemsetter can require coming up with a randomized algorithm while allowing the contestant to not be aware of hacking pseudoranom solutions.
The checker doesn't write "your pseudorandom was not good enough, try again". If I see my solution fail, I look for a bug in the code, not for a way to use another random number generator. Sure, it's my fault then, but it's not as easy as you describe.
Well, as a counter-argument, C++ is notoriously not a precise model of computer science. C++ is full of such quirks, we just familiarized ourselves with the fact long before becoming successful in programming contests.
In most other languages (I've just checked for Java, Python, and D), when you just start using random numbers, they are already conveniently initialized by a seed which is more or less unpredictable (at the very least, milliseconds of start time are used in the seed, which makes most contest hacks infeasible). The mess here is more or less exclusive to C++, and MinGW for that matter.
But that's what C++ is: it is very powerful, it can do anything, but at the cost of every single thing requiring a bit of knowledge and effort. In the balance of power versus convenience, why would random numbers be any different?
I think that in this case the rules should be updated, because now it (at least formally) can't be considered violation of rules. [Just read https://codeforces.me/blog/entry/4088 carefully :)]
By the way, the trick is really interesting :)
I think it is a violation of rules:
You are forbidden to perform any other actions that can in any manner destabilize the judging process.
Maybe it can be considered destabilizing, but I think that destabilizing here means making the system crash, significanly lag or become unavailable, but not exploiting this oversight, which doesn't affect the stability of the system.
Okay, now I see that no one accepts my point of view, but nevertheless I will try to explain what I say.
IMO, destabilizing the judging process means all actions that will interrupt this process from the participant's side. For example, this case (when participants forbids to compile his solution in some time segment).
Formally, using such asserts, the participant just says: "you cannot test my solution until I don't want it".
I.e. for me it seems like stopping the judging process of his solution until he wants it.
Now got your point of view, it also makes sense. But, in my opinion, but such things or explanations what "destabilizing" means should be written in a more explicit way.
This "hack" can also be fixed in a pure technical way (see below).
I think the hack should just receive "Compilation Error on hack 1" verdict and be successful
Hacks are devastating, I approve
So, why hacks still exist???