Блог пользователя Um_nik

Автор Um_nik, история, 21 месяц назад, По-английски
  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.

  • Проголосовать: нравится
  • +1017
  • Проголосовать: не нравится

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится +132 Проголосовать: не нравится

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.

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится +80 Проголосовать: не нравится

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.

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится +414 Проголосовать: не нравится

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

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится +99 Проголосовать: не нравится

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

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится +105 Проголосовать: не нравится

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.

  • »
    »
    21 месяц назад, скрыть # ^ |
     
    Проголосовать: нравится +61 Проголосовать: не нравится

    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.

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится -115 Проголосовать: не нравится

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.

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

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

I wonder how you think about it.

  • »
    »
    21 месяц назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится +48 Проголосовать: не нравится

    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.

  • »
    »
    21 месяц назад, скрыть # ^ |
     
    Проголосовать: нравится +39 Проголосовать: не нравится

    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.

    • »
      »
      »
      21 месяц назад, скрыть # ^ |
       
      Проголосовать: нравится +42 Проголосовать: не нравится

      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.

    • »
      »
      »
      21 месяц назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      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?

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится -13 Проголосовать: не нравится

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.

  • »
    »
    21 месяц назад, скрыть # ^ |
     
    Проголосовать: нравится +108 Проголосовать: не нравится

    Literally contribution

  • »
    »
    21 месяц назад, скрыть # ^ |
     
    Проголосовать: нравится +21 Проголосовать: не нравится

    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.

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится +20 Проголосовать: не нравится

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.

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

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.

»
21 месяц назад, скрыть # |
Rev. 2  
Проголосовать: нравится -13 Проголосовать: не нравится

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

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

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

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

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
19 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится +16 Проголосовать: не нравится

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

»
118 минут назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I agree that during-the-round hacking was pretty useless now. In problem F of the recent Codeforces Round 1100, many people around me submitted code with incorrect complexity (with some pruning) and passed the system test. Seems now people are focused on solving problems, and none of them are thinking about hacking others. Also, solving the problem before hacking reduces the number of people who were able to hack. Even if you solved the problem, there must be someone else in your room who also solved the problem for you to hack; for difficult problems, the conditions were really hard to meet. This leads to many wrong codes passing the system test.

I suggest removing during-the-round hacking and add 12 hours open hack to every round, just like the edu round and div3/4 did.