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

Автор rng_58, история, 9 лет назад, По-английски

GCJ will start in less than 24 hours.

Live Stream: https://www.youtube.com/watch?v=rh_EYIu7Ztc

Unfortunately I don't have time to edit this table, but rowdark will participate, and JoeyWheeler won't.

Participants:

GCJ Handle Country CF Handle CF Rating TC Handle TC Rating R2 Rank R3 Rank Previous Finals
Gennady.KorotkevichBelarustourist3503tourist3766132014 (1st)
vepifanovRussiavepifanov2963Kankuro323233102011 (8th),
2012 (4th),
2013 (17th),
2014 (8th)
qwerty787788Russiaqwerty7877882947qwerty78778828992420
rng..58Japanrng_582941rng_583468312010 (7th),
2011 (1st),
2012 (19th)
yeputonsRussiayeputons2783yeputons309210319
MerkurevRussiaMerkurev2758Merkurev25463921
bmerrySouth Africabmerry2722bmerry329560112008 (3rd),
2009 (10th),
2010 (21st),
2012 (6th)
peter50216Taiwanpeter502162637peter502162974224
TankEngineerChinaTankEngineer2634OierRobbin26362326
AngryBaconChinaBaconLi2619AngryBacon6216
tkociumakaPolandtomasz.kociumaka2613tom612pl271782
dzhulgakovUkrainedzhulgakov2607dzhulgakov3168142142008 (44th),
2009 (5th) 2012 (9th),
2013 (13th),
2014 (9th)
simonlindholmSwedensimonlindholm2570208
semiexp.Japansemiexp2507semiexp3005627
pashkaRussiapashka2488pashka286211152008 (84th),
2009 (17th),
2010 (8th),
2011 (7th)
ishraqAustraliaJoeyWheeler2482izrak20868518
betaverosTaiwanbetaveros2463betaveros218138417
RomkaBelarusRomka2452_Romka_2474446282014 (10th)
iwiJapaniwiwi2427iwiwi3100762008 (59th),
2010 (9th),
2014 (15th)
tczajkaPolandtomek2393tomek32041872003 (4th),
2004 (4th),
2006 (6th)
JAPLJJapanwrong2367wrong246567222013 (23rd)
wuzhengkaiChinawuzhengkai2343wuzhengkai2575135232014 (23rd)
faguGermanyfagu2306fagu225912612
kevinsogoPhilippineskevinsogo2236kevinsogo1369
XharkSouth KoreaXhark2132Xhark1677354
linguoUKlinguo3652008 (74th),
2010 (22nd),
2011 (22nd)
  • Проголосовать: нравится
  • +297
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

If you want you can add this into tomek previous finals- 2003(4th), 2004(4th), 2006(6th)

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

The size of your graphic list is disturbing the page Please fix it.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope you guys the best of luck :D

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).

»
9 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Let us see how many different languages linguo uses today.

In Code Jam 2009, he used a total of 14 different languages, uptil Round 2.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think iwiwi's TC handle should be [[iwi]].

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In this context, the optimal strategy for tourist to make headlines could be to tie his right hand behind his back, and then still come 5th or thereabouts.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +112 Проголосовать: не нравится

It's interesting to recall Dota 2 (computer game) International finals, which I observed in the same Seattle city just a week ago. The prize pool was $18 mln, and the the members of the winning team got about $1.2 mln each.

And now compare it to $15 thousands for the winner of Google Code Jam.

I make no judgements or comments here. Merely giving the info.

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

    So where did the prize pool come from?

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

      Mostly — players. They were buying a special virtual book, and Valve donated 25% of the proceeds to the pool.

      The book is not required to play Dota, it gives some virtual things like hats or costumes, tickets to watch the tournament games online and a number of games in the game.

      The audience of the game is tens of millions. There are ~600,000 playing at any single moment of time concurrently.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck everybody :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Who is apiad and why he's not mentioned in the list? He ranked 13th in round 3

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think tourist will win.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Why would you make such a hasty conclusion?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +33 Проголосовать: не нравится

    It is not easy to win finals, you need bit of luck. Last year as far as I know petr mentioned that eatmore was close for large data set in problem F and problem E large set has been expired for him. From last couple of years Petr failed in problem C in Yandex, Facebook hacker cup 2014 result was close too, as tomek is not involved in competitive programming regularly and he still do well that's quite awesome. In round 3, rng_58 won, he has won the competition previously too. Yes tourist has been in great level now but about finals you can't say. He is good but still with little bit of bad luck he can fail or somebody other can outperform him. If you see the list there are many onsite champions and ICPC champions are there. And some are new but has good progress in recent years. So you never know who will win. Its about the competition hours.

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

It would be really cool if linguo wins.

»
9 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

You may miss rowdark.

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится -11 Проголосовать: не нравится

~

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

Is there a scoreboard link that shows current results other than youtube link ?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please everyone that will compete today, if you have the option for screencast, do this! It's a great orportunity for "us"(coders) to see how the bests programs.

»
9 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

All the best rng_58 :)

