Chmel_Tolstiy's blog

By Chmel_Tolstiy, 9 years ago, translation, In English

Flex your programming muscles in Yandex.Algorithm, an annual international programming championship organised by Yandex, one of the largest internet companies in Europe and Russia's leading search provider.

Anyone over 18 – regardless of education, profession or programming style – has a chance of reaching the finals and winning up to the equivalent of $4,500, while participation in the preliminary rounds is also open to younger competitors from age 6. The top 512 participants according to the cumulative result of all three elimination stage rounds will receive a contest T-shirt.

The warm-up round takes place online on May 10, starting at 21:00 Moscow time (UTC+3). It is followed by the qualification round, which takes place online on May 21 starting at 00:00 Moscow time (UTC+3), and running for 48 hours. To qualify for the elimination stage rounds you need to solve at least one problem in the warm-up or qualification rounds. The top 25 competitors after the elimination rounds advance to the finals in Minsk, Belarus.

See the schedule of all rounds here. Read more about Yandex.Algorithm and register for participation no later than May 22.

Take a look at 2015 problems and results here.

Good luck!

UPDATE 01. The warm-up round takes place tonight at 21:00 (UTC+3). You can qualify for the elimination in this round.

UPDATE 02. Analysis of the warm-up round.

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

»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Sir, could you show us the t-shirts ?!

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

Strange, I could not get past the registration page. It always shows "To view this page you have to authorize.", even though I have already been logged in to the site. Nothing happens when I clicked on the "authorize" after I logged in...

