VLamarca's blog

By VLamarca, history, 4 months ago, In English,

Hi!

In this blog I would like to humbly suggest a change in how hacking is calculated in CF rounds. I've talked to some of my friends and they agree that it feels a little unfair that someone who solved more problems scores less than someone who hacked more. A great example from where this happens is from the top positions (and other positions too) in today's round: Codeforces Round #482 (Div. 2) .

I have two main suggestions on how to calculate hacking points in a way that I consider fairer. The specific way may vary, but the key points are:

1) The more you successfully hack a certain problem, the less you should score with it. This means that the first hack on problem A should get you 100 points, but the second 50, the third 25 and so on (or something like this, maybe keep 50 for all the following hacks starting with the second one). I feel that a decreasing function for this is fairer because, in most cases, when you hack a certain problem, it is easier to hack it again. It only depends on luck to have lots of people in your room that made the mistake you spotted. Notice that, in this suggestion, if you hack problem A one time and then problem B one time, both of them should get you 100 points each.

2) The harder the problem, the more you should score by hacking it. This means that hacking problem A should get you 100 points, and hacking problem B 150 points, or something like this. I feel that in most cases it is harder to hack harder problems because generally their solutions are longer and therefore harder to read. Also fewer people solve harder problems, so it makes sense to increase the value of hacking them to make it more attractive for people that did passed pretest for this problem to try to hack others' solutions.

I am happy to discuss ideas in this regard.

Thanks for reading! (Also if you spot any mistakes in my english I would appreciate to hear about them in my private talks :) )

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

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

It's harder to hack when there are fewer (and weaker) pretests that has little to do with the problem difficulty as you can see from Codeforces Round #467 (Div. 1) where Div1B had a lot more hacks than Div1A.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it -35 Vote: I do not like it

    You are right. But I still believe that it is reasonable to increase the value of hacks in harder problems. Maybe A and B could have the same score (because I assume they are almost equally the most hacked problems anyways), but I feel like hacking problem D should give you more points than hacking problem B.

    Maybe 100 — 100 — 200 — 300 — 300 would be fairer.

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

      300 points for a hack!?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        300 hundred points for a hack in a hard problem. In the last contest there were only 3 hacks in problem C, 1 hack in problem D and 0 hacks in problem E.

        Also notice that this second suggestion along with the first suggestion should not make too drastic of an impact.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I agree with the first idea this will make contestants focus more on solving problems than hacking

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Couldn't agree more

I think 100 points is too much for hacking, I would go with 25 points, or 50 max, but not 100!!!

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

Part 1 I think is fine.

For part 2 I disagree. We have already seen cases where cheaters will make a ton of alts, then hack themselves if they are in their own rooms. The most obvious cases have been caught, of course, but nobody knows how many times it happened with only 1 or 2 hacks on the fake accounts. And even those hacks can significantly alter ratings. If you make the higher questions worth more points then this problem may become worse.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    Your point is valid but I keep my position.

    The score distribution should not be too drastic. Maybe something like: 100 — 100 — 200 — 300 — 300

    Also hacking harder problems is way more infrequent, which makes it easier to spot any possible cheaters that try to do so on harder problems.

    Imagine the scenario of cheating: You need an alternative account in your room. The alternative account also needs to pass systest in the harder problem with a possible hack. It can not be an obivious hack like:

    if(specific test) print wrong answer

    Because this is too suspicious and will get caught. Also you need to solve the easier problems because otherwise it becomes too obivious too. People will notice that someone solved only one harder problem and he also happens to get hacked in it. So you need to code in a style different from your own for all other problems just to get a few extra hundred points.

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

      Alternate doesn't need to solve the easier problems, I see a lot of legit players only solving one or two hard problems before.

      Honestly, an edge case is really easy to also put in, like if (ans == 1) print -1, and can't attract any high confidence of cheating.

      I think a score distribution of 25 — 25 — 50 — 100 — 100 (without the part 1) is much more reasonable. 300 points is way too much, in a contest with mostly flat scores that could be difference between -20 and +40.

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

        "if (ans == 1) print -1" are generally in pretest. It is very akward to squeeze in a corner case that does not exist (unless the pretest does not have the most common corner cases, which is very rare for harder problems)

        Anyways the main suggestion in my blog is indeed the first one.

