Прошел четвертый этап XV Открытого Кубка по программированию. Как решать задачу D?
Прошел четвертый этап XV Открытого Кубка по программированию. Как решать задачу D?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
Задача K — WA 13 у кого нибудь кроме меня было ?
По D у нас была такая идея (сдать не получилось):
Рассмотрим простое число, на которое будет делиться НОД. Для каждого такого числа сохраним отсортированный список позиций, на которых находятся числа, которые делятся на это простое число. Суммарная длина таких списков будет
, т.к. каждое число войдёт не более, чем в 
чисел. Далее Будем считать, что у нас есть массив из 1 (сохранённые позиции) и - 1 (позиции, числа в которых не делятся на p. Нам нужно найти самый длинный подмассив с положительной суммой. Задача, кажется, известная. Мы пытались решить с помощью дерева фенвика...
Можно просто отсортировать префиксные суммы и дальше за O(n).
for every prime number P get list of positions i, where a[i] is divisible by P,
Let's denote positions as p.
So, we need to find, (j, i) such that p[i]-p[j] is maximised and next condition is hold
* p[i] — p[j] + 1 <= 2 * (i — j + 1)
or p[i] — 2*i <= p[j] — 2*j + 1
By using interval tree, for one prime, time complexity is O(|p|log(|p|))
Overall time complexity: O(n*log^2(n))
When working with a prime P[i], I always built the segtree with the vectors related to that prime. And started to find the maximum index. It was a nice problem to solve during the contest time.
Что такое WA31 в Е?
У нас было переполнение long long
C: Apply Burnside's lemma. We don't need to try all permutations: if the permutation graphs of two permutations are the same, we get the same results, so the complexity is O(partition_number(N) * something). Still my program required 10 minutes on the max test, so I computed all answers locally.
F: I believe we need bitset here — does anyone know a good way to use bitset when the length is not fixed?
K: Here is the tricky case: 1 4 | | 2-5 | | 3 6 Edges 1-2, 2-3, 4-5, 5-6 can't be in the decomposition at the same time.
Could you post a few first answers for C? I got mine working 10 minutes before the end, it required about 30 minutes to run, but I got WA after submitting the result :(
Answers for n <= 10:
answers
wow, how did you receive them?
I'm developer of the problem :)
We had used Burnside's lemma... But it's long story with Gaussian Elimination and dynamic programming...
There is no need in Gaussian Elimination :Ь
Code.
It computes answers for all N up to 60 in less than 2 seconds (about 1.5 seconds), that's why it may look ugly.
Nice!
Thanks! Apparently my answers match for n<=10 :(
What's the answer for n=60?
24697351
Interesting, this one is completely different. Will keep debugging.
Can you please give more insight for C? Thanks.
How to solve L?
Find centroids of the first tree, can be one or two centroids, try both.
Find centroids of the second tree. If there are two centroids try both.
We will try all combinations of centroids. Let's denote centroid of the first tree as v and centroid of the second tree as u.
Now, we will assume that the vertex v is the vertex u in the second tree.
We try to compare two subtrees recursively,
bool isSame(v, u);
Here, subtree u in the second tree should have one more vertex than subtree v.
Now, we will compute hashes of subtrees of children u and v, after that try to match two arrays of hashes, there should remain exactly one non-matching subtree from both tree. Check them recursively.
P.S. I may miss something. :)
Hi! Please can you tell why we cannot do that:
Get power of parent of that leaf ( x )
Sorry for my English, hope you understand me.
Shortly, your proposition is: If degree sets of both trees are equal, then you conclude that trees are also equal? If I understood correctly, this should be Counter Example:
First Tree:
1-2, 1-3, 2-4, 2-5, 3-6
Second Tree:
1-2, 1-3, 2-4, 2-5, 5-6
Be the way, how to upload a picture to Codeforces?
Yes, I suggest it. Thank you for your answer. But this part is hard for me because I cannot find some counter examples.
Anyway, thank you much.
How do you compute hashes of subtrees?
Как решить H и G?
G — 1. Искал (перебирая) пары таких клеток, которые обменяв местами, две клетки становились на свои места. 2. Если таких больше небыло, тогда обменивал любую пару нетронутых клеток, так чтоб одна встала на правельное место, и возвращался на первый пункт.
Кстати, я тут получил "Presentation error test 2", когда послал решение, которое ничего невыводит в указанный для вывода файл "puzzle-swap.out", а выводит ответ в stdout, непонимаю, как прошел тест нр. 1.
Тестирующая система принимает стандартный ввод-вывод вместо файлов. Всегда так пишем. Не знаю можно ли комбинировать: чтение из файла, а вывод в stdout.
Я читал из файла, а выводил в stdout. А про выше написаное — незнал, зачем тогда вообще эти файлы указанны.
Presentation Error — это нарушение формата. Формат можно нарушить, выведя не туда, а можно и как-то ещё. Второй тест — скорее всего, минимальный (уже отсортированная таблица, ответ 0).
В G почемуто заходит следующее:
1) Перебрем все перестановки строчек.
2) Внутри 1) переберем все перестановки столбиков.
3) Выполним эти перестановки. Потом все оставшееся добьем перестановками элементов.
H — будем перебирать шаг, на котором число N может вычеркнуться, начиная с 2. Пусть это шаг равен k. Если N делится на k — ответ -1 (мы вычеркиваем наше число). Иначе, до него есть ровно N/k чисел, которые вычеркнутся, значится позиции уменьшится на N/k. Моделируем до тех пор, пока k не превзойдет N. Можно запустить эту программу и увидеть, что для N = 1012 делается около миллиона операций (это без учета того, что ответ может быть -1, то есть это оценка сверху)
В G ясно, что это должно заходить. Пусть мы сперва поменяли какие-то элементы, а потом строки. Тогда ясно, как изменить порядок на обратный. Аналогично для столбцов/элементов. Строки и столбцы вообще независимы. Итого, из правильно ответа легко получить правильный ответ такого вида
Примитивное решение было.
1)Для каждого числа при счёте запоминаем его координату в первый массив. 2)теперь создадим ещё нейкий массив, в котором будем для числа хранить его координату(которую это число должно иметь в отсорченом массиве) 3)теперь просто перебор бежим i от 1 до 16 и смотрим если координаты i числа из первого массива не равны координатам i числа из второго массива то производим замену чтобы найти то число на которое нужно поменять пробегаем от j 1 до 16 снова и если координаты этого j числа из первого массива равны координатам i из второго массива то меняем местами эти две ячейки
http://pastebin.com/1UVBmJgZ
how to solve K, E, H, F ?(div2)
Кому-то удалось сдать K в div2? Мы постоянно получаем WA2, даже при попытке заслать правильное решение из div1 с поправкой на то, что корень всегда в вершине с номером 1.
Идея нашего решения: для каждого ребра посчитать количество запросов, которые через него проходят. Это можно сделать стандартным трюком с lca и динамикой по дереву. Потом суммируем количество запросов по всем ребрам и вычитаем самое тяжелое ребро выходящее из каждой вершины.
Расскажите пожалуйста, а зачем в интерактивной задаче создаются файлы input.txt, если они не работают? https://www.diffchecker.com/azmuvqut
Час дебажили буквально, потому что приходит WA1 и абсолютно непонятна причина.
А что написано в условии задачи?
стандартный ввод или input.txt
В PDF?
В pdf stdin.
Но это же не дело, когда в pdf одно, в Яндекс.Контесте другое. Мое решение работает и с stdin, и с input.txt. Оно не работает только в случае "есть input.txt, который не используется".
В Яндекс.Контест вообще условия на этом Гран-При не загружались.
Ну я вот эти читал: http://imgur.com/4wgKnYw
Интересно; возможно, что загрузили сами авторы; как минимум, я никаких условий, кроме pdf, не загружал.
Ну я без претензий, если что, просто в целях улучшения системы.
Нам одним пришлось решить задачу G без условия, только по сэмплу, и считать что это нормально?
Not bad :)
В самом начале был клар " Statements can be uploaded as PDF file.", и в той pdf-ке условие есть — и в английской, и в русской версии)
О_О" Там есть условие!
Не одним.
'can be', but not 'should be' :)
Они еще назвали ее «Головоломка», все сходилось.
Пора уже привыкнуть ко всем этим яндексовским фишкам:)
Кстати, без условия мне эта задача больше нравилась. В этом была какая-то изюминка что ли :)
Лол. Я думал суть задачи как раз догадаться до условия.
Да, я загружал, потому что lperovskaya попросила. А с этой задачей не справился, потому что табличка в условии, а как делать в yandex.contest таблички, я так и не понял. Ну и копировабельные сэмплы тоже приятный бонус.
Но да, написать "посмотрите pdf версию" я не догадался. То, что задача оказалось удачной для решения без условия это интересный эффект.
В задаче "J" нечитал пояснения к примеру, так как он был понятен и непротиворечил условию задачи. Написал то чего просили в условии — незашло.
Есть способы бороться с тем, что перед каждой посылкой мы должны менять язык со Scala на плюсы? Раньше что-то мы с такой проблемой не сталкивались.
Поддерживаю, словили бревно из-за этого :(
Не CE?
У нас вроде с этим было ОК
What about F?
It's extended Euclid algorithms. You should write it with bitsets and optimize until done.
I think I know solution with complexity
(uses sqrt-decomposition and Karatsuba algorithm, also can benefit from bit operations). It's highly unlikely that in Java O(n2) solution would pass, and I don't want to implement my idea, so it would be very nice if one of the contest authors could comment.
We had
in java working 0.8 on YandexContest
Did you have shift-and-xor as a single operation for that?
Anyway it'd nice to see the code.
http://pastebin.com/3ZCRK88W
Just submitted, and got accepted with running time 0.64 seconds using Oracle Java 8 compiler on Yandex.Contest.
thanks
Скиньте, пожалуйста, условия див1, я всё перерыл, но ничего не нашёл.
Ссылка.
Сдавать можно сюда. Там же есть и ссылка на задачи, кстати говоря.
I used segment tree for solving problem D. At first I stored the positions for every prime that is divisible by D. Then for every prime, I built segment tree each time and query the maximum index such that the condition is held: p[i] — p[j] + 1 <= 2 * (i — j + 1) Every time building a segment tree is enough efficient because it costs only n*(Log(n)^2) time.
Can anyone share their solution for problem G?