»
9 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Anyone willing to bet on rng_58 to win the Finals ? :D

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I would like to see yeputons win this year :p Good Luck to him

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

rowdark also made it to finals. And my TC handle is cvcvb_lyp. :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Very red page :]

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

may I ask if the large constraint for B is N<=10^6 or N<=106? it just looks similiar

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Angry bacons keyboard is soo noisy

»
9 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Seems Something is going wrong with tourist!!!!

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +24 Проголосовать: не нравится

    Not sure about that , because Penalty equal to the time of the last submission and not the sum of submissions like in ICPC so i think he is keeping large input to check later .

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

      Just watched him leaving his chair and walking around. Besides noticed him reading the question for quite a while!!

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится

      Precisely. There is very little value in submitting your solutions to large subproblems early. In the finals a very valid strategy is to solve the small subproblem separately, then to solve the large one using an efficient algorithm, and then to run both implementations on many random inputs to make it more likely that your solution of the large subproblem is correct. You only download and submit the large subproblems after what you expect to be your last solved small subproblem. One extra benefit: your opponents receive less information.

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

        And it's probably worth mentioning that this strategy is pretty much only viable for tourist.

        Unless you're a big favorite, minimizing the variance is not the way to go. You're losing your time in the hope of increasing the accuracy. Also, there's a huge psychological benefit of being done with the problem. If you have three problems that you're unsure of, then it will be harder for you to focus on the new one.

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          Rev. 5   Проголосовать: нравится +17 Проголосовать: не нравится

          Sure, the strategy does require some balls :) but many of the contestants there should be able to pull it off.

          I would certainly go for a separate solution for the easy anyway, at least in problems where it's easy and fast to write it (which is the case for most problems this year). My experience with CodeJam finals is that consistency is what matters the most.

          Once you implement a solution for the hard subproblem, running the random tests is often only a 1-minute overhead: 30 seconds to write a simple generator and 30 seconds to do some bash magic. IMHO it's a pretty small cost to pay.

          (If I wasn't clear enough before, note that the overhead in writing the generator and running the tests is the only extra cost I would be paying. Instead of, for example, solving and submitting in the order A1 A2 B1 B2 C1, I would solve in the same order but submit in the order A1 B1 C1 A2 B2, or possibly A1 B1 A2 C1 B2, if everything goes well. If we ignore the overhead from running the tests, the time of the last submission is the same in both cases.)

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится +36 Проголосовать: не нравится

            I'm still saying that's a very bad strategy for almost everyone there. It may sound good on paper, but it's horrible in practice.

            • In most cases, the information on the leaderboard you provide is worthless unless you're in the lead, or you've solved a hard problem.

            • You have to write a separate solution to easy. It may take only 3-5 minutes sometimes, but it's still a significant cost. I agree that sometimes it may be a good idea even if you're behind. But it's definitely very far from being a golden rule.

            • 30 seconds for generating test cases? Um, maybe in some trivial cases. The cost of switching your mindset, the potential cost of doing a bug in test generator. These things add up.

            • And again, most people have to click that "submit" button in order to get their mind fresh again. Sure, that's something that could be worked on.

            I'll also add "If I wasn't clear enough before" clause: I'm not saying that doing that for any problem is a bad idea. I'm just against advocating it as an near-optimal strategy for every GCJ onsite participant.

            • »
              »
              »
              »
              »
              »
              »
              9 лет назад, # ^ |
                Проголосовать: нравится +11 Проголосовать: не нравится

              Yeah, I agree with all you are saying. I also never claimed that this is a near-optimal strategy for everyone, I just said that it is a valid strategy worth considering, and it is certainly something I would strongly consider.

              It is still worth to consider each problem separately. Sometimes, it is obvious that if a program solves the easy input, it's correct. In such cases, why bother testing :) but in many problems the hard can be tricky and failing it because of some dumb bug is very costly.

              • »
                »
                »
                »
                »
                »
                »
                »
                9 лет назад, # ^ |
                  Проголосовать: нравится +17 Проголосовать: не нравится

                Yeah, I guess we both agree on everything.

                It's the usual problem of trying to express in a short and precise way. Which makes everything sound much less subtle than it really is. Ahh, teh internetz :)

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What means "Time expired"?

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

    It means that the contestant downloaded the large input but failed to submit the correct output within the allowed 8 minutes. If you see "Time expired" in the scoreboard, it means that the contestant cannot solve that subproblem any more.

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

    He downloaded a large input, but did not send a output in time.

»
9 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Why they block chat on stream? =( On the ACM ICPC finals live stream chat was blocked too.

But why? I really miss it =)

»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

What a technique of tourist ! First he is solving the small input problems and make him sure that if it is correct or not? I think he will submit all the large input problems after solving all the problems at a time.

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Last year the stream was really better! This year the camera is always in the same place!

I think it was better showing each contestant and computers.

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Is he or she? xD

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

OVER, bmerry First Place!! CRAZY CONTEST

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

What happened to tourist's penalty?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    He resubmitted D-large, apparently.

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

    Resubmitted D-large.

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

    You can resubmit as many times as you like during 8 minute window, but the time of the last submit will count.

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

      no extra penalty 20 minutes?

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится
        • This is not ICPC, so instead of 20 minute penalties Code Jam has 4.
        • 4 minute penalty is only applicable for submissions judged incorrect. No judgement is happening on large test cases, so no penalties are possible on large test cases.
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What do you think,are there gonna be any upsets/surprises in the final results this year ?

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

tomek is the beast.

»
9 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

GG gennady why did I ever doubt you?

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

Yet again, tourist is the Google Code Jam Champion! :D

»
9 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Congratulations to tourist for back to back titles :)

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