»
4 months ago, # |
  Vote: I like it +59 Vote: I do not like it

I think the real problem in these rounds is not that hacking is worth too much — it's that hacking is too easy. Contest authors should stop giving such tricky problems with such weak pretests.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -25 Vote: I do not like it

    "Contest authors should stop giving such tricky problems..."

    Lol, maybe they also should write a solution in statements? Talking about topic, weak pretests are really not good. But everyone has the same conditions, so it's still fair.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

      But everyone has the same conditions, so it's still fair.

      For example, there are 10 hackable solutions in one room, and 20 — in another. Are the hackers from these rooms in the same conditions?

      BTW, I love current hacking system, even if someone has more points than me because of hacks, it doesn't really influence on my rating change.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +43 Vote: I do not like it

        I actually remember situation when I saw that many people on top of scoreboard had something like 7-10 hacks in A and I started browsing people's A in my room and found just one flawed solution and later it turned out that all other solutions were correct. Moreover it is also highly random whether someone from your room already started hacking (in which case there are probably no easy hacks to get) or not.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +46 Vote: I do not like it

      You cut a pretty important piece of that sentence when quoting subop making this quote highly biased. By the way "tricky" may have two meanings. First, positive, where this means that solution requires some nice trick to come up with and second, negative, where it means that there is some hard to spot corner case or some different trap. And here second meaning was used and when it is combined with weak pretests it causes that half of participants who basically solved this problem fail systests (my "favourite" one is this http://codeforces.com/contest/549/problem/C where there was a game which could have lasted for 0 turns...). I'm also not a fan of such situations and agree with with Neil that we of course can't ban problems with corner cases, but when they appear pretests should cover these tricky cases.

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

        Exactly, I wasn't saying we shouldn't have problems with lots of corner cases, as long as the pretests are reasonably strong.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Last three paragraphs from this comment are my vision about hacks. It's not a solution to the problem, but it's a strong way to alleviate the symptoms.

»
4 months ago, # |
Rev. 2   Vote: I like it +72 Vote: I do not like it

When I saw VLamarca posted second "Please change (...)" topic I thought that he is actually on a roll after instantaneously implemented suggestions about divisions changes and suspected that this one won't be that good. However it is actually the opposite, I think that these suggestions are really very good.

Regarding 1). I think this is great.
1)1) It is obvious that total score gotten by hacks has a really big variance from contest to contest. It would be good thing to prevent situations where many people have many hacks because they noted some corner case in A and they overtake people who solved what they solved and additionally D.
1)2) When there is a highly hackable problem there are big inequalities introduced by partitioning to rooms. It can be a case that number of wrong solutions vary significantly from room to room (see one of my above comments) and that would flatten the differences.
1)3) It is pretty random whether there is somebody in your room who noted that tricky case in A/B and already started hacking in which case you are probably left with no easy hacks to get what introduces a big random factor. Suggested change would also help to flatten differences resulting from that.

2) This is also a really good suggestions as hacking E is way harder than hacking easier problem. You need to solve it by yourself, you need to have second person in your room who has also solved it (however this is sadly random) and you need to find flaw in probably a pretty complicated and long code.

