VeniVidiVici's blog

By VeniVidiVici, 5 years ago, In English,

I will attempt to explain why I think people do this, and hopefully start a serious examination of how to deal with the problem...

struct Warning{
  long long story;
}; 

Label: Meet Bob. Bob has always been a pretty bright individual. Deciding that he should use his intelligence for good, Bob decided to put his skills to the test. As Bob knows, people use computers for programming. Because Bob owns a computer, he figures he must be a programmer as well. So Bob decided he was going to create the best game ever — one that would inspire a generation of children to waste their lives chasing pixels — solely with the power of his mind. Absolutely sure of how to continue, Bob promptly opened up the command prompt. This made sense to Bob because he once saw a monospaced screen in a movie where some dude hacked the government in 90 seconds. He proceeded to type in his masterpiece:

open a new window
make the background look like trees
put a guy with a gi in the middle of the screen
every 2 seconds randomly send out another guy with a gi from one end of the screen
set p to punch and k to kick
return 0;

Unfortunately, Bob was told "'open' is not recognized as an internal or external command, operable program or batch file". Utterly confused, he curses out his stupid computer for being too stupid to figure out what he wants. Surely any idiot could figure out this paragraph! What fool designed this computer anyway? It's completely broken! THINK OF THE CHILDREN!

So Bob promptly threw away his computer and bought the new iComputer v201.39428012 with all the special features. Unfortunately he couldn't find the command prompt anymore. Finally he decided he would admit defeat — he needed help. But of course nobody could know this, so late at night, when everyone was asleep, he gathered up all his supplies and gently, gently, gently snuck down to his computer. Checking to make sure nobody was watching, he went to his computer, enabled the "hyper-super-privacy" feature, and typed in the fateful words... "google.com".

Bob was fascinated. No wonder his "program" didn't work before — there were very specific rules on how to do things! Bob studied these links all night and made his next attempt:

import java.io.*

class IAmAnAwesomeProgrammer{
  public static void main(String[] args){
    long long temp;
    vector< vector<int> > nums;
    cin >> temp;
    def add1(x):
      return x+1
    return 0;
  }
}   

But once again, his stupid computer couldn't figure out what he wanted. Stupid developers! Bob had followed all of the instructions he found on the internet — how could SexyCoder123's post from 2003 be wrong? Now Bob was more determined than ever. The days went by. Days turned into weeks. Weeks turned into months. His favorite games turned into wastes of time. His weekends turned into all-night coding sessions. School turned into... welp... still school. But finally, after precisely 3 months, 1 week, 4 days, 1 hour, 59 minutes, and 26 seconds, Bob declared himself ready. He sat down in front of that computer, which was now 17 versions outdated, and wrote the most beautiful program he had ever laid eyes on. But Bob wasn't satisfied. You see, Bob is a very competitive person. He loves to succeed, loves to see the fruits of his labors. But more than that, he loves to win. And so he decided to put his newfound skills to the test...

It was 2:30 in the morning. Everyone was asleep. All through the house, not a creature was stirring, not even Bob. Ah, who am I kidding, Bob was perfectly awake. After checking to make sure nobody was watching, he snuck over to his computer, enabled the "hyper-super-privacy" feature, and searched for "programming competition". Being an experienced internet surfer, he skipped the first two links and clicked on "topcoder.com". It was a fateful day in Bob's life. Well, at least it would be if he could figure out the website. So Bob promptly gave up, but not before discovering another website: "codeforces.com".

This one Bob could work with! He created his account, "conqueror_of_tourist", and got ready to lock horns with tourist and Petr and all these other guys with fancy red names. This made sense to Bob because his friend had tried out for the national football team despite his refusal to run. He registered for his first contest, but this stupid system made him compete in the second division. How could he defeat tourist now? Oh well, he'd have to do that next time.

