Задача K — WA 13 у кого нибудь кроме меня было ?

По D у нас была такая идея (сдать не получилось):

Рассмотрим простое число, на которое будет делиться НОД. Для каждого такого числа сохраним отсортированный список позиций, на которых находятся числа, которые делятся на это простое число. Суммарная длина таких списков будет , т.к. каждое число войдёт не более, чем в чисел. Далее Будем считать, что у нас есть массив из 1 (сохранённые позиции) и  - 1 (позиции, числа в которых не делятся на p. Нам нужно найти самый длинный подмассив с положительной суммой. Задача, кажется, известная. Мы пытались решить с помощью дерева фенвика...

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))

Что такое WA31 в Е?

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.

How to solve L?

Как решить H и G?

how to solve K, E, H, F ?(div2)

Кому-то удалось сдать K в div2? Мы постоянно получаем WA2, даже при попытке заслать правильное решение из div1 с поправкой на то, что корень всегда в вершине с номером 1.

Идея нашего решения: для каждого ребра посчитать количество запросов, которые через него проходят. Это можно сделать стандартным трюком с lca и динамикой по дереву. Потом суммируем количество запросов по всем ребрам и вычитаем самое тяжелое ребро выходящее из каждой вершины.

Расскажите пожалуйста, а зачем в интерактивной задаче создаются файлы input.txt, если они не работают? https://www.diffchecker.com/azmuvqut

Час дебажили буквально, потому что приходит WA1 и абсолютно непонятна причина.

В задаче "J" нечитал пояснения к примеру, так как он был понятен и непротиворечил условию задачи. Написал то чего просили в условии — незашло.

Есть способы бороться с тем, что перед каждой посылкой мы должны менять язык со Scala на плюсы? Раньше что-то мы с такой проблемой не сталкивались.

What about F?

Скиньте, пожалуйста, условия див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?