wilcot's blog

By wilcot, history, 2 months ago, In Russian,

Привет всем. Наверное каждый зарегистрированный на CodeForces хоть раз слышал о таком замечательном сайте, как e-maxx. Там можно получить довольно подробную информацию по алгоритмам и реализацию на C++ — для копипаста (что не совсем хорошо) или усвоения особенностей реализации алгоритма в неидеальном реальном мире.

Алгоритмов то много, но вот про Link-Cut Tree ничего небыло, а это очень интересная структура и довольно простая. На самом деле, разобраться с ней было не так то и просто с первой попытки, но со второй все стало на свои места. После этого захотелось посмотреть на примеры реализации, выбрать лучшие решения и реализовать самостоятельно. Но вот с примерами возникли проблемы — я не смог найти внятной реализации (может быть плохо искал?). После десятка переписываний кода и долгого дебага я получил довольно внятную структуру данных, которую можно использовать как замену HLD.

Я поддержал следующие операции (все работают за $$$O(\log n)$$$ амортизировано):

$$$link(x, y)$$$ — соединить вершину $$$x$$$ с вершиной $$$y$$$ (в случае, если вершина x не является корнем, дерево будет переподвешено).

$$$cut(x)$$$ — удалить ребро от вершины $$$x$$$ до родителя.

$$$distance(x, y)$$$ — найти расстояние между вершинами.

$$$depth(x)$$$ — найти глубину вершины $$$x$$$.

$$$lca(x, y)$$$ — найти LCA вершин $$$x$$$ и $$$y$$$.

$$$parent(x)$$$ — найти родителя вершины $$$x$$$.

$$$root(x)$$$ — найти корень дерева, где находится вершина x.

$$$path(x, y)$$$ — проверить наличие пути между вершинами x и y.

$$$evert(x)$$$ — переподвесить дерево за вершину $$$x$$$.

Следующие операции переподвешивают дерево за вершину $$$y$$$:

$$$query(x, y)$$$ — посчитать сумму значений в вершинах на пути от $$$x$$$ до $$$y$$$.

$$$update(x, y, v)$$$ — прибавить $$$v$$$ к каждой вершине на пути от $$$x$$$ до $$$y$$$.

Исходный код здесь.

На данный момент не гарантирую, что в данной реализации нет багов, если кто и найдет, то пожалуйста расскажите, как они воспроизводятся.

Хочется услышать критику со стороны сообщества (и о том, что я плохо искал или написал плохой код).

Read more »

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

By wilcot, history, 10 months ago, In Russian,

Не хотел создавать данный пост — надеялся, что кто-то другой сделает, но нет :) На этой неделе проходят областные олимпиады в Беларуси. Все как обычно, два тура по 4 задачи, 5 часов на их решение. Здесь предлагаю обсудить задачки, решения и так далее.

Первый тур

Условия задач, обзорный лист.

Задача 1. Олимп-Сити

Решение

Задача 2. Дружелюбные соседи

Решение

Задача 3. Поворот плиток

Решение

Задача 4. Садовник

Краткое условие
Решение

Решение на C++.

Второй тур

Условия задач, обзорный лист.

Задача 1. Доставка почты

Задача 2. Контрольная работа

Решение

Задача 3. Текстовый редактор

Задача 4. Послание инопланетянам

Решение

Read more »

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

By wilcot, history, 20 months ago, In Russian,

На этой неделе (26-30.03.2018) проходит республиканская олимпиада в г. Минске. Как обычно будет два тура, на которых будет предположительно по 4 задачи. К сожалению задачи будут, наверное, сильно сложными для меня, поэтому предлагаю обсудить решения в комментариях к этому посту. А можно обсудить не только задачи :)

Желаю удачи всем участвующим школьникам!

Read more »

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

By wilcot, history, 22 months ago, In Russian,

Привет всем. На этой неделе (8-12 января 2018 года) проходит областная олимпиада по информатике в Беларуси. Олимпиада проходит во всех областях (а их у нас всего шесть) в одно и то же время с одним и тем же набором задач. Здесь можно обсудить олимпиаду, ознакомиться с уловиями задач (надеюсь, что все участники олимпиады ознакомятся с условиями на самой олимпиаде) и, может быть, если я смогу решить, с решениями.

Всем участникам желаю удачи!

Read more »

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

By wilcot, history, 2 years ago, In English,

Very interesting contest.

But, how to solve task L, G and J?

Thanks in advance.

Read more »

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

By wilcot, history, 2 years ago, In English,

Very interesting contest.

But, how to solve task K, L and H?

Thanks in advance.

Read more »

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

By wilcot, 3 years ago, In Russian,

С 9 по 12 января 2017 года будет проходить областная олимпиада по информатике. Первый тур олимпиады состоится 10 января, второй — на следующий день. Постараюсь разместить здесь условия и решения задач как можно скорее, естественно не раньше начала самих туров :) В комментариях предлагаю обсудить задачи, поделиться идеями по поводу их решения, мыслями...

Всем участникам желаю удачи!

UPD. Первый тур завершен. Ниже можно почитать, как же получить полные баллы по задачам.

UPD2. Второй тур тоже завершен. Можно почитать разбор, кроме последней задачи — я ее не решал, да и решений можно придумать множество.

Read more »

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

By wilcot, history, 4 years ago, translation, In English,

Hello, Codeforces!

My name is Ivan Udovin, and I would like to say, that the Codeforces Round #344 will be held on Thursday (March 3, 2016 at 19:35). This is our first round, but it doesn’t mean that problems will be boring and not interesting. The problemsetters of this round are me (wilcot) and Ilya Kheifets (iliya785). Thanks a lot to Alex Vistyazh (netman) and unknown person (he don’t want to be added in the announcement) for testing our round. Also I’d like to thank Fedor Korobeynikov (Fedosik) for his awesome idea for task E.

We thank Gleb Evstropov (GlebsHP) for his help in preparing the contest, Maria Belova (Delinur) for translating the statements into English, and, of course, Codeforces team and Mike Mirzayanov for unique Codeforces and Polygon platforms.

This round consists of five problems. Main heroes of this round: Blake — the owner of the "Blake Technologies" company, and Chris — an employee of this company, and others.

Scoring distribution: 500, 1000, 1500, 2000, 2500.

Good luck, have fun.

PS. Editorial is ready.

PPS. Congratulations to the winners:

Div. 2:

  1. lovelive

  2. Lonely_Coder

  3. chychmek

  4. chrome

  5. _-_Sa1378_-_

Div. 1:

  1. Um_nik

  2. chffy

  3. natsugiri

  4. ershov.stanislav

  5. AndreiNet

Read more »

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