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.
Sir, could you show us the t-shirts ?!
Are you interested in t-shirts of previous years?
It would be interesting to see any yandex T-shirt:)
2015 t-shirt
Oh, you are first :)
2013 2014
I hope this year's one would be as cool as 2015 one :3
Yes it would be really nice if it is black i really like that color :D
When would the T-shirts be dispatched?
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? :(
Yes, same thing happened to me.
Fixed that, can you double check?
I had the same issue before but I was able to register just a while ago.
Sorry, I couldnt register. Not authorised.
Edit : Logging out and logging back in helped!
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
There is no option for English alphabet captcha in account recovery :(
hmmm, can you try https://passport.yandex.com for that?
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?
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.
Thank you.
I registered using the Russian version and a translator xD. Now once registered the English version shows up as well.
GG registration page is filtered :( (benefits of living in iran)
Sorry about that. (Ads) You can always use Yandex.Browser with turbo mode! (/ads)
Thanks, but to have yandex browser you have to download it, and guess what? filters... filters everywhere... lol! still, gl to all participants!
unless access to turbo servers is closed too
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.
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.
Thanks for the quick reply!
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 ?
sure! Elaborate on that issue in feedback page of the service (lower left corner), after the contest
what is the difference between an open and a blind submission?
Blind submissions are tested only on samples, but you get negative penalty time if it's Accepted on the full testset
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
OK thanks. Wish I asked sooner :(
How to solve problem F (Future Playlist)?
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.
Orly? I don't think so:
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
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.
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)
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 :)
Would the power method work here instead of Gauss elimination?
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.
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
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:
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)).
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.
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.
Will there be an editorial posted somewhere at some point?
Yes, tomorrow we will post it here.
Update. Posted.
Is it possible to solve C using dynamic programming approach?
Yep
Isn't it memoization?
Isn't it the same thing?
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.
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.
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.
What to do with E? I was doing random shit and managed to pass 14 tests...
Read Wikipedia.
I just read the abstract of this paper.
And m = 1 is a special case to be considered apart.
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?
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).
Does the problem D (cold countries) of on-line round 1 has any solutions like this?
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:
I had tried to submit your code (and many other) but always getting WA6. What it could be?
Dunno. Overflow maybe? Btw, I have
#define int int64_t
in my code ))Really, I've finally found it :) But your code have one too:
can't be OK (100 0 0), but tests are weak.
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 ?
Yes, 0! * 100! > M
Oh no, it's cursed task, I should guess after 15 submits! You're right, that was bug in my precalc :)