Chmel_Tolstiy's blog

By Chmel_Tolstiy, 7 years ago, translation,

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.

• +149

 » 7 years ago, # |   -6 Sir, could you show us the t-shirts ?!
•  » » 7 years ago, # ^ |   +30 Are you interested in t-shirts of previous years?
•  » » » 7 years ago, # ^ |   0 It would be interesting to see any yandex T-shirt:)
•  » » » » 7 years ago, # ^ |   +31 2015 t-shirt
•  » » » » » 7 years ago, # ^ |   0 Oh, you are first :)
•  » » » » » » 7 years ago, # ^ |   0 I hope this year's one would be as cool as 2015 one :3
•  » » » » » » » 7 years ago, # ^ |   0 Yes it would be really nice if it is black i really like that color :D
•  » » » 7 years ago, # ^ |   0 When would the T-shirts be dispatched?
 » 7 years ago, # | ← Rev. 2 →   0 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? :(
•  » » 7 years ago, # ^ |   0 Yes, same thing happened to me.
•  » » » 7 years ago, # ^ |   +10 Fixed that, can you double check?
•  » » » » 7 years ago, # ^ |   0 I had the same issue before but I was able to register just a while ago.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Sorry, I couldnt register. Not authorised.Edit : Logging out and logging back in helped!
•  » » » » 7 years ago, # ^ |   0 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
 » 7 years ago, # |   +14 There is no option for English alphabet captcha in account recovery :(
•  » » 7 years ago, # ^ |   +10 hmmm, can you try https://passport.yandex.com for that?
 » 7 years ago, # | ← Rev. 3 →   +3 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?
•  » » 7 years ago, # ^ |   +5 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.
•  » » » 7 years ago, # ^ | ← Rev. 3 →   0 Thank you.I registered using the Russian version and a translator xD. Now once registered the English version shows up as well.
 » 7 years ago, # |   0 GG registration page is filtered :( (benefits of living in iran)
•  » » 7 years ago, # ^ | ← Rev. 3 →   +14 Sorry about that. (Ads) You can always use Yandex.Browser with turbo mode! (/ads)
•  » » » 7 years ago, # ^ |   +10 Thanks, but to have yandex browser you have to download it, and guess what? filters... filters everywhere... lol! still, gl to all participants!
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 unless access to turbo servers is closed too
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ |   +8 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.
•  » » » 7 years ago, # ^ |   0 Thanks for the quick reply!
 » 7 years ago, # |   0 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 ?
•  » » 7 years ago, # ^ |   0 sure! Elaborate on that issue in feedback page of the service (lower left corner), after the contest
 » 7 years ago, # |   0 what is the difference between an open and a blind submission?
•  » » 7 years ago, # ^ |   +5 Blind submissions are tested only on samples, but you get negative penalty time if it's Accepted on the full testset
•  » » 7 years ago, # ^ |   +5 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
•  » » » 7 years ago, # ^ |   0 OK thanks. Wish I asked sooner :(
 » 7 years ago, # | ← Rev. 2 →   0 How to solve problem F (Future Playlist)?
•  » » 7 years ago, # ^ |   0 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.
•  » » » 7 years ago, # ^ |   -7 Eventually for large m the answer would approach a constant value Orly? I don't think so:
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Ok my bad...full exponentiation upto 10^(2016) will surely time out. We can use this https://discuss.codechef.com/questions/49614/linear-recurrence-using-cayley-hamilton-theorem
•  » » » » 7 years ago, # ^ |   0 This is not a correct test. There should be non-zero elements on main diagonal and in the first column according to the statement.The state 1 of the Markov chain described in the statement is essential because it is accessible from all other states, so there should exist the limit value for (Av)1.
•  » » » » » 7 years ago, # ^ |   +10 OH HOW I LIKE TO NOT READ THE STATEMENT(however, writing the most useful part in the input description is never a good idea imho)
•  » » 7 years ago, # ^ | ← Rev. 4 →   0 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 :)
•  » » » 7 years ago, # ^ |   0 Would the power method work here instead of Gauss elimination?
•  » » » » 7 years ago, # ^ |   0 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.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 7 years ago, # ^ |   0 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)).
•  » » » » » » » 7 years ago, # ^ |   0 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.
•  » » » » » » » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   0 Will there be an editorial posted somewhere at some point?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +15 Yes, tomorrow we will post it here.Update. Posted.
 » 7 years ago, # | ← Rev. 2 →   0 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"; } 
•  » » 7 years ago, # ^ |   0
•  » » » 7 years ago, # ^ |   0 Isn't it memoization?
•  » » » » 7 years ago, # ^ |   +10 Isn't it the same thing?
•  » » » » » 7 years ago, # ^ |   0 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.
•  » » » » » » 7 years ago, # ^ |   0 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.
•  » » » » » » » 7 years ago, # ^ | ← Rev. 4 →   +3 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.
 » 7 years ago, # |   0 What to do with E? I was doing random shit and managed to pass 14 tests...
•  » » 7 years ago, # ^ |   +5
•  » » 7 years ago, # ^ |   +31 I just read the abstract of this paper.And m = 1 is a special case to be considered apart.
 » 7 years ago, # |   +19 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?
•  » » 7 years ago, # ^ | ← Rev. 3 →   +14 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).
 » 7 years ago, # | ← Rev. 2 →   0 Does the problem D (cold countries) of on-line round 1 has any solutions like this?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 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 codeinline int C(int n, int k) { return f[n] * fi[n - k] % MOD * fi[k] % MOD; } // number of ways to split n items to k groups inline int D(int n, int k) { if (k == 0) return n == 0 ? 1 : 0; return C(n + k - 1, k - 1); } int solve() { if (p == 0) { if (m && w) return 0; return f[m] * f[w]; } int res = 0; for (int i = 1; i <= p; ++i) { int x = i / 2 + 1, y = (i + 1) / 2; int g = w - i, b = m - i; int t = (D(g, x) * D(b, y) % MOD + D(g, y) * D(b, x) % MOD) % MOD; res += t * C(p, i) % MOD * f[i] % MOD * f[g] % MOD * f[b] % MOD; if (res >= MOD) res -= MOD; } return res; } 
•  » » » 7 years ago, # ^ |   0 I had tried to submit your code (and many other) but always getting WA6. What it could be?
•  » » » » 7 years ago, # ^ |   0 Dunno. Overflow maybe? Btw, I have #define int int64_t in my code ))
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 7 years ago, # ^ |   0 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 ?
•  » » » » » » » 7 years ago, # ^ |   0 Yes, 0! * 100! > M
•  » » » » » » » 7 years ago, # ^ |   0 Oh no, it's cursed task, I should guess after 15 submits! You're right, that was bug in my precalc :)