kostka's blog

Hack me! (CF Round #262)
By kostka, 10 years ago, In English

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):

Here should be graph

And my graph showing hacks over time:

Here should be graph

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 HeartBlueArchive 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

Country #hacks Hackers (with more than one successful hack)
China 133 Nero [9], skyxuan [7], hnshhslsh [7], Memset137 [7], rabbitlover [6], aswmtjdsj [6], vengarth [5], Devasundaram [5], nhywieza [4], lveternal [4], DanielChau [4], Napoleon_cn [4], FinalTheory [4], I_Love_Balabala [4], Dwayne [4], MADAO_G [4], xwind [3], lin11 [3], bolyeria [3], Just_ck [3], TaoSama [3], CST14-Lee [3], Atlantis67 [3], qingping95 [2], polossk [2], dnvtmf [2], wyxourlove [2], HeartBlueArchive [2], Harry.Guo2012 [2], wwunxc959 [2], 0sFr [2]
India 88 pk. [8], mohit.829 [7], prathyu [6], codefor6768 [6], n1tz53 [5], yellow1 [4], shivatejesh [4], sanjeev1779 [4], Revs [4], win_ay39 [3], shubh_jain [3], pranet [3], boygenius [3], SameerGulati [3], osank [2], mmaks [2], meintoo [2], m17 [2], davinci648 [2]
Russia 66 linjek [10], SC_pRo_ION [6], Guliash [6], rureggaeton [5], Sehnsucht [5], qwerty787788 [4], Artem_kh [4], holycow [3], Slyusar [3], Kvark161 [3], worse [2], stalker506 [2], ItsLastDay [2], Androik [2], ABalobanov [2]
Ukraine 44 Programist [7], Dudka [7], chakred_namor [6], Antoniuk [5], Rebryk [3], Omelianenko [3], BigBag [3], mathhislife [2], konstantin.lex [2], fiter [2], aangairbender [2], T0RRES [2]
Bangladesh 40 Honour_00 [10], the_redback [8], Baridcse [5], ndatta [4], raihatneloy [3], FlaminRage [3], MKGAURAB [2], Binary_ToothLess [2]
Turkiye 36 yEmre [8], muratt [7], kalimm [7], ikbal [6], kursatbakis0 [3], ykaya [2], KayacanV [2]

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!

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

Comments Comments (24)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Idea! I think it would be very nice to see what type of hacks there were during the contest!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

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)

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    iframe is not working (at least for me), but still thanks. I thought about it, but I was quite lazy :)

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

      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?

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

        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.

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

        soon Any update with your wrapper library? I'm really excited about that ^_^ Could you share it with us, that would be very helpful :)

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

          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.

          → Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Keep this work! The more statistics we have — the funnier it will be to solve solutions!

→ Reply
»
10 years ago, # |
  Vote: I like it +40 Vote: I do not like it

DmitriyH style

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, problem B the best this year for hackers!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wtf?

Country #hacks / #hackers Hackers Serbia 4.00 VladaMG98 (11), allllekssssa (1)

Hacks is 12, but hackers is 2, 12/2 == 4???

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    There was one guy who had hack attempt, but it was unsuccessful. I didn't want to add some_handle (0).

    → Reply
»
10 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Good idea! We should list the common mistakes for every future round.

→ Reply
»
10 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Very nice post. It can also come in useful for people (especially novices) trying to debug their WAs.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

very nice stats! i see u are DmitriyH v2.0! :)

a couple of suggestions, if i may:

  • can u tag users with their colored handles instead of using links to their profiles (like kostka and JuanMata instead of illi and JuanMata)? (if u don't know how to do this within a table, accidentallygivenfuck maybe able to help as he has used such table in one of his posts)
  • in Fastest Hackers section, can u also add handle of the defendant (participant whose solution was Hacked)?
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

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

      Now first also done :)

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

        great work! hope you can continue making these stats for every round! :)

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Have you written some software which generated those tables for you (->impressive), or have you really typed all that (-> "impressive") :P?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 5   Vote: I like it +3 Vote: I do not like it

    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 :)).

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You will do statistics for Round #263?

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

    Sure, I need to wait for hacks to appear. :)

    → Reply