Hey, I wanted to start new series about hacking. I think that this part of programming contests is really underrated, but can be helpful for both people solving problems (you should know what tricky cases you need to consider) and people writing problems (you should know how to write nice tests covering everything).
So in this series, which I will try to continue, I will talk over hacks at Codeforces Rounds. I will try to do some statistics and take a look at most common mistakes in passing contests.
It is my first article related to hacking (and first at all :)), so feel free to suggest something, correct me on some errors or mistakes (my English still can be much better :)) and tell about your hacks. Thanks in advance!
So let's move to Codeforces Round 262 (Div. 2).
Update: added country wise statistics (at the end).
Update: added chart with hacks over time and first hacks.
Update: the handles are now full of colours, with many thanks to awesome accidentallygivenfuck!
Update: added section "biggest gap" (between rating of the hacker and defender).
Stats
Problem | Successful hacks | Unsuccessful hacks | Other | Sum |
---|---|---|---|---|
460A - Vasya and Socks | 23 (26%) | 53 (61%) | 11 (13%) | 87 |
460B - Little Dima and Equation | 622 (67%) | 254 (27%) | 58 (6%) | 934 |
460C - Present | 76 (48%) | 33 (21%) | 51 (32%) | 160 |
460D - Little Victor and Set | 3 (38%) | 4 (50%) | 1 (13%) | 8 |
460E - Roland and Rose | 1 (100%) | 0 (0%) | 0 (0%) | 1 |
Really nice graph made by soon (thank him here):
And my graph showing hacks over time:
Remarks
It looks like problem B was the most grateful for hackers (above 600 successful hacks and it was nearly of all tries!). But still, every solution has at least one successful hack.
460B - Little Dima and Equation
This problem had a lot of successful hacks! The most frequent mistakes were:
- printing solutions that are negative or bigger than 109
- forgetting about using 64-bit numbers (sometimes numbers can be too big for 32-bit)
- wrong upper bound for sum of numbers, it should be at least 81 (more than this, like 100, was ok)
And there was pretty wrong solution which can pass the pretests: checking all numbers to some number fitting into time limit (like 1000000).
460C - Present
There were two most frequent types of hacks. First one was just giving big n, m and w. In this case solutions with complexity O(nm) described in tutorial was failing. Second one was using the fact that the result can be bigger than 109. Many people using binary search just forgot about it and set upper bound to just 109. Simple hack:
1 10000 1
1000000000
The result should be 109 + 104 in many programs it was around 109.
460D - Little Victor and Set
All hacks were just big x and y and k = 3. It was destroying naive approach in such case of k.
460E - Roland and Rose
The one and only hack for problem E was this one, the solution reached time limit.
Fast hackers
Problem | Time | Hacker | Defender | Hack |
---|---|---|---|---|
460A - Vasya and Socks | 00:27:08 | MKGAURAB | windy_sai | 108845 |
460B - Little Dima and Equation | 00:23:51 | linjek | MakArt | 108834 |
460C - Present | 00:35:44 | Heart_Blue | takapt | 108873 |
460D - Little Victor and Set | 01:03:07 | ngfam_kongu | takio | 109096 |
460E - Roland and Rose | 01:59:38 | 4erneff | indestinee | 110005 |
The one and only hack for E was done in the very last minute of contest. Congratulation 4erneff!
Best hackers
Hacker | Stats | Successful hacks | Unsuccessful hacks |
---|---|---|---|
VladaMG98 | +11-2 | B: 108866 108881 108902 109084 109161 109431 109443 109461 109494 109553 C: 109866 | B: 108863 108906 |
Honour_00 | +10-0 | B: 109047 109058 109091 109104 109115 109252 109557 109583 109599 109827 | |
linjek | +10-3 | B: 108834 108857 108888 109152 109194 C: 109469 109580 109668 109796 109836 | B: 108948 109024 C: 109928 |
pk. | +8-0 | B: 109129 109275 109294 109324 109417 109429 109451 109780 | |
KingTon | +8-0 | B: 109134 109138 109385 109629 109843 C: 109595 109669 109709 | |
Nero | +9-3 | B: 108944 108956 108980 108994 109038 109067 109093 109103 109120 | B: 109009 109080 109172 |
Best rooms
Room | #hacks | Hackers | |
---|---|---|---|
66 | 15 | linjek [10], Baridcse [5] | |
69 | 14 | VladaMG98 [11], fiter [2], WorstCoder [1] | |
1012 | 13 | Rebryk [3], Kvark161 [3], FatalEagle [3], BigBag [3], ngfam_kongu [1] | |
1011 | 13 | meodorewan [6], Napoleon_cn [4], MilkyHolmes [2], lucaslima [1] | |
50 | 13 | muratt [7], aswmtjdsj [6] | |
31 | 13 | KingTon [8], vengarth [5] | |
83 | 12 | Devasundaram [5], 31smurfs [5], mufasa [1], mengshangqi [1] | |
77 | 12 | rabbitlover [6], SameerGulati [3], phankhai [2], anhphi257 [1] | |
1009 | 11 | Nero [9], Romchela [1], Misha100896 [1] | |
67 | 11 | prathyu [6], maguih [4], goga24 [1] |
Countries
You can see that worse had 2 successful hack attempts (and 22 unsuccessful :)). And let's see what will happen if we take all successful hacks and divide by number of people who tried to hack (with at least one hack attempt):
Country | #hacks / #hackers | Hackers (with at least one successful hack) |
---|---|---|
Colombia | 6.00 | jhonber [6] |
Turkiye | 4.50 | yEmre [8], muratt [7], kalimm [7], ikbal [6], kursatbakis0 [3], ykaya [2], KayacanV [2], WorstCoder [1] |
Serbia | 4.00 | VladaMG98 [11], allllekssssa [1] |
Cyprus | 4.00 | michael10024 [4] |
Belgium | 4.00 | jorik [4] |
Biggest gap
In this section I took all successful hacks and looked at difference in rating between hacker and defender. There were 18 "new" hackers (it was their first contest), so I simply miss them from obvious reasons.
Hack | Hacker | Defender |
---|---|---|
109378 | worse [206] | impiry [1565] |
109375 | worse [206] | CAUTION [1285] |
109383 | Artem_kh [1757] | dreamoon_love_AA [2562] |
109684 | jhonber [1044] | David.Zhang [1664] |
109630 | jhonber [1044] | 0x666 [1642] |
109712 | MilkyHolmes [1748] | ballon [2249] |
109491 | jhonber [1044] | Nitto [1504] |
109717 | m17 [1780] | yuusti [2219] |
109483 | Programist [1735] | Shangke7788 [2150] |
109674 | stalker506 [1714] | sweiss [2117] |
Thanks for your feedback!
Great Idea! I think it would be very nice to see what type of hacks there were during the contest!
This is a really smart series. I struggle with hacking, so tutorials like this on what to look for and how to break common errors would be appreciated!
I've made simple graph with hack stats. People prefers images to plain text :)
Stats with numbers here (not sire if codeforces allows
iframe
inside posts)iframe
is not working (at least for me), but still thanks. I thought about it, but I was quite lazy :)I'm working on wrapper library for codeforces API. It is almost done, I just have to add some examples of usage. Plotting this graph was one of them. How do you think as a contest owner, what data should be also visualized?
I was thinking about hacks over time (to see when people are hacking and so on), but as I said, I don't have any particular ideas about what should be included :))
I am looking forward to your library.
soon Any update with your wrapper library? I'm really excited about that ^_^ Could you share it with us, that would be very helpful :)
The library is ready to use, and I posted an entry in my blog about it, but did not get any effort (neither positive, nor negative), so, I just put it on hold.
You could find library on Github and read the post in my blog.
Keep this work! The more statistics we have — the funnier it will be to solve solutions!
DmitriyH style
My B and C failed on not checking <10&9 and taking 10^9 as high, so i just wondered am I am the only one :D
Wow, problem B the best this year for hackers!
Wtf?
Country #hacks / #hackers Hackers
Serbia 4.00 VladaMG98 (11), allllekssssa (1)
Hacks is 12, but hackers is 2, 12/2 == 4???
There was one guy who had hack attempt, but it was unsuccessful. I didn't want to add
some_handle (0)
.Good idea! We should list the common mistakes for every future round.
Very nice post. It can also come in useful for people (especially novices) trying to debug their WAs.
very nice stats! i see u are DmitriyH v2.0! :)
a couple of suggestions, if i may:
Second: done.
First: I had problems with colouring handles in tables (it simply didn't work). I asked accidentallygivenfuck how he managed to do this. I will try to do this for next round.
Now first also done :)
great work! hope you can continue making these stats for every round! :)
Have you written some software which generated those tables for you (->impressive), or have you really typed all that (-> "impressive") :P?
If by "software" you mean one simple script, which was using CF's API, then the first option.
I am not that kind of guy who would like to look at every single hack (there were over one thousand in last round :)).
You will do statistics for Round #263?
Sure, I need to wait for hacks to appear. :)