Yandex.Algorithm 2011 - Round 2
By yaro, 14 years ago, translation, In English

Hello, dear participants and spectators!

Let me remind you that the elimination phase of the open programming competition "Yandex.Algorithm" comes to an end. With it this means that the time for the most important event of the phase has come: the elimination round for the finals (finals will be held at the Yandex Summer School)! This means that today two hundred best participants of the tournament (based on the results of the previous qualification rounds) will compete to get into the top-15 of the world olympiad programming community.

We hope that the round will be appreciated not only by the participants but also by the spectators, who will have the opportinity to watch the events developing for at least two hours.

Please, pay attention to the problems' costs: 500, 1000, 2000, 2500, 2500. I also advise you to read all the statements, as the choice of the costs and the order is certainly subjective.

Round will be rated for all the participants (including those competing hors concours).
Good luck to the participants. The problems are going to be rather hard, so you'll have to do your best!

I also wish a spectacular round to the rest!

Round is over. According to the results, 20 participants solved at least three problems, and just one (the winner) was able to solve the fourth. The first three places were taken by Petr Mitrichev, Gennady Korotkevich and Sergey Kopeliovich. Congratulations!

In addition to this, 15 leaders advanced to the finals: Petr, tourist, Burunduk1, ivan.metelsky, dzhulgakov, e-maxx, LayCurse, rng_58, pieguy, zeliboba, ktuan, levlam, wata, dolphinigle, Progger .

Problems proved to be rather tough. Here's the full analysis.

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

14 years ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

EDIT: Everything seems fine now :),,,


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

    I recognized Яндекс :P

    edit: Ah, a translation has been added. Much better!
    → Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Good luck & Have fun!!
→ Reply
14 years ago, # |
  Vote: I like it +39 Vote: I do not like it
I missed registration but qualified from Round 1. Anyway I can get in?
→ Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
"Good afternoon, participants and spectators!"
It's mid-night there.

Good luck every one!
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Anyone can tell me where to see status of past submissions? I can see only one page of the newest ones.
During the contest I tried to hack one person printing with %lld but somehow this code passed my test. So I wonder if there is any way to see what compiler did he use and failed on finding this.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it
    Hover your mouse over his submission (486 00:07), you will see MS C++. Printing with %lld works there.
    → Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Due to my internet connection problem, I have had submitted the code for problem C by email before the end of the game. Is it available? And the manager please take an attention. Thanks.
→ Reply
14 years ago, # |
  Vote: I like it +23 Vote: I do not like it
:'(  What a pity, rank 71. One more T-shirt, please?
→ Reply
14 years ago, # |
  Vote: I like it +18 Vote: I do not like it
:( just change one constant to get D accepted
in GCJ 1A, add one more if to win
Poor me
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What a pity! 
If I had one more minute ... I can solve problem B ...
I was so sad when I submited problem B and got accepted right after the contest ...
→ Reply
14 years ago, # |
  Vote: I like it +10 Vote: I do not like it
The problems is pretty good!

I remember a problem that is similar to D.(The author is Myth5)
(There is only Chinese version statement, I couldn't find a English one.)
It asked Ks * Ks instead of Ks * Ks * s.
But the data is about N = 50000, which is smaller than this one.

So I want to know if there is a solution for these problems?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    There is an editorial for D published (russian only at this point). It follows from it that the intended approach is able to solve such problem for any function (Ks, s) (of course given that it can be calculated quickly).

    Something that I didn't like about this problemset is E being quite easily googlable. Other problems were pretty good though.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      We apologize for such a defect. The fact was proved by my co-author (by mathematical means) and we didn't actually thought of the problem to be googlable. Moreover, we supposed the simple quantitative approach to be very popular and polynomial approach to be unlikely.
      P. S. Could you, please, provide a link to the source of dishonesty? :)
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Here is an example: http://www.ncd.matf.bg.ac.rs/~ezivkovm/publications/primpol1.pdf. I believe there are others as well, since the topic of "primitive polynomials" seems to be well-studied.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Oh, yeah, that's nice, but how did you come to the idea of irreducible polynomials over GF(2) ?
          We thought this was the main part of the problem, not the process of constructing such a polynomial.
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it +16 Vote: I do not like it
            I implemented brute force and hoped to find some regularity in answers (it failed). Then I used brute force to count the number of valid answers for different values of k. Finally, I used OEIS to find that it corresponds to the number of primitive polynomials over GF(2).
            → Reply
            • 14 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              Aah, okay, thanks. That's the standard programming idea I always forget about!
              → Reply
      • 14 years ago, # ^ |
        ← Rev. 6   Vote: I like it 0 Vote: I do not like it

        As I remember this problem is in study program in MIPT radio labs. (It was two years ago so maybe I'm wrong, but as I remember this device is named De BruijnLFSR generator)
        UPD. prooflink: http://en.wikipedia.org/wiki/Linear_feedback_shift_register
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          De Brujin sequence is somewhat similarly defined, but in fact is absolutely different topic.
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Linear feedback shift register (you can look in wikipedia) is what I am speaking about.
            → Reply
            • 14 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              This time it seems to be exactly this problem. The Wikipedia article even contains a link to all necessary answers (for n <= 128).
              → Reply
              • 14 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                I was a bit unhappy when I remembered this 5 minutes after contest was over =(
                → Reply
14 years ago, # |
  Vote: I like it +10 Vote: I do not like it
Could you publish the date of the Finals?

I can't participate in all summer school (July 12-18), so I want to know the exact date of the Finals.

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

    By the way, have you ever been in Russia before?
    I asked that because in that post you said you were studying Russian.
    Are you ready to challenge your knowledge? ^__^
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      No, I've never been to Russia. I'm studying Russian as second foreign language.
      → Reply
14 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

Whit change only one character of my solution for B from 'i' to 'k' the result changed from "RTE Test 8" to "AC", and rank from 85 to 61. (Between contestant that qualified from round1. And from 117 to 69 in all) :(
→ Reply
14 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Oops.. I noticed a sad thing.

In this match , I got the 101th place and my rating changed 1787 -> 1875 (+88).

And RodionGork got the 80th place , but his rating changed 1443 -> 1528 (only +85!)
hmm... Why his rating got little changing ?

In my opinion, his rating should rise more.
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    As I understand, now codeforces uses a formula like one at topcoder. So your score increment is affected by your reliability, i.e. how stable your rating was during previous contests.
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      I have just understood it. thanks!

      But I think that, his changing is still little when consider his former rating ..
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      Stupid formula. It's evident that paricipant with lower rating who got higher place should get more rating points than that with lower score in the match.
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      If it had worked like TopCoder's one, his rating would have been incredibly changed since he did only one match before. Were the ratings calculated independently between Div1 and Div2? Many Div2 coders' rating change were the almost same as Div1 coders even if their results were close... In my case, I got 56th but my ratings were 1615→1735(+120)...
      → Reply
14 years ago, # |
  Vote: I like it +10 Vote: I do not like it
How can the top 70 guys get their T-shirts?
Where can we fill in our address like Google Code Jam?
→ Reply