Hello everybody!
Tomorrow, at 10:00 Moscow time will be held Round 1 of Yandex.Algorithm competition, authored by me. I would like to thank Zlobober for all the job he does to make this competition interesting, MikeMirzayanov for the great polygon that ease the preparation process a lot, and everyone, who tested the round and made useful comments. Of course, we did our best to make the problem diverse by topics and difficulty.
See you in the competition dashboard!
UPD Thanks to everyone who participated, hope each of you found at least one interesting problem. We apologize for the situation with problem F, we have googled for all the problems and asked all testers whether they have seen such problems or not, but that didn't helped. The editorial has been published.
What do we have to do in order to qualify to the second round?
Nothing, everyone can participate in rounds 1-3. In each round, top 30 get some points, and in the end, people with the most points go to the finals.
How do you select t-shirt winners? If there are only 4 rounds with 30 people earning any points.
If two participants have the same amount of points earned(0), lowest rank in all 4 rounds matters. I dont actually understand what happens if somebody skips one round but in others he is like top50, he loses his chance to win a t-shirt?
What if you didn't participate in all 4 rounds?
I guess the ranks are compared numerically, i.e., the 1st place is "lower" than the 2nd place.
having a combined rank-list like this from the previous year can help
Actually now there is one, link
To advance to final you have to submit a solution to at least one task. Nobody said about submitting to get tshirt. Hack found!
Problem F == http://agc009.contest.atcoder.jp/tasks/agc009_d == http://main.edu.pl/en/archive/oi/11/jas
It has a nice solution, need to make sure that everyone has seen this problem!
That's a great pity for us, but nobody among contest authors and testers have seen any of these problems.
Both me and GlebsHP tried to Google this problem before the contest but we didn't succeed. As you can see, all three versions of this problem have almost nothing common in statements, so it was almost impossible to find them without seeing any of them before.
I haven't participated in a lot of contests recently, so I haven't seen it either. But I don't like when people submit something in 5 minutes that's obviously not an easy problem. Probably, I won't waste my time on Yandex contests any more.
That's frustrating and not a good thing to happen, but definitely not Yandex's fault (it's impossible to read and remember all existing tasks in the world). The same thing has happened in TopCoder, Codeforces, AtCoder, Facebook, etc.
Okay, and how to solve it? :)
You can find editorial from AtCoder's link.
Easy — just read the editorial: http://i.imgur.com/5dyupc1.png
Oh wait.
Here it is, page 9: https://atcoder.jp/img/agc009/editorial.pdf
How to solve C?
For every vertex, in any order: look at numbers of components in neighbours, choose minimal that is absent.
Proof: In the end, for component number K, there are edges to components K-1, K-2, K-3,... because otherwise we wouldn't be able to assign this number to some vertex.
What's the efficient way to get that mex?, I used set, but unfortunately TLE :(
Use a set, put all number from 1 to N in it. Then for each u, iterate every v that is adjacent to u, remove ans[v] from the set. Then mex will be the smallest value in the set. After that, put all ans[v] back into the set. P.s: ans[v] is the answer for vertex v.
What do you mean by ans[v] here?
Boolean array. Set true for already used ids, find first non-used in O(ans), then set false for all that we set true before. All is done in O(degree), total complexity O(m).
Stupid is most effective. Just dump heibours component numbers in array and sort it. Its O((M+N) log N)
I found the bug, the problem was something else, set should work fine, but thanks anyway
Can we see the codes of the participants?
So, since I've never seen it publicly stated, I think it's worth moving this discussion to the public at this point.
Java in Yandex.Contest got broken a few months ago — execution time slowed down in the 10x range, simple linear solutions with n=200000 now get TLE. Today's problem F is a good example — I got a TLE with the straightforward linear solution, I'm pretty sure that if you upload my solution to Polygon it will run in less than a second.
We have reported it through various channels, but it seems that this problem is very hard to solve for Yandex.
Given that the testing system is broken and fix is hard/impossible, would you please consider moving the remaining rounds to Codeforces or ejudge? It is really frustrating to get TLEs for linear-time solutions, and it's even more frustrating with the contest format where failures are super costly. Moreover, this impacts all problems, not just those where one actually gets TLE — having got such TLE in today's problem F with such simple code, how can I be sure in almost any other problem that I won't get a TLE?
Did you use Java7 x32? It worked for my F solution.
And yes, I remember we both had problems with Java in last opencup ;)
There was a jury message about this during the round
It said "Java7 or Java7 x32", but Java7 still got TLE (that's what I used).
Edit: never mind :)
It does indeed pass with Java 7 x32. Before the contest I asked the organizers which version of Java to use, and they told to use Java 7 x64 or x32 (also duplicated in the announcement), so I assumed that x32 and x64 have similar performance.
But I think it is somewhat besides the point. Even if it's possible to squeeze in a solution to this particular problem, some problems do not pass with x32, too (we had quite a few in the recent open cups), and what's more important, it is hugely disadvantageous in this contest format because you always fear getting TLE everywhere.
Well, it is a bit offtopic but...
How to solve F in O(n) time? Both AtCoder editorial and my solution (slightly different) work in time.
I was assuming various bitmask operations are O(1), which I guess is not strictly correct:
BTW, if i am not missing something then the last 4 lines could be ++mask
Petr
This part is equivalent to
I wrote the same O(N * loglogN)
Btw, this decomposition looks good. May be there will be more problems based on it, who knows ;)
Object creation is expensive in Java 7 x64 / Java 8 x64. The only reliable version is Java 7 x32 (why not add Java 8 x32? I wanna use streams and lambdas sometimes)
Please see comments above — we had plenty of cases where Java 7 x32 was getting unexpected TLEs in Open Cup, too. And I believe snarknews has rejudged our solutions from older Open Cup rounds and they got several times slower, so something is definitely broken with the system.
Our firs encounter with this issue was on an OpenCup problem where a linear solution with arrays of ints (so almost no objects involved) with n = 200000 was getting TL. So it's not object creation, but rather broken Java.
FWIW, exactly this issue was discussed during the recent marathon round one week ago. My measurements back then showed that even Java 7 32 on server is several times slower than Java 8 locally.
I don't understand why is it so hard just to roll back to the state several months ago, when everything was working fine... Also, so far I've never seen any Yandex representative even acknowledging that the issue exists, which is mildly frustrating (given that many different Java-users are complaining about it after every single contest).
For the sake of transparency, it would be much nicer if someone from Yandex publishes smth like "we changed <this and this> several months ago, which broke Java, sorry about that, we're going to do <this and this> to fix it".
Hi. Thanks for taking part in Round 1 and sorry for the trouble caused, there is indeed a significant slowing down in java execution on large input data cases.
We prepared the problems in such way that they would be less affected by the java issue, made sure to add problem X for server side testing and notified all contestants about java 7 recommendation at the contest start.
Nevertheless I understand that wasting time on problem X testing and not being sure in your language of choice is annoying.
We put our best effort to this problem right after the opencup round, where the problem was reported, and will do so in two upcoming weeks before the next algorithm round.
Thanks a lot for looking into this problem, and for telling more about the measures being taken. I'm really sorry for assuming that nothing was being done — now I understand that it was completely not true.
Thanks for acknowledging that the problem exists, and working on fixing it!
FWIW, the issue doesn't seem to be related to I/O (or at least, not just to I/O). It seems that Java heap is very slow for some reason (and I/O is just a side effect, because it allocates String objects). I've performed the following measurements, for Java 8 locally, and Java 7 32bit on Yandex.Contest server (and C++ locally/on server for comparison):
One can see that Java on Yandex.Contest outperforms my local Java on simple int operations, and performs roughly the same for de-referencing pointers. However, it drastically changes if I compare time of object allocation: allocating 10M objects is 13 times slower than locally (and it's not a system issue: for C++, it works just fine).
Ignore.
I've added assertion to my AC code that times are greater than 0 and it still passes. Probably you have some other problem
You're right. It's 4AM and I'm not thinking clearly. Thanks for the help!
I logged in using my Facebook account and the scoreboard shows that I'm from the US which is not true. Is it possible to somehow change the country flag?
Go to passport.yandex.com/profile and change your country (although I'm not sure if it works with FB login).
After doing that, I still cannot change my country and my display name.
does marathon round scored for giving t-shirt or you just send t-shirt for top 500 of round1,2,3 ?!
T-shirt winners and finalists will be determined based on 4 rounds (Marathon and Round 1, 2, 3).
Is this ranking accurate?
What happens if someone skips a contest?
AFAIK, the ranking is done as follows..
A participant can participate in any number of rounds (out of the four). If after the end of all the four elimination rounds, a participant has some NGP30 score (summation of all the four rounds), he gets ranked on the basis of that. (the larger the better)
Now, for all the participants, who have NGP30 score sum == 0, they are ranked on the basis of the minimum rank they have got in all the four rounds, (the smaller the better), below the participants whi have NGP30 score sum > 0.
If you don't participate in a round, it's equivalent to, NGP30 score 0 and rank infinity.
Yep, I understood that as well, but given the grand prix point system at most 120 people will have a score, probably much less. So now we rank the rest by minimum position. But then by that criteria a person who has been 50th in 3 rounds but missed one should be ranked lower than one person who participated in all rounds?
Yes,
If person A participates in only round-1 and gets a rank of 40, while person B participates in all the four rounds and gets ranks 150, 200, 180, 257 respectively, then:
minimum rank of A = 40
minimum rank of B = 150
and hence person A gets a better rank than person B.
Oh, I misanderstood minimum instead of maximum, my bad
General rant against such comparisons
It's a bit weird to compare people by ranks in contests that have unequal participation. For example rank 200 in marathon(which had ~400 participants) is over rank 201 in Round 1(which had ~800 participants)[assuming both don't participate in other rounds]. Besides, you are comparing someone's skills in approximate challenges with someone's skill in Algorithm tasks, which is weird in itself.
But it's your decision, so if this is intended result, it's okay.
Is there O(1) B solution?
Almost constant I guess (independent of N)
A shorter version of your code.
What is the solution for D? I came up with O(N^4 log N) but didn't write it.
Anyway here is my idea: Divide bets in three categories. Let us focus on W-bets. We compute dp[1...N*M] where
It can be computed in O(N^2*M) (we add bets one by one and update all N*M answers)
We compute similar dp for L-bets, and D-bets. Now we do a bin-search for the answer. For an amount of money C we fix an outcome from W-bets and L-bets and find if there is suitable outcome in D-bets. It will take O(N^4 log N).
Replace ai and bi with xi=bi and yi=ai+bi . You can restate problem in the following way: for each bet you take you receive xi and in case of proper outcome you pay yi. Now notice that for the chosen subset of bets, you receive sum of their xi and may lose maximal of three sums of yi for W,D,L respectively. Iterate over maximal loss X and pick best subsets of bets with loss <=X. Your dp suits it quite perfectly if you replace a and b with x and y.