The next day, Bob awoke bright and early at 11:25 AM. He began to fall back asleep, but then suddenly remembered why he was waking up so early — it was time for programming! He rushed to his computer and began the contest. He saw five problems, and decided to start with problem "B" — B for Bob!

20 minutes later, Bob was confused. "Who the hell is Dima?" he thought to himself. But Bob was no fool. With his many days of experience, he put together a rock solid solution, and submitted it. "Compilation error" the system said. "Compilation error?" said Bob angrily. "But I looked at it before I submitted it and nothing looked wrong!" he thought to himself. This made sense to Bob because his friend regularly submitted essays that he did not bother to proofread for grading. Finally he mustered the courage to actually test his code. After finding the problem and testing his code extensively with the case n=2, he decided it was clearly correct and sent it on. "Pretests passed" the system said. Bob felt pretty damn good.

The rest of the time Bob worked on problem E, because there was no Dima in that problem. This made sense to Bob because his friend had tried to use a 25-pound bowling ball despite being only 80 pounds, since it was the biggest one. Finally, with just 3 minutes remaining, he submitted his solution. Once again, "pretests passed". Bob was very proud of himself, because when he clicked on "room" he was the top guy. "I'm the best on this silly website." thought Bob to himself. He then went back to sleep.

When he woke up, he received his very first rating: 1312. He was very proud of his shiny new rating, and went to go look at his room again to see exactly who he crushed. But there must have been some bug — he wasn't on top anymore. In fact he was now 14th in his room. He noticed something else strange — that number in the "B" column was green while the one in the "E" column was a big glaring red "-1". After overcoming his initial excitement at being red, he clicked on the big "-1" to see "Time limit exceeded on test 11". "What?", Bob exclaimed, "But I checked every permutation!". Unfortunately n was 10^5. Who is that stupid Mike guy anyway? Not giving my program enough time to run. What an idiot.

This was just a minor setback to Bob. After all, a tricky testcase might trip up anyone's O(n!) solution because of some silly error. Next time those tricksters wouldn't be so lucky! And so Bob continued, participating in every contest for the next 1 month, 6 days, 18 hours, 03 minutes, and 39 seconds. Slowly he began to understand the whole system, and was now particularly adept at solving the first 2 problems within an hour. His efforts had not been for naught — conqueror_of_tourist now sported a shiny 1552 rating, far ahead of those newbies who joined last week.

Bob had come so far, but it wasn't enough. You see, tourist would often solve 4 or even 5 of the problems, while Bob could solve only 2. Now it was time to get serious. Bob disposed of his old computer and bought a PC running Windows 17.82, which had none of the bugs Windows 17.81 had. And his true training began. Bob first set off to the adjacent town of Naboo, seeking the reclusive yet famous Master Knuth. Under the guidance of Donald's third cousin twice-removed, Bob matured as a programmer and reached all new heights — he was now able to solve problem C once in a while. Master Knuth also taught Bob to fight dirty, teaching him how to put mere mortals in their place by exploiting their mistakes, such as integer overflow, incorrect bounds on their binary searches, tricky n=1 cases, and the like. Bob was now ready.

In Bob's next contest, he pulled off the crowning achievement of his short career. Not only did he solve problems A and B, he also submitted a completely correct solution to problem C! Now Bob was beaming with pride. But the contest wasn't over yet, still 40 minutes to go. Unfortunately for Bob, problem D was titled "Dima and the anti-Bob problem", so he decided to use his newfound hacking skills to push him over the top. And hack he did. Bob quivered with excitement as he submitted his first hack. Then a second. Then a third. But he didn't stop there, Bob submitted fourteen hacks! With an impressive +4:-10 next to his name, Bob knew he was headed to the top.

And to the top he was indeed headed. This incredible result sent Bob into the upper echelons of competition, with a new rating of 1701. Bob had never been happier in his life. Newly confident in his social status, Bob picked up girls by telling them he was division 1 on Codeforces. Strangely, when he called the numbers a week later, they were all disconnected. What a coincidence. But I digress...

