How does hacking work with the new feature of unrated registration? I have seen this question raised in the comments to the announcement several times, but there is no answer still and I think it's weird that Mike hasn't thought about it before announcing.
I was working recently on a div.2 Codeforces round (still might happen in the future) and I was told by my coordinator that pretests should be equal to systests in all the problems. From this I can conclude that it is a Codeforces policy and intentionally weak pretests do not happen. It doesn't mean that it is impossible to hack anybody, but it doesn't sound like a viable strategy. I find it weird that this information is not public, it's like I'm getting bonus information about all other Codeforces rounds by setting a round myself.
I have done exactly zero research on the matter, but my feeling is that 99% of hacks (I'm talking about during-the-round-hacking here, not open hacking of education rounds and such) happen in rare cases when authors didn't break some popular for some reason wrong solution, and every room has (15+-3) solutions with the same bug. So somebody in the room gets (1500+-300) points that have no correlation with their problem-solving skill, and even if somehow it is the top participant in the room, it still can affect the results in a random way due to rooms. It doesn't feel good to win a round like this. It feels even worse to lose a round in such a way.
I would be glad if during-the-round-hacking was removed.
Strong agree. Hacking was during Topcoder days when pretests were weak/nonexistent, and with room-based rounds. Modern codeforces rounds have strong pretests and systests, so hacks are basically only by tryhards to cancel div3/4 solutions using a
dictin python. I support this feature being removed during the round.wice city
I totally agree. And while we are at it, another feature request would be to enforce rating recalculation for everyone who is registered as rated for the round. Imagine someone opens problems, can't solve anything, doesn't make a submit and there's no penalty for that. Such pussy behaviour should not be tolerated. Topcoder had it, Atcoder has it, this is the way.
Don't agree with this — what if you register but then have an emergency which means you can't participate...
Register immediately before the round
Making stuff hard to take advantage of is much more important than accounting for such people.
I have never missed a rated atcoder round that i registered for.
but this isn't possible because of that braindead 5 minute period before the round where you can't register
That would go away if hacking got removed fyi (since no need of rooms)
Either way, is it too much effort to sit down 10mins before a contest?
Then we can talk about this change after the 5 min period gets removed.
5 minutes is not a long time at all
Register when you know you are capable of attempting the contest, as of me I always find myself before 10-15 minutes in front of my PC before a round and we have the option to register before 10-15 minutes so better register then.
strongly agree very unethical
Hi! We're making progress on this issue. Don't go too far, and you'll see changes soon.
Kindly look at the above request too.
What do you think about all rounds having hacking, but strictly after the round, like in div3/4? That way, the potential for cheats stealing innocent people's solutions and putting them on Telegram is removed
Please don't remove systest phase
thnks uncle
Yes, it's been pretty pointless for a while and gradually becoming more pointless. Just move it to post-round phase and problem solved.
I would be very sad to see hacking go, but you might be right.
For what it's worth, most of my recent hacks aren't at all in the "authors didn't break some popular wrong solution" category. I'm always surprised when people say that the only kind of hack these days is breaking
unordered_map, randomized algorithms and similar because this hasn't matched my experience at all.The most common cases are (a) bizarre, haphazardly hacked together attempts to solve the problem and (b) solutions that should very obviously get TLE. Case (b) might be surprising but it kind of does make sense — in a Div2B problem there are some 4-6 pretests, which might mean only one max test. And if that max test doesn't fail all solutions that are too slow, then the test cases are weak. Surprisingly, there are not as many people who write solutions with blatantly bad time complexity.
Your claim of 99% might still be correct, because in cases where you really have 15 hacks per room, the total number of hacks greatly outnumbers the number of hacks in a round where
I do recommend trying hack, by the way. The chaotic code that you see makes you understand grey people a lot more.
I agree that it might be fun for some people. I think that uphacking is a nice feature and I have nothing against it. Maybe even add post-round open hack phase that affects the results, although it needs some tweaking.
People these days just can't prepare good rounds with hacks and say it's impossible. When I was the author, there were hacks, they were interesting, not trivial and not deciding. Look at rounds 124 and 222 and learn.
I wrote a similar proposal a while ago: https://codeforces.net/blog/entry/131115
I wonder how you think about it.
I dislike the open hack phase
I would much rather prefer there to be no hack phase at all (which affect the standings, uphacks is fine)
Check any div3/edu hack list, and it will always be 90% umap/hashimg/uset etc hacks.
I dislike that you can target users and specifivally try to hack them (why should tourist face more scrutiny than any other person?), and it becomes a luck game of whether people targetted you or not. I also dislike that if you want the best possible result for yourself, you have to hack people who placed above you for another 1 — 3 hours after the contest.
Earning points for these hacks would also destroy the system as it becomes a speed test of who can find the most hacks.
Just do it like in div3/4/edu rounds. Trivial. Problem solved. No cheating, everyone gets same scrutiny, what's the issue???
It is not solved.
Div3/4/edu rounds hacking system is not fine. We just dont care for it as we are not rated. I listed the problems. Umnik and Xellos listed some more problems. Maybe read instead of asking whats the problem?
No, everybody does not get the same scrutiny.
Everyone FSTs in the end, and if all the hacks are umap hacks, anyone who uses a umap FSTs. What's the problem? Do you really propose no scrutiny for anyone?
I think he meant "certain people facing more scrutiny" and "most of them are umap etc. hacks" are two seperated problems.
Additional things to what Dominater069 said: There are some types of solutions that might have good complexity but bad constant factor, especially if you are allowed to construct tests against this solution in particular. I'm mostly thinking about sqrt-like things, when you just choose a constant and apply different solutions for different cases. The existence of open hack phase then requires you to choose the constant in the best possible way, which is not the usual case. I would suggest to only consider hacks by TL that make the solution much solwer than intended, maybe 2xTL. But then there are randomized solutions with
while(clock() < TL), and TL would be hardcoded in the solution.With sqrt solutions, it's better to check locally at least where the optimum lies in practice for a random max test. In my experience, the branch constants don't vary much from constructed non-random max tests (though exceptions exist), but to account for this variation, optimising the execution time of a random max test is worth that bit of effort.
I'm more concerned that it'd lead to a "Dark Forest" kind of situation where if you solved a problem in a weird way, you need to keep quiet and pray nobody notices your solution. It could even be that you solved a problem in the intended way, but as long as you don't know the intended way (and when would editorials be published, then?!), it's better to not draw attention to yourself since 1 hack is a big difference in placement and you can't resubmit then. Post-round discussion is perhaps even more important to preserve than the competition itself.
Is there any viable way to make solutions using
while(clock() < TL)exceed the time limit at all? Won't they almost always stop early enough, even if the answer is wrong?No, what he was referring to is the solutions that might have passed in 2 * TL (because they can try more runs then, so higher probability of passing)
Oh, so they would be at a disadvantage during the hacking phase compared to other solutions... Thanks, that makes way more sense than what I initially interpreted the sentence as lol
Also I suggest to have the
std::hashpatched to have randomized behaviour to make it not hackable, considering how many people use STL hash tables without knowing their working principle and how tricky is it to write randomized hashes during contest for those who don't use long templates. This is still a viable issue even if we only allow post contest hacking. I wonder if there is any downsides to this, but I don't think there's any solution to an actual problem dependent on the hash policy, right?Though I completely have no idea how hard will it be to implement this, since
std::hashis implemented on lots of data types and it doesn't seems easy to write an universally unhackable hash policy for each of them while keeping the original time complexity and constant factor.I think there still needs to be some form of reward for hacking even if the hacking phase will always be after the contest, otherwise the testdata may not always be strong enough.
Literally contribution
this looks perfect, "strengthen the test data" seems like something you do to the community rather than some test to your skill, and that gives contribution more sense, upvoted
The testdata is not always strong enough right now. In-contest hacking does not really improve it, because there is little incentive to do in-contest hacking as is. Post-contest hacking doesn't have any incentives but some people still do it. There is payment for preparing the round which includes preparing strong tests for every problem. In conclusion:
- I'm not sure the problem you are describing exists;
- If it exists, it is not really connected to the issue of in-contest hacking;
- Your proposed method for solving that problem is flawed.
I am sorry, but you will never be gas.
Personally, I liked during-the-round-hacking. But it became almost obsolete as multiple tests replaced single tests hence covering most of corner cases in compound TC#2. It looks as if the splitting point of the TCs array into pretest and final tests sub-arrays was moved rightwards, i.e. some after-tests become pre-tests.
And there plays psychology and democracy (https://codeforces.net/blog/entry/76133#comment-618041 (4 ya) and https://codeforces.net/blog/entry/59465#comment-431304 (6 ya)). If most of the community like to have instant "Accepted" over "Pretest passed", they will influence the stearing of the platform. Therefore nowadays "Pretest passed" became much closer to "Accepted" than in earlier days.
Moreover, the platform is rarely accessible, so the reading solutions of others and hacking is usually from difficult to impossible. E.g. it isn't possible when using m1, m2, m3 skeleton platform versions.
Besides my older (3 ya) suggestions in https://codeforces.net/blog/entry/98654#comment-874867, I would also agree of variation where during-the-round-hacking is removed. But that means of no difference in so called "Educational" (whatever it means) and usual (non-educational) div.2 rounds.
An alternative thought is to split coding and hacking, i.e. to make rounds dedicated only for hacking (https://codeforces.net/blog/entry/98770#comment-875485 (3 ya)). E.g. not to hack each other inside the room, but rather to hack some code everyone individually, similarly to usual problem solving. This could be named as "hacking problem solving" or so. But another variation with fighting each other may be also interesting if invented.
Also worth to mention, that hacking isn't popular for >A problems because of the costs being regressive. Moreover, usually only few other competitors of the room have solved higher problems (i.e. scarcity of codes to check for hacks).
And one additional note is that two communities — coders and hackers can't peacefully live in one place, because more populous group will ask for better evaluation compared to another group (example of it — https://codeforces.net/blog/entry/87524#comment-759372 + https://codeforces.net/blog/entry/87524?#comment-759105 (4 ya)). Therefore better is not to have coding and during-the-round-hacking combined until it is fair.
If all the problems nowadays have
pretests == full_tests, why do we wait for so long during system testing? :( Especially it annoys when you want to submit your solution you wasn't able to fix before the end of the round.Systests = pretests + hacks*
Looks like mike didnt special case if (hacks == 0)
IMO Educs have the best hacking system. Doesn't allow for braindead points farming yet leaves an opportunity to punish someone using, for example, polynomial hashes.
Punish someone using uninformed polynomial hashes*
You cannot hack good hashes which depend on time based randomness.
True. Although I wish those could be hacked too. Hashes are never the intended solution, which means that there's always a better option.
This is true a lot (in the sense there is better, but if it AC it works), but definitely not always.
How will you solve
https://oj.uz/problem/view/BOI18_genetics
What does that problem have to do with anything?
Why? Why is hashing bad? Hashing is never the intended solution is just false
Probabilistic methods are just as valid....
Hashes certainly can be the intended solution. Although I also dislike when people use polynomial hashing brainlessly in all string problems when there is a nice way to do the same thing using z-function or prefix-function, I wouldn't say they must be "punished" for it. And there are other types of hashing, probably you haven't seen those. I would say that when hashing appears in non-string problems it is usually a part of a very beautiful solution.
Perhaps I was a bit too categorical. In my experience hashes always were a method to cheat the system, in a "I don't want to learn suff-array I'll just write hashes + bin-search" sort of way. But I concede — hashes do have a right to exist in specific problems.
I agree to remove both the pretest and system test, to make everyone to get Accepted in all problems.
Maybe there's a way to solve while(t < const), I'm not sure:
divide the return value of all time-returning functions by 2.
I have another question, which might have started when I was green:
Why can't we hide all the const values when hacking?
I originally wanted to use the prime numbers I memorized for string hashing, but that's not feasible because others can look at your past code to find your usual modulus. So, you have to use a different modulus each time, which essentially means you still have to randomly choose one, making it pointless.
Randomly choose base using time based randomness ....done
fyi: expected time of finding prime number in $$$[2, n]$$$ by $$$O(\sqrt x)$$$ check is less then $$$\sqrt n$$$.
its definitely atleast root n right?
Since the last prime number will definitely need O(root n) time to check, or were you arguing by constant?
imagine $$$n=10^{9}$$$ and last prime was $$$3$$$
How would this even work? And why would someone implement this
While i dislike hacking bad hashes, it is a feature not a problem.
If pretests are equal to systests, why do we still run system tests? It only wastes computational resources.
Maybe checking if there are cheaters.
It makes sense, but I want to know how to deal with such solution or mistakes then:
They might not be found and tailored to by data-maker,then can be used to solve the problem.This sometimes happens in other contests like this link1 link2 link3.So,I want someone to answer.
I absolutely loved the old days of CF hacking, when pretests were very often intentionally weaker than systests, and hacking was about finding algorithmic inefficiencies or missed corner cases. That being said, if the official policy now is pretests = systests, the only viable hacking strategy is killing poorly randomized solutions and also standard data structures and algorithms, like Java's sort, C++'s unordered set/map or Python's dict.
I think that it is spiritually against the concept of hacking as it was initially introduced, and on the other hand it allows and encourages some behavior that I find unhealthy, such as qmk using scripts to do a few thousand hack attempts on standard library data structures after each Div. 3 contest.
I assume certain bad solution strategies that are missed by the authors and still can be hacked exist, but they become exceedingly rarer with the current system, and basically makes it not worthwhile to try hacking during live contests, as the risk/reward ratio of wasting your time on it is completely off.
I would personally prefer to go back to the "good old" concept of hacks and use weaker pretests much more often, but unfortunately it seems that in most cases it just leads to people being frustrated with the contest author, and downvoting the announcement. Quite saddening to me, but if it's not the option, then it might indeed be better to disable hacks altogether.
I think one really good thing about old CF contests was that you could never depend on your solution being correct due to it just passing pretests. It forced you to put much more attention on the correctness of whatever you're doing before the submission, and I think it's a very nice habit to develop, and the currently existing system doesn't help with it that much, as "Proof by AC" officially works on CF now.