That resubmission on D saved tourist. Well done bmerry and rng_58.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    I think tomek also did really well. He does compete only in few major competition. And according to his submission time it looks like he took more time in B which may result in applying optimization algorithm in D and E. May be rustiness cost him :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    im wondering how did he realize his submission was wrong so that he did a resubmit?

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +43 Проголосовать: не нравится

      They have showed a part of the process on the stream. This may not be entirely accurate, but from what I have seen it looked as follows:

      It did not seem to be the case that he ran his solution, then found and fixed a bug in his code, and then resubmitted. It seemed that he had two versions of his solution. As soon as the first one produced some output, he submitted it. The second one (presumably one that was slower but tried more possibilities? maybe one for which he wasn't sure whether it will be fast enough?) ran longer but also finished in time. When he compared the outputs he saw that some of the outputs the slower solution produced were slightly better. This was still within the 8 minutes, so he could resubmit the new output.

»
9 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

Interesting, tomek submission of D large, Simulated Annealing, 99/100 test cases pass, last one added yesterday.Really!

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Awesome tourist Comeback !

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Does anyone know the practice round problem from this years code jam? Apparently it was a finals problem they found out was similar to a recent problem and had to remove it from the set. (According to the broadcast)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I really like one thing from tourist and learned from it that sticking to problem you think you can solve instead of reading different problems and try them. Last year he sticks to problem E not moving for F small and this year he stick to problem D not moving for F small. Yes you need a bit of luck but this is the great things to learn.

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

    This strategy works if you are, not saying tourist,but at least an IGM.

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

      Of course it is not for me for a time now but it is good point to note for the future.

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

tourist is becoming Messi of CP, winning every major individual trophy possible and multiple times :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    And probably, ITMO university is Barcelona :D

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +36 Проголосовать: не нравится

    I would find this analogue accurate if tourist had never won [ICPC] World Finals, like Messi. :)

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

      True in National Level:)

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +44 Проголосовать: не нравится

      tourist has never won any cup as Belarus national team :D

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

        In the world of competitive programming, nation is more like an university. I would love to have some national team programming competition though. Something along the lines of "Battle of Giants", but on a much larger scale and with a single team per nation.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    He is better. He's no real opponents like Critsiano Ronaldo for Messi. Also he's won World Cup for two times, but Messi hasn't.

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

tourist == mangus carlsen

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    tourist == magnus* carlsen

    If he was a bit more dominating then he could have been compared with Ronda Rousey of UFC.

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Where is wuzhengkai? Did he participate?

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

Current TC handle of Xhark is RRx.

»
9 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится
»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

This is the second year he's won and it has felt like such a close call. What extra skill did he posses to be able to outperform a 3 time IMO Gold winner? I thought being very good in discrete maths and being able to prove your programs with heavy use of induction and many other techniques were the key.

At any rate, congrats to tourist. It was a phenomenal match, and such a close one. Tomek was in awesome form to not have competed much recently, also. I guess it is a bit like riding a bike?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tourist is like CR7 :D Best in the world. Congrats Gennady

»
9 лет назад, # |
Rev. 5   Проголосовать: нравится +29 Проголосовать: не нравится

Scoreboard has been updated (also with solutions!)

It looks like tourist used the strategy everyone speculated for A, B and E (His solutions for small and large are identical).
tomek's Simulated Annealing solutions to D and E are really interesting too.

-

Oh and for a good laugh, look at the filename for tourist's solution to C-small.

»
9 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Where is my cookie for predicting everything exactly as it was?

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

STEP5 is another participant, that is missed in the table.

»
9 лет назад, # |
  Проголосовать: нравится +68 Проголосовать: не нравится

Pretty disappointed that up until now there are exactly 0 comments/blog entries regarding to Distributed Code Jam.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

    My main feeling about distributed code jam: the problems were too hard. Anyone who solved D or E would have gotten first place, and no one did. I did my best on E, but didn't manage even after trying for 3 hours, ending up with >300 lines of code and an awful amount of special cases... Even B was only solved fully by two people. (To be fair, perhaps just no-one looked at D. I don't know how hard that one was.)

    Hopefully next year, when people are more used to the format, and if the problems get less heavy on implementation, things will be more interesting. I also hear they are planning to run the solutions on more machines then. :-)

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

linguo — was the only person to use the programming language Brainfuck in order to complete a set. :O source

»
9 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

who won?