Today, on June 15 at 1 p.m. MSK the last round of Yandex.Algorithm elimination stage will begin. Crucial for determination of Yandex.Algorithm finalists 718 score points will be distributed during these 100 minutes. Three prize-winners of Yandex.Algorithm 2013 have already reserved a place in the final round. Have you?
Oh, NO!! I get the 26th place. :(
The task C is too evil, I misunderstand the task (ask pair of i, j s.t. abs(x[i]-x[j]) = d) but can pass all examples.
26th place isn't so bad: if someone declines onsite invitation, you'll be invited instead (if I understand correctly).
I don't know if they have such rule. At least in last year all top-25 attend the finals.
And if it's very late to happen, then I don't have time to apply visa. Maybe you will attend instead, because you don't need a visa. :)
Some of my predict come to truth: I did get the invitation, but I can't get obtain the visa in time. Unfortunately it is to late to invite you instead. :(
I first thought of reducing it in such a way, but then I realized it doesn't work that way so simply :D
Sometimes, many successful solution and passed samples can be deceiving. It happens to me quite often in TC, since they sometimes don't have maximal samples or have too weak ones. Once, I even passed the samples with a solution that had several serious mistakes in one formula... I guess they cancelled each other out or something :D
Yes, but I think at least the examples should check if you read the statement correctly.
It feels like something similar to last SRM (mod 1e9+9).
I have "I64d or lld" issue!(I thought that was the same as Codeforces).
My blind A gets WA. My open C gets 4 WA before OK (after the 4th WA I turn to solve E first. Then C gets OK).
That's not a good experience for me. Hope next time there can be some clarification about that. :D
How to solve problem F? Got TLE using SG.
For L<20 I use SG. For L>=20 I use the following:
and the formulae were derived by running SG for each L and noticing the rules.
Apparently the next N is 397*L-121, this works for N >= 14 and is over 7000 for N >= 18. I have some intuitions why this would work, but I have not really proven anything.
Of course I meant L >= 18 and L >= 14.
Please, give some intuitions why this work. :) How you get this formulas?
Probably observed from running the bruteforces. We can obviously see that if 2|(N - L) or N - L < = 2(L - 1), then it's possible to split the game into 2 identical ones or 2 instalosses in the first move; SG works fast for N up to about 1000 and decently fast (not good enough for a submit, but good enough for observing the rules) for N up to
, so it's just a question of observing some rules for the remaining L (and these are large, so there are likely many winning strategies, if any).
Xellos is right, from running the bruteforce. If you fix L, you can find all N such that the second player wins in O(N*L) time. This can be done for all values of L in reasonable time, and you can list all such pairs (L,N) and look for rules. There are not many such pairs (usually F wins) so it is quite easy to see that 3L-1, 5L-1, ... are S-wins, which can be confirmed by asking the program to write L in this form. Low values of L are irregular, so just solve them with SG.
As for intuitions: assume that L is big enough. For N=L the first player wins. The same happens for N up to 3L-2 by playing in the middle, but at N=3L-1 this no longer works, and the second player wins. At 3L the first player wins again by playing the middle, which works until 5L-1, where apparently something happens again (I have not analyzed it). And so on.
In Gym: 2014 Яндекс.Алгоритм - Отборочный этап, раунд 3.
How can I solve problem E?
Calculate centroid of tetrahedron and consider its projection to the surface z=0: 1) If it lies outside of triangle formed by the first 3 coordinates, then the answer is 'Falling'; 2) if it lies on the edge of triangle, then the answer is 'Unstable'. 3) if it lies strictly inside of triangle, then the answer is 'Standing'
Ok. thanks! But how can i calculate centroid of tetrahedron?
You just google for the formula:
Similarly for other coordinates.
The funny thing is that this centroid is the same for a filled tetrahedron and for unit masses in ints vertices.
You can split the tetrahedron into many thin homothetic triangles parallel to any face; their centers of mass lie on 1 line, so the tetrahedron's will lie on it too. And you can show that a filled triangle's center of mass is the same as that of one with unit masses in its vertices, in the same way by splitting it into thin rods.
How was problem A to be solved? The one in which we had to count the number of pairs of nodes at a distance 2 from each other?
Notice that the graph is a tree. It's obvious that there are no triangles, so we're counting paths of length 2. Fix a central vertex of that path, then all pairs of its (distict) neighbours are endpoints of one such path. Alltogether, there are
, where D[i] are degrees of vertices.
Is there any news about T-shirts?
I got a mail from lperovskaya yesterday, asking me to complete/check my address and T-shirt size.
Is there any other way to solve problem B other than matrix exponentiation?
Lol, yes
Obvious linearity of expectation
I found a recurrence relation,based on the current length of the string,and current length of the pattern already matched(BW...WB).Can you kindly explain how this closed formula can be derived?
There are n - k - 1 positions where this pattern can be matched and probability of occurence in a fixed position is 2 - (k + 2), so result is (n - k - 1)2 - (k + 2)
Thanks a lot :)