Anyone having the same problem? :(

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

    Yes, same thing happened to me.

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

      Fixed that, can you double check?

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

        I had the same issue before but I was able to register just a while ago.

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

        Sorry, I couldnt register. Not authorised.

        Edit : Logging out and logging back in helped!

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

        I still can't register. Clicking the link won't change anything. I've tried to log out and log back in but it doesn't help.

        Link to screenshot

»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

There is no option for English alphabet captcha in account recovery :(

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

I tried to register, but it always shows "To view this page you have to authorize". I'm already buggily logged in with Facebook (it keeps logging out whenever it feels like), but I can't seem to register. How do I know if I'm already registered or not?

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

    I had the same problem. Then I tried replacing the option lang=en to lang=ru in the URL, and registration page appeared.

    Since I don't understand Russian, I switched back to English and it was still working.

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

      Thank you.

      I registered using the Russian version and a translator xD. Now once registered the English version shows up as well.

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

GG registration page is filtered :( (benefits of living in iran)

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it +14 Vote: I do not like it

    Sorry about that. (Ads) You can always use Yandex.Browser with turbo mode! (/ads)

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

      Thanks, but to have yandex browser you have to download it, and guess what? filters... filters everywhere... lol! still, gl to all participants!

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

      unless access to turbo servers is closed too

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

Is filling in the obligatory fields (those with red '*'s) enough? I think I should at least provide an address for the T-shirts, if I somehow managed to win one.. But I couldn't find any fields about it.

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

    We'll supply you with additional form with shipping information, when you will score within top 512 of elimination stage — make sure to fill in correct email address though.

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

I'm obligated to select an Eastern Europe city in order to register (even not being there), can I change my city after the registration ?

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

    sure! Elaborate on that issue in feedback page of the service (lower left corner), after the contest

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

what is the difference between an open and a blind submission?

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

    Blind submissions are tested only on samples, but you get negative penalty time if it's Accepted on the full testset

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

    see rules. In short — open submissions work like regular ACM submissions — you get penalty for time and wrong attempts and full feedback on testing. With blind submission you only have one (1) attempt to send submission that will pass sample tests and can't resubmit — if that submission is correct you get negative penalty time

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

      OK thanks. Wish I asked sooner :(

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

How to solve problem F (Future Playlist)?

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

    One possible approach was to use matrix exponentiation and speed up multiplications using strassen's method. Eventually for large m the answer would approach a constant value and thus we don't even have to exponentiate to 10^(2016), much lesser will suffice. This could have passed the time limit (barely) but there must be a better solution.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      Eventually for large m the answer would approach a constant value

      Orly? I don't think so:

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

    It is actually a problem of finding a limit distribution of the Markov chain. It is guaranteed that 1 is an essential state, so at first step we should remove all inessential states (those are the states that cannot be reached from any other state with non-zero probability). After that all remaining states (in particular, 1) form an irreducible Markov chain where all states are positive recurrent (meaning that there is non-zero probability to return from each state to itself). For such Markov chain it can be proven that the limit distribution is exactly the stationary distribution (i.e. the distribution that transforms to itself after one step of a Markov chain), so we can find it as a left eigenvector of matrix B of that chain using Gauss elimination.

    UPD: Looks like we don't even need to leave only essential states, it works even without it. All components of stationary distribution corresponding to the inessential states will be simply equal to zero that perfectly makes sense.

    I didn't implement this, but I believe it works. Also I've seen author's solution, it also has a Gauss elimination :)

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

      Would the power method work here instead of Gauss elimination?

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

        I'm not sure because the speed of the convergence is exponential, though the base of the exponent depend on the eigenvalues of the matrix that may be pretty close to 1. Each matrix multiplication is O(n3), you simply won't be able to perform many of them.

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

          The matrix multiplications should be only O(n2) right? We only need matrix-vector multiplications.

          Nevertheless, I just implemented it and it didn't pass :(. I'll have to see the test data before figuring out what's wrong.

          Code: http://pastebin.com/n0tGWTg7

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

            Oh, I thought you are talking about fast matrix exponentiation first, and then multiplying the result by the distribution vector.

            Still, my claim holds that you make too small number of multiplications. Think of the following test:


            2 1 0 eps 1 - eps eps = 1e-6

            In order to move the most part of the distribution from the second state to the first you need about ~ 1 / eps steps that is too much. The answer here is 1 (the limit distribution is a vector (1, 0)).

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

              Ah, I see. I eventually got this hacky solution to pass, by exponentiating the matrix just enough to be under the TL, and then finishing off with the power method to reach the necessary precision.

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

                Acutally, there's no need to exponentiate the matrix. As Zlobober mentioned, after removing all inessential states, you will get a new transitive matrix M with dimension n′ × n. Just solve the equations MX = 0 with an extra equation . You will get the final solution.

                Here's my accepted code.

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

Will there be an editorial posted somewhere at some point?

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

Is it possible to solve C using dynamic programming approach?

int winner[8][8][8][8][2];

int main()
{
    // Some clever method using dynamic programming.
    FillWinnersTable();

    if (winner[whitePosY][whitePosX][blackPosY][blackPosX][firstMovesWhite] == 1)
        cout << "White";
    else
        cout << "Black";
}
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Isn't it memoization?

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

        Isn't it the same thing?

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

          Probably, I am wrong, but I always thought that dynamic programming is when you build up the solution bottom-up (without recursion).

          In the book "Algorithms" written by Dasgupta, Papadimitriou, and Vazirani, they make a clear distinction between memoizing technique and the dynamic programming.

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

            I think, that these two techniques do exactly the same thing (reduce some big peoblem to a set of smaller problems) but in slightly different ways. And I can't think of a problem, that can be solved with memoization, but can't be solved with non-recursive dynamic programming, and vice versa.

            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
              Rev. 4   Vote: I like it +3 Vote: I do not like it

              It's good for us to argue about this, so we can brush up our theoretical knowledge :)

              Here are my arguments:
              1. There was no purpose in inventing the second name for dynamic programming. That is why memoization and dp have to stand for different concepts behind them. I don't believe they are synonyms.
              2. It is trivial to estimate the complexity of dp solution. That is not the case for memoization. It is not at all obvious that the solution will not TL or overflow the stack.
              3. Most importantly, dp solution and memoization solution will perform absolutely different set of operations. That is, in some cases memoization may explore only some part of solution space, whereas the dynamic programming solution will always explore all possibilities.

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

What to do with E? I was doing random shit and managed to pass 14 tests...

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

What does "cumulative result" in T-shirt section mean? Is it calculated by overall accepted problems and penalties on every elimination rounds? If so, don't we have to take part in every round to get a T-shirt?

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +14 Vote: I do not like it

    From my experience from last year,

    First they sum the number of points you get, who has more stays in front (using that grand prix formula for giving points, sum all points you get during the 3 elimination rounds).

    Tie-breaks are made by number of problems solved (sum of number of problems during the 3 rounds).

    I am not sure about the last one, but I guess if you are tied in points and number of problems the tie-break is the sum of your penalty during the 3 elimination rounds.

    Edit: If you get a point in a round you are guaranteed a t-shirt as only 30 people get points in a round. Last year Petr got first place in the first round, he didn't participate in any other elimination rounds (if I remember correctly) and got a spot in the onsite finals (because he had a lot of points). Participating in more rounds gives more chances to get points and solve more problems (which is the first tie-break criterion), but it is possible to only participate in one round and get a t-shirt (though not advisable if you want the t-shirt and got no points for the round).

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

Does the problem D (cold countries) of on-line round 1 has any solutions like this?

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

    Don't know what did you mean exactly. But the solution for this problem is also a formula ;). I computed it in O(p) and didn't try to reduce the complexity and simplify:

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

      I had tried to submit your code (and many other) but always getting WA6. What it could be?

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

        Dunno. Overflow maybe? Btw, I have #define int int64_t in my code ))

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

          Really, I've finally found it :) But your code have one too:

          return f[m] * f[w];
          

          can't be OK (100 0 0), but tests are weak.

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

            Hm. I think that everything is fine here. This line returns m!w! And we know for sure that either m = 0 or w = 0.

            Maybe I'm missing something ?

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

              Yes, 0! * 100! > M

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

              Oh no, it's cursed task, I should guess after 15 submits! You're right, that was bug in my precalc :)