It was time for Bob's first division 1 contest. He noticed with excitement that tourist was registered for the contest as well. All Bob needed to do was perform a little bit better than usual, solving problem D in addition to the first 3, and he'd have a fighting chance at taking down the best. But problems A and B were unusually hard this time, and Bob wasn't able to solve any of them! An hour passed, and Bob was still stumped. "Oh well," Bob thought, "everyone else must be having difficulty as well". So he went to see how tourist was doing. Unfortunately for Bob, tourist had finished all the problems in 46 minutes. Whoops.

Frustrated, Bob didn't submit a single solution and went to bed. Visions of the failed contest haunted all his dreams. How could he not have solved a single problem? Surely he was ready for division 1 — the system had placed him there! This made sense to Bob because he knew the internet is always right. But Bob was determined. After all this time, he was not going to back out now. Bob redoubled his efforts and aimed towards the top...

Unfortunately for Bob, the next contest went exactly the same way. And so did the next. And the next. Finally, after plenty of experience struggling with the division 1 problems, Bob submitted his very first division 1 solution — which was accepted! Bursting with joy at his first solve, Bob collected 294 points for his achievement. Now, since Bob had always locked problem A and gotten lots of hacks off of silly fools before, he decided to do the same here. This made sense to Bob because his friend had once tried to teach a class after learning the material 3 minutes beforehand. Unfortunately, it turned out that these codes were much more complicated. Now simply bound-checking was insufficient! Bob ended the contest with no hacks, but the joy of solving a problem remained. However, his fall from glory still disappointed him. Bob's rating decreased to 1661.

Although Bob was disappointed at his rating drop, he figured that at least he was progressing. It was a slow, boring, painstaking process, but eventually he'd get to the top. But now the task seemed more daunting than ever. Having matured a bit, Bob now understood that it would be a long long time before he would ever be a successful division 1 competitor. This saddened him deeply, as he realized the journey was far longer than he had expected...

The next contest, Bob was back into division 2. He checked his room and recognized some of his old rivals — "not_tourist" and "wish_i_was_tourist" — neck and neck with him for the lead. The old competitive fire returned, and Bob was once again motivated to win. But division 1 had changed him. He solved both A and B, but he did so relatively slowly. Instead of his usual strategy of hacking on those problems, he instead turned to problem C. An hour later, he admitted defeat and went to hack the problems. Unfortunately for Bob, not_tourist was +6:-1 and wish_i_was_tourist was +7:-3. All the hacks were taken. Bob managed to get one in near the end, but it was nowhere near his previous performances. His rating decreased again to 1638.

Bob now realized that, for him, division 2 was more fun to compete in. Div1A was just too hard for him, and he didn't want to spend all the effort to become the very best anymore. His other interests, such as CtarSraft and World of CarWraft, seemed to dominate his time more and more. So he decided he would stay in division 2 and do the contests just for enjoyment.

Of course, he quickly returned to his old form, and he roared back to division 1. But now he was in a bind. The next division 1 contest was still 3 weeks or so away, and he wanted to compete! So he waited patiently, and when the next division 1 contest came, he gave it his all but ultimately returned to division 2. This cycle repeated for several months. Finally, Bob had had enough of it. Knowing that he was not deserving of division 1, he came up with his master scheme...

In the next contest, Bob reached division 1. But he would not wait weeks this time! Instead he created the subtle "definitely_not_conqueror_of_tourist" and sneakily joined. This made sense to Bob because his friend had once purchased a stolen identity and hadn't been arrested for a whole 3 days. Nobody noticed a thing. Unfortunately for Bob, this account also made it into division 1 in just 2 contests. Well, darn. So he made another account. And another. And another. Soon he had amassed an army of accounts in the 1710-1720 range, but the old competitive fire was gone. No longer did Bob dream of unseating tourist; rather his dreams were filled with "Successful Hacking Attempt". And though Bob became one of the fastest on Codeforces at solving Div2A+Div2B, he was never able to consistently solve a Div1 problem. Bob faded into the background, and slowly people forgot who he was. Nobody was making a note of all his accounts getting 250th place every contest, and frankly nobody really cared.

