Dword's blog

By Dword, history, 3 months ago, In Russian,

Здравствуйте. Наверное, многие из вас, читая статью о декартовых деревьях на сайте emaxx, увидели описание "магической" операции union() — объединение двух декартовых деревьев. Там указано, что ее ассимптотика составляет O(Mlog(N / M)). Вопрос заключается в следующем: какую величину имеет константа M и откуда взялась такая ассимптотика операции?

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

By Dword, history, 11 months ago, In Russian,

Здравствуйте. Хотел бы узнать решение следующей задачи. Дан массив a[0..N-1]. Нужно отвечать на запросы двух типов, желательно за O(log^2(N)) на запрос: 1) L R x — найти кол-во различных элементов отрезка массива a[L..R], меньше либо равных x. 2) i x — изменить элемент a[i] на x. Знаю, как находить кол-во различных элементов на отрезке за O(log^2(N)) на запрос. Думал над применением похожей идеи в данной задаче, но ничего нормального так и не придумал. Какие будут идеи?

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By Dword, history, 12 months ago, In Russian,

Здравствуйте, пользователи Codeforces. Решаю задачу 1051F. Мое решение упорно MLится на 11 тесте, хотя по моим подсчетам ML быть не должно. В чем дело? UPD. Тема закрыта, ошибка найдена.

Read more »

 
 
 
 
  • Vote: I like it
  • -18
  • Vote: I do not like it

By Dword, history, 13 months ago, In Russian,

Приветствую всех. Хотел бы узнать, как решить одну задачу (уже не помню откуда). Дан неориентированный 0-1 граф с n вершинами и m ребрами и число k. Необходимо найти остовное дерево с суммарным весом ровно k (или сообщить, что такого не существует). Ограничения: 1 <= n, k <= 10^5, 1 <= m <= 2 * 10^5. Время 2 сек, память 256 Мб. У кого какие идеи?

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By Dword, history, 13 months ago, In Russian,

Приветствую всех пользователей Codeforces. Возникла задача разделить один большой многочлен на другой. Решил использовать БПФ, но если при умножении многочленов все более-менее понятно, а именно перемножаются соответствующие значения ДПФ двух многочленов, то при делении возникают сложности, ведь значения ДПФ могут быть равны 0, а на 0 поделить, увы, не получится. Что же делать в такой ситуации? Буду также рад, если вы предложите какую-нибудь статью, которая разрешит мой вопрос (желательно на русском).

Read more »

 
 
 
 
  • Vote: I like it
  • +20
  • Vote: I do not like it