I agree wholeheartedly with both points made by VLamarca. Probably exact point values should be better adjusted than these originally suggested (100+50+25+... is too harsh decrease, I think), but main idea behind is great.

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

    Thanks a lot for your position. I was a little bit reluctant to publish this as I already made an accepted suggestion and a second one might sound a bit cocky. I hope I do not look like this.

    Also the mentioned issue is a recurrent complain in rounds where there is an excessive amount of hacks. So I just figured I would gather those complains and make a more formal blog/suggestion about it.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I agree with (1) but it's worth noticing that all your arguments would also work for e.g. just halving points for hacking.

    (1.3) isn't that bad because you are able to see whether someone has already started hacking in your room — then you should focus on solving problems or testing your solutions. And you can decide to start hacking yourself at any moment. Like with Yandex blind submissions, it introduces some strategy element.

    Hacking E is harder so it makes sense to gain more points for that, but it increases the variation. Right now it's very unlikely to hack E (it isn't likely to have at least 2 solutions in your room and it's hard to find a mistake), so maybe let's leave it this way? I would guess that hacking A and B is usually similarly hard. It often boils down to using the same case, like n = 1 or some p = 0.

    It's nice to keep rules as simple as possible. Balancing everything is cool for us, but it makes things harder to comprehend for newcomers. It's similar to a feature that was once discussed: after locking a problem being able to submit a fake submission to see if it passes pretests. It would be nice to check the strength of pretests this way, but it's complicated for newcomers.

    I'm not strongly against the proposed ideas. Just wanted to point out some possible flaws that should be discussed.

    EDIT: One more thing against next hacks giving less points: after a few hacks every next hack is harder and harder to make.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Interesting feature is to growing score for hacks, instead of stable. To opposite to problems, we have cost of 25 for hack at beginning and 100 point closer to end of the contest. Now +10 in first half of the contest <= problem A. But if you choose to wait, until it will costs more you are risking, that somebody will starts hacking.

»
4 months ago, # |
  Vote: I like it +42 Vote: I do not like it

How about using dynamic scoring for hacks?
Looks like it solves both problems you've described

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    I thought about this too. But dynamic score for hacks alone does not deal with some points regarding fairness because if someone hacks two times problem A he gets twice the points compared to someone that hacked it only one time.

    Also I feel that this is a bit akward solution, but it is indeed not a bad one in my opinion

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

      Score for hack can be min(500/(total_number_of_hacks_on_problem_in_room), 100)

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

I really liked your suggestions, but I guess this would all be solved if the writers didn't intentionally exclude corner cases from the pretests. In my opinion, the pretests should be a small sample of the systests, just to quickly estimate the correctness of your solution. The hacker should also look for possible TLEs and bugs, not only check if the contestant remembered to include the case when n = 0, for example.

I think maybe a quick solution for that would be selecting a random subset of the systests to be the pretests (same subset for everyone).

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

    random subset will not include n = 0 test with high probability

»
4 months ago, # |
  Vote: I like it -15 Vote: I do not like it

I also wrote a same blog, but people there are downvoting. I also suggested a similar thing. but just in a rude way and with no intendation. Please read my blog and consider my suggestions. Thanks!

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

    You can add identation or make a more polite suggestion by editing your blog.

    But I believe you are getting downvoted because you posted it from a fake account, that is not cool. Also I am sure you did not copy, but I published my blog about an hour before yours.

    Regarding the suggestion you made in your blog about adding a third rating that ranks contribution of hacks made, it is a possible solution but I feel like there is no need to take away the influence of hacking in the score of contests. It is arguably good to have something to do to increase your score when there is no more time to solve other problem. Maybe just changing how the score of hacks is calculated is better

»
4 months ago, # |
  Vote: I like it -37 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I think hacking a problem should never yield more score than the problem had originally. The score per hack should be calculated with such formula that the total score of all the hacks yield less than or equal to the score the problem had originally. Say, Problem A starts with 500 score. So nobody should get more than 500 score no matter how much hacks they make on Problem A. This somewhat matches the suggestion (1) of this post.

Sorry for my poor English.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Second suggestion will never be introduced if admins would make a decision democratically (like/dislike voting). Anytime someone posts suggestion to make hacking more profitable, more folks will dislike it, and less folks will like it. Because least of participants do hacking and like hacking, and most of participants are only victims of hacking.
Whilst first suggestion is about making hacking less profitable it will receive more likes.

Anytime someone will write arguments for "how easy it is to hack", they will use easiest cases, and intentionally won't mention about cases when one need to read a dozen obfuscated codes sometimes written in not a native language and to write a script for hack test generation for bounty of 1/15 sometimes with risk of losing half.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    You know being a victim of hacking is a good thing right?

    Don't think that people only oppose decreases of hacking because they are greedy 1-step thinkers.

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Me Engravida!

»
4 months ago, # |
  Vote: I like it +53 Vote: I do not like it