All this changed one day. Bob had just made his 38th account, "conqueror_of_tourist_38", and was ready for his competition ritual. But on that fateful day, everything changed. Bob, as usual, solved A and B within 10 minutes. As was his protocol, he then tried C for 10 minutes before moving on to hacking. But today, something was different. This C was unusually easy to Bob, as there was a simple greedy strategy known to him from playing the CtarSraft minigame "greedy strategies". Suddenly Bob was on the top. "What the hell," Bob figured, "might as well try D". But Bob knew D. He had seen D. Problem D was titled... "Dima and the anti-Bob problem". "Unbelievable", thought Bob, who proceeded to submit the solution 10 minutes later. Bob then went to collect some hacks, which he amassed 6 of on problem B where a silly grey coder used strlen() in a loop condition and some more forgot to check for integer overflow. Bob was on the top of the standings. Nobody would solve problem E that contest, and Bob's solutions passed the system tests. Bob had won.

"WHO IS THIS NEW CODER WHO WON THIS CONTEST" screamed the masses. "Clearly," they reasoned, "this is a division 1 user who has nothing better to do besides make division 2 accounts to try and win". Well, they reasoned correctly. "Why would he possibly ever do such a thing?" yelled the masses. "Well," responded Bob, "...goto Label". Bob then faded out of the spotlight, and would never be heard from again.

...until "conqueror_of_tourist_39".


So what was the point of this really weird/long story, and why should we care about Bob? Well, if you can find even 5% of Bob inside you, you're looking at a few hundred people who are going to feel the same way as Bob. And, frankly, you'd be lying if you said you couldn't relate to Bob's struggles at all. Should we condone what Bob does? Of course not. Not only is it against the rules of the site, it helps to ruins the experience for thousands of other coders — many of whom still seek the dreams that Bob once had. This is unfair and should not be tolerated. But we need to understand Bob's motivations if we want to create a meaningful solution, rather than just shouting "ban the cheaters!" and wondering why more keep cropping up. That reasoning might make sense to Bob, because his friend kept killing the flies in his filthy house but couldn't understand why more kept coming, but it should not make sense to you.

