Уже сегодня, 15 июня, в 13:00 начнется заключительный раунд отборочного этапа Яндекс.Алгоритма. За 100 минут будут разыграны в общей сложности 718 зачетных очков, которые определят состав финалистов. Все три призера Яндекс.Алгоритма 2013 уже гарантировали себе участие в финальном раунде. А вы?
Кто-то в курсе, что такое WA12 в B?
кроме как забыть про случай 'if (n < k + 2)' я не могу ничего предположить)
Ага, оно, спасибо)
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).
Как решать "F. Странная игра"? Шпраг Гранди дает TLE на 12 тесте. =)
Будем считать функцию Гранди отдельно для каждого L.
Во первых, функция Гранди не превосходит 300 для L ≤ 50, и не превосходит 15 для 50 ≤ L ≤ 7000.
Во-вторых, для больших L (начиная с 50) наша функция имеет много длинных отрезков, где она постоянна. Достаточно рассмотреть случай, когда длина одной из новых частей попадает на границу этого отрезка постоянства. Например, если наша функция постоянна на отрезках [1,50], [51,70], [71,110], то достаточно рассмотреть случаи, когда один из двух кусков имеет длину 1, 50, 51, 70, 71...
Вместе эти два наблюдения позволяют ее посчитать за пять секунд (для всех n, l ≤ 7000). Думаю, подбирая константы менее грубо, можно еще быстрее.
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
как решать В?
как получается эта формула?
сначала заметим, что если n < k + 2, то ответ 0
посчитаем количество удовлетворяющих наборов. их будет (n - k - 1) * 2n - k - 2, так как наличие фрагметна может быть в любом месте, а все что не в нем нас не волнует. всего же вариантов 2n, таким образом ответ будет![](https://espresso.codeforces.com/f2a66e44deb554cdf39b28378892b61ac69909f6.png)
Нам нужно посчитать E(кол-ва) = Е(I(первые k + 2 образуют что нужно) + I(2..k + 3 образуют) + ...) = [линейность матожидания] = EI_1 + EI2 + ... = (кол-во позиций)*(1/2^(k+2))
оказалось, что %I64d не работает ни для одного с++ компилятора :(
Ну а с чего оно должно работать-то? это же MS расширение, а MS компилятора — нет. В чем проблема юзать %lld, который стандартен. Раньше он не работал на КФ, но сейчас уже давно работает.
(А вообще cout тащит)
DELETED, double comment.
cout
медленный и длинный по количеству кода. Но тут вроде не проблема.А
%lld
и%I64d
по факту не всегда взаимозаменяемы на Windows — зависит от комбинации компилятора, версии Windows и установленных msvcrt.Он и не обязан работать: http://msdn.microsoft.com/en-us/library/tcxf1dw6.aspx
То, что работает, см. здесь: http://en.cppreference.com/w/cpp/io/c/fprintf#Parameters
Как решалась задача C?
Перебираем правую границу R от 1 до N. Каждый раз нам надо знать максимальный j такой что a[j]+d или a[j]-d встречается после этого j. Прибавляем этот j к ответу. Как пересчитывать этот максимум: для нового R ищем когда последний раз встречался a[R]+d или a[R]-d (обновляем HashMap с ними или что-нибудь такое), пусть a[x]=a[R]+-d , тогда обновляем j: j = max(j, x)
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.
Я может быть что-то пропустил, но все-таки меня интересует, а будет ли официальный разбор от Яндекса?
В прошлом году он был и с указанием авторов контеста. А сейчас приходится вычитывать это в комментариях под постом. Тоже вариант, но все же :)
Авторы 3 раунда: я и RAD. Официальный разбор в процессе подготовки, но сомоорганизация на Codeforces просто великолепна, и все задачи прекрасно разобраны еще до того как мы проснулись :)
Я скорее про то, что это стало хорошей традицией не только для этого конкретного раунда от Яндекса :)
In Gym: 2014 Яндекс.Алгоритм - Отборочный этап, раунд 3.
У меня пара вопросов: Что значат крестики возле ников в таблице по трём раундам, столько людей забанили? Так что же пологается тем кто попал в 150?
Если навести курсор на крестик, то появится надпись "не может поехать на финал".
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.
Я решаю "D. Злые палиндромы" на JAVA с помощью BigInteger и получаю TLE? Надо просто свой BigInteger делать? Или я просто слишком небрежно пишу код?
Мое решение достаточно простое (для 0<K и 0<N): считаем CNT кол-во палиндромов, больших данного числа и имеющих такую же длину как и число N. Если CNT <= k находим данный палиндром. иначе решаем задачу для N_NEW = 10^длина_числа(N) и K_NEW = K — CNT.
BigInteger двоичный, преобразование из десятичного в двоичный и назад дико тормозные.
Спасибо. Хорошее замечание. Я думал что в 10ой хранится или в 1e2 или 1e9 и т.д. =) Уменьшил кол-во BigInteger, кое-что переписал (сложение в столбик). AC =)
У меня что-то в таком роде прошло как раз (где-то за 1.5с), так что где-то у вас много лишних операций
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 :)
Начало задачи F в виртуальном контесте выглядит странно: