Join Yandex.Algorithm, an annual international programming championship organized by Russia’s leading search provider Yandex, to flex your programming muscle and win the equivalent of up to $5,500 of cash prize. The championship is open to anyone, regardless of their education, profession or programming style.
Qualification round starts on May 17 with warmup round on May 3. Read more about Yandex.Algorithm and register for participation before May 18.
UPD Qualification round is open until 0:00 May 18, start now on Yandex.Algorithm website.
UPD Do not miss first elimination round. That will start May 24, 2015 at 21:00 (UTC+3)
Sorry, form unavailable Need auth.
What's wrong?
You need to be logged into Yandex to register. Use social auth for easy registration
I think I have logged into Yandex. And the message above is what I got.
What social auth do I need?(I am confused about this). Thanks for helping me.
maybe you're logged into yandex.com and trying to access yandex.ru, or vice versa.
You can log in using your facebook, google or twitter accounts, check https://mail.yandex.com/
Fixed. Thanks anyway.
Will you send reminders before every round?
Where will be the final round take place?
Russian post version says that the championship will be fully online :(
Why am not I allowed to enter warmup round?
We will start the round at 22:10, thank you for your patience
I hope you guys are not managing the contest from the Yandex Moscow office at Sunday, 22:00 :)
It's still unavailable for me
The absence of the exact date seems now suspicious to me :(
Lie
My friend says he can see the problems but all I get is "The contest is over. Submissions are not allowed". Sounds quite unfair?
He's lying and shouldn't be your friend anymore.
Well he sent me a problem statement, so I guess he just created a problem for the lie! :D
Why would he lie to you wihout a preparation? Don't be naive. :)
Same here
The countdown timer is shown now.
Now it says the contest will start in 3 minutes, but my friend sent me a picture of the statement already... Gonna be a fair competition I see!
I saw problem A and started coding it but now it says the contest has not started yet. =.=
Hey, that's unfair! We need some men in black to fix that for ya.
Ваше решение отправить не удалось. UPD: У вас нет прав просматривать это соревнование.
Just when you thought it's all going well — "You are not allowed to view this contest".
I'm getting Bayan flashbacks here :\
Даже условие загрузить не успел :(
А я успел и решить, но отправить не успел(
What can I do sometimes ?!!!!!
Whenever I try to submit a solution, it tells me:
"Your solution was not submitted."
Help?
I can't submit my c++ solution for A. Any clue? :D
Problem B is identical to a problem from Canadian OI, with minor changes to the statement and identical input format/sample data:
http://wcipeg.com/problem/ccc03s2p3
I think all problems used for this round are not new. I don't see any troubles with giving old problems to the warm-up round.
In the rules it says
Official Rules
Problems in the warm-up (testing) rounds were used on different contests like OpenCup or local contests. Problem about cube was used on some ancient SnarkNews Series; but in there it was taken not from Canadian OI, but from some other source (dont remember precisely, which one though).
Original problems must be for all official rounds (Qualification, three Online rounds and Online Final). Testing round(s) use selections — main goal of it is to test if the system is working ok and to remind TCM/Time rules to players, and for this goal selection from different sources works okay.
I met problem with same idea several times in different old contests, so it was added as "classical problem"; i am surprised that number of players solving them is not that big.
May be, first time it appeared in Canadian OI (atleast format points at it). Btw, tests were changed abit to catch some special cases.
See also the following problems:
https://contest.yandex.ru/contest/424/problems/F/
http://wcipeg.com/problem/ccc13s2p6
What is the solution for this problem?
link
Huge thanks for everyone who stayed with us until the normal flow of the round. We'll make sure that Qualification round on May 17 will run smoothly.
Разбор будет?
How to solve C ?!
If points are on the different sides to axis x result is euclidean distance between them. Else change y of first point to -y.
It is stated, that both points are on the top side the river, so you don't have to check whether cities are on different sides of the river.
How to change the country flag that is shown to the right of my name in the standings?
I can't wait more for the editorial. Can anyone give the accepted code for problem A? Thanks.
You can use Havel–Hakimi algorithm to solve the problem.
Because there is at least one solution. You can first build a degree sequence with all degrees equal to k. The divide the rest degrees to each element of the degree sequence evenly.
My code for reference: http://paste.ubuntu.com/10994941
Is it possible to solve this problem ignoring K? I mean, create a sequence of edges based only on N, and then take the first M edges of it. (Yes, the sequence must ignore M too :)
For a challenge I have been trying to solve A this way, but failed. I still do not know the answer.
Well, I ignored K, but had not ignored M though
Sooo, who are the t-shirt winners ?!
I couldn't understand open/blind submission. What is difference ?! What are advantages of open/blind. Does blind mean : "I don't need feedback" or sth else ?!
When you use blind way, you dont have feedback but you have additional bonus instead of penalty time. I.e. you choose harder way and are awarded for it with the decreasing of total penalty.
hmm got it... So if my solution gets OK in open submission does it mean I have solved that problem I mean it checks all tests ?!
Yes.. It means ur solution passed all the test-cases
To be precise, it's not instead of a penalty, it's in addition to penalty (so you have both penalty and bonus)
Where can I solve previous Yandex contests?
(of last year and last to last year)
EDIT-1 : Found 2014 in GYM
Here: https://contest.yandex.ru/algorithm2014/schedule/
And here: https://contest.yandex.ru/algorithm2013/schedule/
Thanks
Is there public standings page?
Not until the end of the contest. It will be unfair if contestants who haven't started yet could see someone's final results.
It still would be cool to see the standings for those who are not registered.
Huh, memory limit is 64Mb ; o? Kinda completely missed that, I haven't seen such small memory limit as a standard limit for some time and it costed me one problem ; d.
Same for me.
I'll read statements more carefully. I'll read statements more carefully. I'll read statements more carefully...
Like this ?!
UPD I understood why minus. I think you you thought it doesn't calculate if your memory exceeds 64MB, but before this submission memory was around 135MB.
My first submission stayed with the "waiting" status for about half an hour and I had a stupid bug that I had to wait half an hour to correct. I hope this doesn't happen in the Elimination rounds.
Top 512 participants according to the cumulative result of all three elimination stage rounds will receive a contest T-shirt. what does it mean "cumulative result",there is 3 round,and in each only top 30 user can earn points,3*30=90 and how 512? pls some1 explain me
What is the solution for Problem B — Optimal Playlist ?
Binary search, then condense strongly connected components and topologically sort them. Components will form a chain iff the required path exists.
What about finding Minimum Cost Spanning Tree in DAG? Would this approach work?
No: for example, in graph (1->2,1->3) there is an oriented tree, but no path visits all nodes.
Ah, missed qualification again.
Can someone give some hints for problem C? Thanks.
My approach was following. Let's store in f[d][j] j-th parameter of d-th document, in s[d] relevance for d-th document and in some structure r — sorted relevances with numbers of corresponding documents (it was set<pair<long long, int> > in my code). Then for each query it's easy to update. For 2 K it was just top K elements of set. For 1 d j v:
I used order statistics tree. I guess using STL set container would have sufficed too.
How to solve E problem ?!
We need to find the number of pairs (A, B) such that A divides N, B divides M and L <= AB <= R. First generate all divisors of N and M. Then iterate over A (divisor of N). Corresponding B must be in the interval [L/A, R/A]. The number of divisors of M from this interval can be found by binary search.
You may even iterate through all divisors of N and M and just check if L<=A*B<=R.
Yes, it seems that the worst case is the number 223092870=2×3×5×7×11×13×17×19×23, which has only 2^9 divisors, so it's 2^18 pairs at most.
i think the worst case is 931170240. this number have 1344 divisors.
I am pretty sure, that your estimation is not correct (for example, you may use 2*2*2*2*2 instead of 2*23), but you may assume that the number of divisors for such small numbers is O(N1 / 3), and the total complexity of our algorithm will be O(N2 / 3)
I'm still unable to understand what Problem B was. Can someone please explain the output of the sample case or any other case?
You should find a path in the given graph with minimum possible max edge weight.
Couldn't understand the purpose of problem X — Fake testing problem.
People were asking for some way to be able to test code on the server in case of compiler configuration problems. I think this solution proposed.
You can build your source file on Testing server and run it. e.g. you can debug TL for your solution.
it's as codeforces's custom test
How to solve problem B (Elimination round 1)?
My solution — in cycle pick every city as a center.
Central city can be allocated to either top or bottom cities group depending on where you need it by shifting line some infinitesimal amount up or down. We can do it because no three cities lie on the same line.
After you picked central city you can use magic atan2 function and simulate rotating line through your central city and calculate how many people live above or below it. You can do it by sorting two lists by atan2 value (or one list) and going through it with two pointers. Pick minimum, but remember that you can always allocate central city the way it's better for you (my code was like abs(abs(x) — central)).
I bet there are easier solutions but this one got ACed and I am happy with that.
For me it was tough round, much tougher then Round 1 in GCJ this year. I solved just one problem and spend 1 hour solving Saw or Not To Saw — I think I was very close, but couldn't get through WA3 :(
Moved to: Proper thread for discussion
You can use orientation in integers, but use atan2 in doubles?
With coordinates limited by 1,000, double precision should be more then enough for all angles. Though I already see that it was bad solution — over complicated. Costed me 15-20 minutes of my time.
coordinates were limited by 2⋅104
and with good tests no solution with bad-written doubles should pass imho
If so, I defy you to show us test where atan2 is not sufficiently precise (on long doubles, why not?)
of course it's difficult to construct such test. And in this problem I think atan2 is sufficiently precise
so maybe using orientation everywhere is paranoia, but a good one ;)
This is overcomplicated? I think that your solution is the simplest possible one. What can be even more simplified?
I used more complicated approach where I maintained array of prefix sums of possible divisions when sweeping points with line of a fixed inclination and updated it appropriately when rotating this line.
I liked idea of taking pairs of dots and drawing lines between them. I think if this idea struck my mind I would finish this question in 15 minutes, not 35. But I often experience that — coding more complicated solution.
But thank you for admitting that red coders sometimes do complicated things too. :)
What do you mean by that idea?
Found it in this thread above. I just realized that it is O(n^3), to test all pairs of cities and calculate population on each side. So maybe not good idea. Ok, my solution is not over complicated :)
It isn't real solution, but here's some magic!
http://ideone.com/YeLtmM
Rotate point around origin by
, and try all possible y axis, as a "divide line". Do it K times.
Did it pass all tests? I tried with this idea, but failed on test #12 :((
Update: Accepted. There was a bug in my solution. :sosad:
I wrote a similar fake solution. I tried MAGIC = 20,000 random dividing lines :)
http://ideone.com/MTRn2I
How to solve Problem F — To Saw or Not to Saw?
I got 2 formulae by using similarity of triangles:
Got WA on testcase 3.
ans = gcd(a, c) * min(b / a, d / c)
It may sound really stupid.. but how can one get to this formula?
Let me rewrite it a bit:
ans = gcd(2a, 2c) / 2 * min(b / a, d / c)
The first part d = gcd(2a, 2c) comes from the following observation. Let's assign integer numbers to each peak of the saws and let's put two saws so that 0-th peak of the first saw will be exactly above the 0-th peak of the second saw and denote this coordinate as X = 0. If you plot the rest of the peaks then peaks of the first saw will have coordinates xi = 2a * i for each integer i, similarly peaks of the second saw will have coordinates yi = 2c * i. Then you plot all those peaks as points on X-axis and the question is what is the smallest distance of first saw peaks and second saw peaks. In other words what is the min(dist(xi, yi)) = min(abs(2a * i - 2c * j)) for any integer i and j. If you solved enough number theory problems it will be clear to you that this is equal to d = gcd(2a, 2c) = 2·gcd(a, c).
Now you have this d number. If you plot peaks again you should see that the optimal solution would be to move one of the saws d / 2 units left or right and then move them towards each other as much as possible. How much you will be able to move it depends on the "sharpness" of the saw's teeth (i.e, b/a ratio). Then if you know d already the result is simply l = d / 2 * b / a. Then you replace b / a with min(b / a, d / c) because you need to consider the case when first saw has "sharper" teeth.
Thank you :).
It's crystal clear now..
Thanks for your time
well and if a = c ? I put min(b,d) but it's WA on 4th
Just my luck. Picked the weird looking problem earlier on only to realize there was an easier one waiting. Started solving and couldn't submit by 5 seconds. Submit in upsolving mode and get Accepted.
Can someone start a new thread with editorial to the problems of Elimination Round 1.
I think I can learn a lot from the editorials of this round. Problems were a lil tough for a beginner like me.
It's already there apparently: http://mirror.codeforces.com/blog/entry/18078
Thanks :)
PS : The thead started just after I posted that comment :)
My code (for Elimination Round 1 problem E) gets TLE in test 9 with 2.093s. How can I improve it? What's the problem?
Thank you in advance!
Here is how I did it. Hope it helps.
I am currently too sleepy to read your code so I can't really say why yours failed. Sorry.
Thanks, it helped. I forgot to compress queries in which k=1.
My opinion is that problemset was very nice! C, D and F were very interesting in my opinion! B and E were also OK. Unfortunately A was tedious, any deeper thought, just a lot of cases to consider.
You can write A with almost no special cases
How? My solution has about 10 ifs.
I do not measure number of cases in number of ifs, rather in number of different constructions. My solution
OK, that sounded like a challenge, so I went for it and managed to get this accepted by this code: http://ideone.com/kFdFxb It doesn't contain that many ifs (only 5), but it is still tedious >_>... I think that analysis of those cases is nonomittable (case when cur_wid == l[hor] is especially nasty xd) and if you have more elegant solution I would like to see it.
During contest I didn't give that task a deeper thought, because I haven't even read it, because in half of the contest I have to made a choice which problem to do next — A, C or D. A had least amount of ACs within top people (but now I see that it had much more ACs that time :d) and had longest description, so I disregarded A and choose D since I quickly got and idea how to do this. After contest I thought that it's all about cases, so I didn't think about this much :P.
Are you implying that you haven't seen about 10 problems which are basically equivalent to B? Those half-plane things appear over and over and over again.
Uh, OK, indeed it is not very innovative problem, but at least there was not anything which will cause me to complain about something, for example no restoring result, no collinear points etc.
For problem C,I find the fomula: dp[n][k]=dp[n-1][k-1]*(n-k+1)+dp[n-1][k]*k (1<k<n) using bruteforce.But what's the logistic in it?
(I guess that you meant problem C). Don't tell me that it's true :o!? That looks very mysterious for me. I got AC (after contest) using much more complicated DP with n^3 states, some binomials and stupid trick allowing me to fit in O(n^2) space ;__;.
UPD: Yeah, it looks that it's true, however I don't have time now to wonder why is that. Here's my code: http://ideone.com/GdOSTe but compared to your solution I guess it can be mainly used to make fun of me :P.
Can you explain more about your idea?I really can't understand it.
I consider similar type of game. When we delete only the smallest card, not smallest or largest. Observe that game when there are n cards and we want to end up with k-th card is a sum of two independent games of that type (one with cards 1..k, one with cards k..n) when we delete last card in turns of the same number — this is key observation to whole solution (one of them (k..n) is reversed, that means that we delete the largest card instead of the smallest one).
Given that I compute dp[a][b][c] which tells how many of such games are that we are given a cards, largest card is on b-th position and we delete it c-th moment we see it. pref[a][b][c] = sum dp[a][1..b][c]
Fitting in O(n^2) space is little tricky. Given formulas for dp I can compute dp for dp[a][..][..] given only dp[a-1][..][..], I do not need previous values of a, but when counting answer I have to combine games of sizes k and n-k+1, so I either need to separately count this for dp[k] and run everything once again for dp[n-k+1] or observe that analogous property holds for number of checks and when combining games I always combine two games with the same number of checks (I used second approach).
I think the c-th moment factor is also the hard and key point to solve the problem.And it really needs observation.
This formula is also number of permutations with k-1 rises (position such that a_i < a_i+1). It's easy to see why it's correct but I still haven't found connection between that and C problem. Maybe there is a bijection?
Here is the explanation
And by the way, why is that formula correct for calculation the number of permutations with k-1 rises? UPD Got it, nevermind
this was hard