Um_nik's blog

Hacking (as a CF feature) does not fit modern competitive programming
By Um_nik, history, 3 months ago, In English

  1. 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.

  2. 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.

  • Vote: I like it
  • +1015
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +132 Vote: I do not like it

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 dict in python. I support this feature being removed during the round.

→ Reply
»
3 months ago, # |
  Vote: I like it +80 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    Don't agree with this — what if you register but then have an emergency which means you can't participate...

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +40 Vote: I do not like it

        but this isn't possible because of that braindead 5 minute period before the round where you can't register

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it +72 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it +32 Vote: I do not like it

            Then we can talk about this change after the 5 min period gets removed.

            → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it -14 Vote: I do not like it

          5 minutes is not a long time at all

          → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    strongly agree very unethical

    → Reply
»
3 months ago, # |
  Vote: I like it +414 Vote: I do not like it

Hi! We're making progress on this issue. Don't go too far, and you'll see changes soon.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it -40 Vote: I do not like it

    Kindly look at the above request too.

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    Please don't remove systest phase

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    thnks uncle

    → Reply
»
3 months ago, # |
  Vote: I like it +99 Vote: I do not like it

Yes, it's been pretty pointless for a while and gradually becoming more pointless. Just move it to post-round phase and problem solved.

→ Reply
»
3 months ago, # |
  Vote: I like it +105 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    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.

    → Reply
»
3 months ago, # |
  Vote: I like it -115 Vote: I do not like it

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.

→ Reply
»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I wrote a similar proposal a while ago: https://mirror.codeforces.com/blog/entry/131115

I wonder how you think about it.

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it +48 Vote: I do not like 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.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -19 Vote: I do not like it

      Just do it like in div3/4/edu rounds. Trivial. Problem solved. No cheating, everyone gets same scrutiny, what's the issue???

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it -10 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it +15 Vote: I do not like it

            I think he meant "certain people facing more scrutiny" and "most of them are umap etc. hacks" are two seperated problems.

            → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +42 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Also I suggest to have the std::hash patched 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::hash is 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.

→ Reply
»
3 months ago, # |
  Vote: I like it -13 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +108 Vote: I do not like it

    Literally contribution

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      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

      → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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.

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am sorry, but you will never be gas.

→ Reply
»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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://mirror.codeforces.com/blog/entry/76133#comment-618041 (4 ya) and https://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/blog/entry/87524#comment-759372 + https://mirror.codeforces.com/blog/entry/87524?#comment-759105 (4 ya)). Therefore better is not to have coding and during-the-round-hacking combined until it is fair.

→ Reply
»
3 months ago, # |
  Vote: I like it +20 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Systests = pretests + hacks*

    Looks like mike didnt special case if (hacks == 0)

    → Reply
»
3 months ago, # |
  Vote: I like it -10 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Punish someone using uninformed polynomial hashes*

    You cannot hack good hashes which depend on time based randomness.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -55 Vote: I do not like it

      True. Although I wish those could be hacked too. Hashes are never the intended solution, which means that there's always a better option.

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        this?
        → Reply
        • »
          »
          »
          »
          »
          9 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          What does that problem have to do with anything?

          → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +33 Vote: I do not like it

        Why? Why is hashing bad? Hashing is never the intended solution is just false

        Probabilistic methods are just as valid....

        → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +39 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          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.

          → Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

I agree to remove both the pretest and system test, to make everyone to get Accepted in all problems.

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I have another question, which might have started when I was green:

Why can't we hide all the const values when hacking?

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Randomly choose base using time based randomness ....done

      → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      fyi: expected time of finding prime number in $$$[2, n]$$$ by $$$O(\sqrt x)$$$ check is less then $$$\sqrt n$$$.

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          imagine $$$n=10^{9}$$$ and last prime was $$$3$$$

          → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    How would this even work? And why would someone implement this

    While i dislike hacking bad hashes, it is a feature not a problem.

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If pretests are equal to systests, why do we still run system tests? It only wastes computational resources.

→ Reply
»
10 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

It makes sense, but I want to know how to deal with such solution or mistakes then:

  1. Hashing up(I sometimes use it to AC Atcoder problems).
  2. Bruteforce that might be fast mostly.
  3. Using queue/stack to make a fast Bellman-fold(sometimes as fast as BFS).
  4. Wrong greedy that often get correct answer and passed.
  5. Wrong impletion that may die of details.
  6. Imperative case that some people not considered.
  7. Incorrect guessing.
  8. Wrong magic ideas.

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.

→ Reply
»
8 days ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

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.

→ Reply