alexwice's blog

Reconsider open hacking in Div3+4 contests
By alexwice, history, 16 months ago, In English

Because pre/systests are reasonably good nowadays, hacking is basically a "gotcha" where you screw over people not using custom hash (cpp) or managing their sort (java) or wrapping their integers in a dict (pypy), as this is the main way people get hacked.

For olympiad level contests whether this is good or not is arguable, but when the target audience is those under 1400 rating (Div4), IMO there shouldn't be open hacking. Imagine doing a contest and getting your map<int, int> or dict hacked and therefore receiving a WA on an otherwise acceptable solution, because you didn't know about "splitmix" custom_hash cpp trivia. It just is a hostile experience that IMO shouldn't be in low rated contests. The "ideal" solutions shouldn't involve writing custom hashes for these data structures either imo.

  • Vote: I like it
  • -44
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
16 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Not having hacks creates a disconnect between Div 1/2 contests and Div 3/4, it's better to learn of bad CP practices earlier than later. The purpose of these rounds is to supplement standard Div. 2 rounds, rather than replace them (the rating ranges for both are subsets of the Div 2 rating ranges).

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

The map<int, int> solutions are not vulnerable. The hacked solutions fail with TLE rather than WA.

C++ users keep using unordered_map<int, int> for some reason. I wonder who is teaching them that?

Python dict is another story and probably should be fixed, but competitive programmers interested in Python have no skills to to come up with a patch and submit it upstream.

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

    lol no, they submit patches and then the maintainers ignore it and instead do dumb shit like removing conversion of int to string

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

      Do you have a link to the ignored pull request, which tried to address the dict integer keys problem?

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

        i misremembered, it was an issue to pypy instead of a pr https://foss.heptapod.net/pypy/pypy/-/issues/3725

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

          Python is a free software, collaboratively developed by volunteers. Opening an issue isn't completely useless, but somebody still needs to create a pull request to get things done. Competitive programmers could learn a thing or two from the real software developers and that "dumb shit" is a perfect example of how things are getting done:

          • Was there a DoS attack vector disturbing someone? yes
          • Was this DoS vulnerability fixed? yes
          • Were there any downsides? yes
          • Were the downsides severe enough to block the patch? no (the hysterical rants failed to demonstrate any breakages in the real world)
          • Was the solution perfect: no
          • Were further incremental improvements possible: yes

          And the dict integer keys problem can be solved in a similar way. Somebody just needs to create a pull request with a proposed solution. The solution doesn't necessarily need to be perfect, because further incremental improvements are possible. The downsides and limitations will be evaluated. Oh, and don't be afraid of some hysterical individuals disliking your solution and ganging up to attack you, because they will be asked to behave according to the "code of conduct".

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

            "failed to demonstrate any breakages"

            https://github.com/sagemath/sage/issues/34506

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

              First let me tell you a totally unrelated made up fictional story:

              Spoiler

              Now back to Python. The code of Python wasn't originally designed for bigint heavylifting. This isn't perfect, but still good enough for almost all existing Python users. And adding an extra safety guard to enforce operation within safe limits didn't affect any normal users. As for this "Sage: Open Source Mathematical Software" thing:

              To sum it up. Python developers are following the established and proven practices of software development. They are doing a good job. The arrogant competitive programmers (typically teenagers with a huge ego and no experience) are free to prove their skills if they think that they can do it better.

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

    what is wrong with that?

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

      unordered_map is a hash set, so hash collisions can kill the performance. Regular map uses a BBST, so it doesn't have that issue

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

        but isn't a bbst $$$\log(n)$$$ operations and the expected time complexity of hash sets are $$$O(1)$$$?

        → Reply