In my view, there are three main issues that lead to the creation of multiple accounts:

  • Division 1 contests are significantly rarer than division 2 ones. The ratio seems to be somewhere between 3 and 4 division 2 contests for every division 1 one. Although users can still compete out-of-competition, it is not hard to imagine that they wouldn't feel the same fulfillment. This is not a problem easily rectified, as division 1 contests are much harder to write. Which brings me to...
  • There is a large gap in difficulty between division 2 and division 1. It is hardly unusual for someone to reach division 1 with nothing but a decent A+B time and reasonable hacking skill. Solving the occasional C, which is certainly possible as some Cs are surprisingly easy (i.e. today's), speeds up this process. This leads to a huge influx of competitors in division 1 who are clearly not ready for it. We don't see this magnified as much because many of these coders either don't bother showing up or don't make any submissions, but outside of an unusually easy A I'd be willing to bet that at least half of division 1 participants don't solve a problem.
  • Finally, division 2 has a great deal more hacking. This is due to two main factors: the fact that most division 1 participants got there, at least partially, by exploiting common hacking tricks — meaning they are far less vulnerable to falling for them — and the fact that the problems are harder, so solutions are more difficult to understand (and usually longer). Hacking is obviously one of the most enjoyable parts of competition, which further explains the appeal of div2 over div1.

How can we tackle these problems? That is the difficult question, and I have no good answer — hopefully all of us can create one together. Optimally there would be a smoother transition from division 2 to division 1, but when considering this we need to be careful to not alienate those who should be in division 1. In other words, we don't necessarily want to change div1A to div2B from div2C, even though this would lead to a smoother transition, because then the very large group of people who can solve div2C consistently but not div2D will have their placings largely determined by the speed in which they solve div2B, clearly not an optimal situation. Of course we face similar problems if we want to say "ok, then make div1A=div2B and div1B=div2C" with those who can solve div2D but not div2E. We also don't want to water down the difficulty a great deal, as we already have all 5 problems solved by someone on a regular basis (or whenever tourist competes :P). Furthermore, we can assume that problems are hard to come by and any possible solutions should not add the total number of problems written for a div1/div2 contest combination (of which there are 7 distinct ones). For example, saying "write another div1A problem that is slightly easier than div2C" is unlikely to ever happen because this would increase the number of problems that need to be written. Saying "include div2B in the division 1 contest as a 250-point problem" might make some sense, but it would certainly break traditions.

So how can we deal with these problems? It is tempting to simply say "ban the cheaters!", and certainly this is a respectable position, but we cannot miss the underlying foundations of the problem or the cycle will never end. I've wasted enough of your time already, so any thoughts at all?

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

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Did you write it by your own or copy paste?

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Cool story, I liked it:D

»
5 years ago, # |
Rev. 3   Vote: I like it +22 Vote: I do not like it

This story is awesome.

By the way, there is a simple solution, which Codeforces has been doing: Div1 contestants can participate in Div2-only contests out of competition. The only things that I'm still thinking are:

  • If a contest is available for both Div1 and Div2, may Div1 poeple participate in the Div2 contest out of competition? I'm inclining for no, as long as there are enough Div2-only contests for Div1 to occasionally play in.
  • Should Div1 contestants be considered rated or unrated when they play out of competition? Here I'm inclining rated, as long as we compare only to other Div1 contestants. I can't see any reason why Div1 contestants should be unrated when doing Div2 contests. Making everything a battle of speed? Not much difference from most people fighting for speed in A and occasionally B in Div1 contests.

There is also another possibility, break divisions into three: Div1, Div2, and Div3. The current Div2 becomes Div3, and the new Div2 gets the problems Div2B and Div1A-D. So if we order all seven problems of a contest in increasing difficulty A,B,C,D,E,F,G, then Div3 gets A-E, Div2 gets B-F, and Div1 gets C-G. This makes a reasonably smoother transition, at the expense of making each division to have less people and various other things.

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

    Making everything a battle of speed? Not much difference from most people fighting for speed in A and occasionally B in Div1 contests.

    Why is this argument so common? Most people fighting for speed (for some definition of most) is vastly different from everything being about speed. Do you want a fast coder to get 3000 rating by doing nothing but solving Div2E fast? Div1D and Div1E aren't meant for everyone, they're meant to separate the best contestants. Something a Div2 round will not be able to do.

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

      In my opinion, competitive programming is half about speed, not only about figuring out solutions to problems. If speed is thrown out from the equation, you have online judges.

      If you don't want Div2 contests taken by Div1 to matter a lot, the rating changes for Div1 can be halved or something like that, to suppress the effect.

      Another idea: each contest can have all seven problems available to both divisions, so both divisions use the same problems, probably with different scores (A-B, which would be Div2A-B, would score only 250 in Div1 but 500 and 1000 in Div2, for example). They still fight within their own divisions, of course.

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

    I like the idea of 3 divisions.

    There are good number of div 1 contestants who can solve only problem A during competition. (Around half solved only problem A in the last contests, #263-1)

    It does not sound reasonable to decide the rating of more than half of participants based on whether they spend 5 min or 15 min on one particular problem.

    Also it's not really fun. I usually don't have much to do in div 1 contests, once I'm done with problem A. I honestly enjoy div 2 more.

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

      I usually don't have much to do in div 1 contests, once I'm done with problem A.

      And that's the secret to success. Even if I don't think I can solve some problem, I'll still read it and try. As much as possible. For example Codeforces Round #167 (Div. 1): I solved A,B, read C and tried to solve D — and I remember that I got somewhere, although I couldn't solve it back then. And my rating still decreased due to time, but well, what can I do when I was running from a bus stop when the contest started — doesn't matter, it's about trying.

      You don't have to solve the problems in alphabetical order, either. My second best div1 result comes from solving A quickly, then nothing for a long time and then quickly solving D and C — I never even solved B in that contest, not because I didn't bother, but because I didn't know (sometimes, it's hard to notice something due to being so simple :D).

»
5 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

help why is this posted twice

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You are talented

»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Topkek. This was seriously funny :D

  • Instead of div1 vs div2 contests' ratio, we should look at mixed vs div2 contests' ratio: around 5:3 in the last Contests page. That's not so much that it should need changing, considering there's an influx of new competitors (apart from the cheaters) and div1 rounds drop some people down, so div2 rounds have to be more frequent than mixed ones.

  • There's a large gap between many people's skills — that you can solve easy problems (up to div1 A) in a short time doesn't mean you'll be able to solve a more difficult one (div1 B) even if you got more time, while many other people can. In that case, you should go back to div2 and lurk moar until you can. I know from experience.

  • To be honest, I'm okay with few hacks if it means the pretests are strong enough. If there are 100 hacks on a B+ problem in div1, something's more wrong than if there are none. It also depends on specific problems — some are hackable easily, some are not. Making a problem that has the right difficulty, hacking chances, is interesting and giving it a place appropriate to its difficulty is incredibly hard. If you have some, you should send them.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Ban Bob and the problem will be solved :D

Maybe making a Codeforces account require a valid phone number would decrease cheating?
But I dont know if it would be impractical, what do you think?

»
5 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Very interesting story! Thanks.

I think one factor which contributes to this is, many div1 participants don't submit solution for A if they can't solve it within reasonable time. Look at topcoder div1 rounds, you can see a lot of people who did open 250 but didn't submit it. They get added in the rating change, but here, nothing happens. So, most of the new comers who solve A get deported back to div2.

Edit: There was a analysis done by DmitriyH.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My English isn't enough to understand this blog :(

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

I am Bob's friend.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First of all, I think that the rating remain same if you don't submit should be removed. Second, I've got a question. How did TopCoder handle the following thing:

Have a fake account, see, a task, do it, go to your main and submit it for maximum amount of points.(Nothing to do with this, just wondering :D)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Topcoder usually bans the cheaters they catch.

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Why not simply allow Div 1 participants to join the Div 2 contests, but make it rated for them also? In that way, Div 1 and Div 2 coders will be happy without interfering with each other. Of course, the contests will be a lot easier for Div 1 participants, but well, they have choice after all.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem is precisely that it'd be too easy for div1 participants, which means many would solve the easier problems very easily and time would be almost the only tiebreaker, plus it'd be frustrating to lose many places (possibly hundreds) due to a small mistake or hack/resubmission by the end of the contest.

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

      Quite a lot of Div1 participants are not able to solve Div1 A, B, and C consistently, so why would a div2 only round be too easy for them, considering that D and E on div2 only rounds are usually a bit harder than the D and E on contests for both divisions?

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

        Conversely, a lot of div1 participants are able to solve A-C. And if a round is rated, we can expect the number of participants to be roughly the same as with regular div1 rounds. (Granted, the last div1 2 rounds had hard D and E, but that doesn't always happen.)

        And it seems that div2 only D has become easier lately.

        The idea of 3 divisions seems to work better here, but that'd probably be tough to execute.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I agree with you, I think the 3 divisions is one of the best ideas, and it's probably difficult to implement, but it would definitely help with this problem.

»
5 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Tl;dr, but looks cool!