Начнется сегодня, в 21:00. Приглашаю всех прошедших в отборочный этап участников перейти по ссылке на раунд. Традиционно, раунд продлится 100 минут и будет оцениваться по системе Гран-При 30. Победа в прошлом раунде принесла pperm86 100 зачетных очков и участие в финальном раунде! Кто обеспечит себе приглашение в Берлин сегодня?
Удачи!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | pajenegod | 145 |
| 9 | Petr | 145 |
Do you know how to determine who will win T-shirts?
I know for sure! Check out the Awards section of rules.
Top 150 participants of the elimination stage (more score points, then more problems solved, then with less penalty time) will receive a souvenire.
souvenir = T-shirt? :)
are the contest problem available in english also ??
Sure! The link
http://contest2.yandex.com/algorithm2014/contest/505/enter/
should show you all information in English.
thanks, this gives me redirect loop error in chrome but works in firefox... might be some cookie problem or something !!!
After going through the link I'm getting "You can not participate in the contest because the registration is closed" ???
I have advanced to elimination stage(Yandex has sent me a email for this), but when i entered to round 2 i saw this sentence: "You can not participate in the contest because the registration is closed"
What's wrong???
Try to login maybe
Thanks, but i've login already. I missed round 1 for the same reason above. I don't want to miss round 2 too. Any help will be appreciated.
Please, see personal messages
Как решать C?
Случай, когда компонента одна проверить легко. Научимся выделять случай, когда 2 компоненты. Заодно, сразу будем считать, что у прямоугольника-запроса обе стороны имеют длину хотя бы 2.
Можно понять, что на границе нашего прямоугольника не может быть больше двух "отрезков" одного цвета. Проверить количество отрезков одного цвета на границе можно за О(1), предпосчитав частичные суммы количеств смен цвета на строках и на столбцах. То есть, если у нас больше двух отрезков, ответ сразу 0.
Если у нас 1 или 2 отрезка одного цвета на границе, то нам нужно проверить, что строго внутри нашего прямоугольника нет никаких других компонент связности. Для этого в самом начале, выделим компоненты связности и из каждой выберем по одной клетке-представителю. Построим массив частичных сумм, который будет говорить, сколько в нашем прямоугольнике клеток-представителей компонент. Тогда мы можем легко посчитать количество компонент внутри любого прямоугольника с той оговоркой, что компоненты, прилегающие к его границам могут как учесться, так и нет. Но их не более двух, так что можно просто это проверить отдельно. Выходит O(1) на запрос и предподсчет за O(N^2).
Sorry, i did not get your 3rd para. Can you please translate that for me?
упс
А откуда там
?
У меня там O(1), не считая gcd.
Нормальное решение тоже интересно узнать, конечно.
Поскольку никакие два вектора не коллинеарны, то существует только одна тройка (d1, d2, d3) с точностью до домножения на константу такая, что d1·a + d2·b + d3·c = 0. Находим её, решая систему из двух линейных уравнений, делим на gcd(d1, d2, d3) и находим те вектора с координатами не больше n - 1, при вычитании вектора (d1, d2, d3) из которых хотя бы одна из координат вылезает за отрезок [0, n - 1].
А можно поподробнее по поводу нахождения такой тройки (d1, d2, d3)?
У нас система из двух уравнений вида d1·ax + d2·bx + d3·cx = 0, положим d3 = 1, найдем решение системы линейных уравнений 2 × 2, а дальше домножим на общий знаменатель
Посчитаем такие минимальные по модулю ua, ub и uc, что uaa + ubb + ucc (например, методом Крамера). Если |ua|, |ub| или |uc| ≥ n, то ответ равен n3, иначе n3 - (n - |ua|)(n - |ub|)(n - |uc|).
Решение на O(N2log(N)) — перебираем все u и v от 1 до N. Для каждой такой пары смотрим, куда попадет вектор u * A + v * B. Очевидно, что точки в ответ будут выбираться из прямой, параллельной вектору С и проходящей через эту точку. Для некоторых различных пар (u, v) вектор u * A + v * B может попадать на одни и теже прямые, нам надо будет такие повторяющиеся прямые учесть. Простой способ найти повторяющиеся прямые — это запихнуть все в один массив и отсортировать по ключу, который уникально бы идентифицировал прямую. Из-за этой сортировки и всплывает логарифм.
Еще и с запасом в 3 раза.
Contest for Red coders :( this round really contains very hard problemset
Такой вопрос: у меня во время контеста у решения, отправленного в открытую, был вердикт "Тесты из примеров пройдены", хотя в мониторе был +. После окончания контеста вердикт поменялся на "OK", как и для решений, отправленных в тёмную. Это нормальное поведение или баг?
увидел, что D в итоге самая лёгкая. как её просто решать? сам долго писал решение за nlog2n.
Находим длину, потом ставим одно число на первое место, остальное выводим в обратном порядке.
Ах блин точно. Иногда лучше чуть подумать, а не писать бинпоиск с фенвиком :)
сначала, понятно, найдем такое минимальное n, что n * (n — 1) / 2 >= k. все, теперь мы знаем длину перестановки. теперь она восстанавливается однозначно! пусть мы хотим поставить i-ое число от начала и нам осталось сделать cur инверсий(изначально cur = k). тогда с помощью оставшегося суффикса мы сможем сделать mx = x * (x — 1) / 2 инверсий(x = n — i)и получается нам надо поставить число, которое будет образовывать с суффиксом val = cur — mx инверсий, т.е. надо найти val-ое число по возрастанию из еще не поставленных. это можно сделать фенвиком, но я его не знаю и sqrt-декомпозицию написал. итого n * log(n) с фенвиком и n * sqrt(n) с декомпозицией
тоже самое писал, только val каждый раз перебирал бинпоиском
Только вот каждый раз кроме первого надо будет брать самое маленькое неиспользованное
Большое же.
Да, конечно
У меня квадрат в одну секунду зашёл =)
How to solve A???
If you fix the first black vertex (closest to the central vertex from 1 end) in a cycle of c vertices, you can pack the next few black vertices in that cycle greedily; this way, you get the distance of the 2 black vertices closest to the central vertex equal to c%K + aK ≥ K (a: any non-negative integer such that the inequality holds).
Consider a valid solution (not necessarily optimal) where the first black vertex is fixed at some distance d from the central one, and the last one (in that cycle) is at a distance d' such that |d - d'| > 1. You can rotate the black vertices by 1 now, in such a way that the respective distances are d + 1 and d' - 1 (or d - 1 and d' + 1), so |d - d'| decreases by 2 and
increases by 1. This solution is also valid, so we can use this rotation and fix 
(integer division).
This tightest greedy packing of black vertices makes all pairs of black vertices in 1 cycle satisfy the condition, and the smallest distance between 2 vertices from distinct cycles is the sum of 2 smallest
-s. In case K is odd and there are x ≥ 2 cycles for which that number is 
(first division: integer, second: exact), we fail; otherwise, we win.
If we fail, we need to increment a for at least x - 1 cycles; then, we get the situation with x ≤ 1, and win. So we just need to find the obvious greedy bound B on the number of black vertices, sum of
(integer division, when taking each cycle independently), the number x of cycles for which 
and correct the bound B to B - (x - 1) (if x > 0). I hope it was at least a bit clear :D
For Problem D, I had the following idea, but had some problem while implementing:
Suppose we have sequence
1 2 3 4 5, then rotating the sequence would give 5 inversions ->2 3 4 5 1.So I thought that I just had to calculate the amount by which a particular subsequence should be rotated to come closer and closer to K inversions.
e.g.:
For K=8,
Initially:
1 2 3 4 5Step1: K - = 4
2 3 4 5 1Step2: K - = 3
3 4 5 2 1Step3: K - = 1
4 3 5 2 1So the answer would be
4 3 5 2 1Is my approach correct? How do I implement it? Or is there a simpler approach to go about it?
The number of inversions in your answer is 7, not 8.
Edited. Could you describe your method please?
Let inv[n] = n*(n-1)/2. Find the smallest n, such that inv[n] >= k. The first number in permutation is k-inv[n-1]+1, the others should be put in the decreasing order.
По моим подсчетам топ 8 участников гарантировали себе выход на онсайт
How to solve B?
Note that a bigger module does not influence after a smaller one, or if an initial number is smaller.
So we have a non-increasing subsequence, ending with the smallest number, and we can ignore other numbers.
Sort the numbers and run by them in non-increasing order. Keep in used[] array the set of numbers we have. Initially this set is empty.
At each step, take all the available numbers modulo a[i], add the results to the set and also add the number a[i] to the set (as an initial number).
There are some tricks with the smallest number. It can be unique or not.
The total time is O(largest number * N).
Thanks. I used exactly the same approach, but failed on test 18 :( The "trap" was that if smallest number is present in the array more than once, we should not add it to the set on the last step.
I solved problem D, using Binary Search.
First I find what is length of permutation such that total numbers of inversion is closer to k using the binary search.**(No of inversion = n*(n — 1) / 2)** as maximum value of k can be 10^9 so I took upper limit as 10^5 + 1 and lower as 0(because 0 inversion 1 element at least). suppose we got length of permutation as length,inversion of this length as inversion Now I got length of permutation , so now I have to make this permutation so no of inversion should be equal to k. So inside while loop taking condition as while(inversion > k) do binary search on permutation from 1 to length such that (inversion — (length — (result after binary search)) >= k) Then I add it int array.Print it first and print the remaining one in decreasing order.
for example ;
k = 4
after binary search it will give length of permutation as 4(No of inversion is 6).
step 1 — 6 > 4 : after binary search on permutation from 1 to n we find that 2 is best because(6 — (4 — 2)) gives us 4 which is greater than equal to k.we add 2 in array. step 2 — 6==4: loops break;
print length; print elements added in array. print remaining element in decreasing order
so output
4 2 4 3 1
I got accepted in second time because I added wrong element.
My solution -
I solved problem D, using Binary Search. First I find what is length of permutation such that total numbers of inversion is closer to k using the binary search. ** (No of inversion = n * (n — 1) / 2) ** as maximum value of k can be 10 ^ 9 so I took upper limit as 10 ^ 5 + 1 and lower as 0.
Suppose we Got permutation of length as length , this length of inversion as inversion Now I Got length of permutation, so now I have to make this so no permutation of inversion Should be equal to K.
So inside while loop taking condition as while (inversion> k) do binary search on permutation from 1 to length such That (inversion — (length — (After Binary search result))> = K) Then I Add it int array.
Print it first and print the remaining one in decreasing order.
for example; k = 4 after binary search it will give length of permutation as 4 (No of inversion is 6).
step 1 -; 6> 4: after binary search on permutation from 1 to n we find that 2 is best because (6 — (4 -; 2)) gives us 4 which is greater than equal to k.we add 2 in array.
step 2 ; 6 == 4: loops break; print length; print elements added in array. print remaining element in decreasing order so output 4 2 4 3 1 I got accepted in second time because I added wrong element.
Edit- It got posted in Russian, so need to paste it again in english. My solution
А какое предполагалось решение в F?
Видимо, предполагалось использовать фишку, что количество различных длин циклов в перестановке
.
Я написал решение, которое работает за количество различных длин циклов в кубе умножить на вычисление gcd и получил TL. Добавил запоминание в gcd для чисел меньше 1000 и получил ОК. Вот мне и стало интересно, действительно ли авторское решение такое же.
У меня каким-то чудом без всяких запоминаний прошло.
Видимо чудо называется плюсы :)
Java? На С++ у меня такое решение без запоминания gcd работает 2.079; с запоминанием 0.797.
Ну вот у меня на джаве где-то 5с -> 2c.
Ну решения без запоминания тоже разные написать можно. Можно вычислять gcd 2 раза в самом внутреннем цикле, а также использовать при его подсчете long long. Это работает медленно, но еще может пройти. А можно написать его в интах и считать во внутреннем цикле только 1 раз. Такое проходит c хорошим запасом без всякого запоминания. В любом случае, даже первое решение заходит на Java, правда впритык.
А ещё можно после объединения первых двух перестановок отсортировать список и пообъединять циклы одинаковой длины, и только потом объединять результат с третьей перестановкой.
In Gym: 2014 Яндекс.Алгоритм - Отборочный этап, раунд 2
В Тренировках: 2014 Яндекс.Алгоритм - Отборочный этап, раунд 2
Почему задачи A и E совпадают?
Solution for problem E (user requested):
Suppose that there are two triples (ua, ub, uc) and (va, vb, vc) such that uaa + ubb + ucc = vaa + vbb + vcc. Then (ua - va, ub - vb, uc - vc) is an integer multiple of some fixed triple which could be found by solving a linear system. Let that triple be (da, db, dc). Suppose that da, db, and dc are nonnegative (actually, changing their sign doesn't affect the answer). From every triple (ua, ub, uc), where each of ua, ub, and uc is between 0 and N - 1, subtract (da, db, dc) while the result is still within those bounds. The final set will contain the points which have either ua < da, or ub < db, or uc < dc. The number of such points is N3 - (N - da)(N - db)(N - dc), and this is the answer. However, if either of da, db, or dc is at least N, the answer is just N3. Total complexity: O(1) (ignoring the GCD computation).
I solved it in O(N2) by trying all ua - va, ub - vb, computing the necessary uc - vc for them and checking how many solutions they take out. A really simple solution. Pity that I didn't do this problem instead of F during the contest, I would've probably gotten a better place (at least thanks to time) :D
How to solve F? My idea was for each of the 3 permutaions, we can get cycle lengths of the permuations, and then we can take 3 cycles from 3 permutaions, and for all 3 cycle combination count how many coin it will take to visit all grids having co-ordinates in those 3 cycle combination, add these to get the result. But time complexity becomes O(N^3). How to do this?