imslavko's blog

By imslavko, 4 years ago, In Russian,

Как бы вы реализовали OrderedDict — упорядоченый словарь? Структура данных, которая бы поддерживала операции словаря (или хэш таблицы) над парами ключ-значение, но также хранила бы и поддерживала их упорядоченность?

  • получить значение по ключу
  • убрать из структуры по ключу
  • вставка в любое место новой пары (ключ-значение)
  • найти место пары по ключу

Мне начинает казаться, что такой структуры, которая бы все это поддерживала более-менее эффективно (не за линию) просто нет. Как вы думаете?

Read more »

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

By imslavko, 5 years ago, In Russian,

Очень долгое время я не мог понять: когда я буду писать алгоритмы и структуры в продакшн коде также, как я это делал на олимпиаде? Время шло, а ничего сложнее бинарного поиска и расстояния Левенштейна не нужно было (все работало и так быстро, а структуры и алгоритмы были бы в ущерб модулярности).

Конечно, очень часто нам не нужно думать об эффективных алгоритмах, когда всю тяжелую работу выполняют база данных, веб-сервер и операционная система. А твой код лишь рисует веб-странички или кнопочки в приложении на айфон.

Но именно в этих сложных системах (ОС, базы данных, веб-сервер, компиляторы, др) и используются все те основы, что мы с вами читаем с книжек типа CLRS.

Полный ответ об алгоритмах из книжек был дан на stackexchange и потом был репостнут в блогах и позже на HN. Сегодня я решил перевести ответ об ОС Линукс со своими комментариями (отсебятина) и ссылками на ресурсы на русском языке.

Так давайте поговорим об ОС Линукс, оказывается там можно встретить все, что учит любой школьник до 9 класса (а может и раньше):

Также советуется к прочтению оригинальный пост, там еще больше примеров с ссылками на статьи на английском языке.

И в добавку примеры использования динамического программирования: link

Read more »

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

By imslavko, 5 years ago, In English,

It just happened.

Although, acquisitions happen every day, this one is huge for Competitive Programming community. As you know, almost all acquired companies promise to keep the original direction and make things better with the support from parent company but often we can see they just get shut down.

What do you think?

Read more »

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

By imslavko, 5 years ago, In Russian,

Помогите, пожалуйста, с задачей.

Задача: http://www.e-olimp.com/problems/3206

Что я попробовал: отсортировал ребра по весу. Иду по очереди и поддерживаю компоненты связаности. На каждом ребре (a, b, c) я смотрю на компоненты. Если a и b в одинаковых компонентах, то это ребро нам ничего не улучшит и я его пропускаю. Иначе, соединяю компоненты.

Потом для каждого запроса я смотрю, когда в первый раз a и b попали в одну компоненту. Очевидно, что ребро, которое соединило их компоненты и является самым тяжелым в самом легком пути от a к b. Это ясно, если вспомнить, что ребра были отсортированны по возврастанию в начале.

Реализация: Чтобы смотреть назад во времени на компоненты связанности, я храню все в персистентной структуре, где каждая операция за O(log2N). А для каждого запроса нахожу ребро, которое соединило компоненты a и b с помощью бинарного поиска за O(logN).

Суммарно выходит O(Qlog3N), что не влезает в ТЛ. Да и моя корявая реализация персистентного СНМ — очень кривая и занимает очень много памяти и не влазит в МЛ 64мб.

Мой код: там вообще кошмар на улице вязов. Реализовал первое, что смог. Этот код прошел все мелкие тесты (что подтверждает корректность идеи?). Ссылка.

Помогите решить задачу? Помогите научиться правильно писать персистентный СНМ?

Read more »

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

By imslavko, 6 years ago, In Russian,

Где можно найти справку по полигону? Ссылка в самой системе битая. Помимо блогов codeforces где-нибудь еще можно найти обсуждение и информацию по системе?

Также еще несколько мелких вопросов:

  1. Когда генерятся условия, в примерах отсутствуют ответы. При этом есть и main-solution, и ответы на обычные тесты генерятся отлично. Как добиться того, чтобы и в условиях появились ответы?
  2. Есть ли способ импорта в полигон задачи из готового full-package созданного в формате polygon?
  3. Может есть место, где люди делятся простенькими задачами в формате полигона или другом формате пригодном для использования другими?

Read more »

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

By imslavko, 6 years ago, In English,

Hello there! Recently I found this link: http://62.183.105.236:30080 .

There are many contests uploaded like virtual contests. Thought, it would be helpful for those, who want to train these contests.

Also I want to ask, who is owner of this site? I guess he is Russian speaker.

Read more »

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

By imslavko, 6 years ago, translation, In English,

There are many intresting topics on CF! But it became very difficult to find really intresting things. Here are links to all such topics, I found after scanning all post ids.

There are two general categories: "Help me find problems on topic X" and "intresting technical information or algorithm".

There are no out-of-topic messages, such as "Hello world"s and other flood posts. Also there are no competition anounces and tutorials, but there is link to post, where you can find all tutorials of CF.

Give me problems to given topic

Интересное

Most of these topics have no english translation, so use google translate. Any suggetions are welcome

Read more »

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

By imslavko, 6 years ago, translation, In English,

This competition starts in several minutes.

I guess, you didn't forget about it and are ready to rock, good luck!

Read more »

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

By imslavko, 6 years ago, translation, In English,

Hello everyone! Can you give me links to Online Judges, where I can find problems to solve them with given method? Thanks in advance!

Read more »

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

By imslavko, 6 years ago, In Russian,

Здавствуйте! Все знают, что |MinCut| = |MaxFlow| в сети. Кто знаком с темой может прокрутить вниз, там вопрос.

[newbie mode] Как найти какие именно ребра являются разрезом? Тут вроде тоже все понятно, разделим множество вершин на два множества: S — множество достижимых вершин из истока по ненасыщенным ребрам и T = V / S. Ребра, которые соединяют вершины из разных множеств и будут одним из ответов.

Как найти вершинный разрез? Учили так: разделим каждую вершину v на 2 вершины: v1 для входящих и v2 для выходящих. Сделаем так же ребро v1 -  > v2 с пропускной способностью 1. Далее найдем макс.поток и размер потока будет равен минимальному вершинному разрезу. Но как теперь найти ответ?

В задаче на USACO trainings (telecow, 5.4.5) проходит такое решение для |V| ≤ 100, |E| ≤ 600:

Будем по очереди удалять ребро между v1 и v2 для каждой вершины и будем заного находить поток. Если поток уменьшился на единицу, то эта вершина входит в раздрез.

Мне не очень понравилось это решение, ведь делая это алгоритмом Диници, это будет работать не мало: O((|V||E|)2), где кол-во вершин увеличивается в 2 раза, а кол-во ребер примерно в 4 раза(обратные ребра и по 2 ребра на каждое, так как ребра не ориентированны), получается где-то 100 * 2 * 600 * 4 в квадрате итераций? Сначала я испугался такой цифры, но вспомнив, что ребра с пропускной способностью в единицу делают ее еще быстрее, то выходит помножиное на |V| вызовов, то выходит около 6 * 106, что приемлемо. [/newbie mode]

Но как находить вершинный разрез, когда вершин и ребер еще больше? Есть ли более оптимальное решение?

Read more »

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

By imslavko, 6 years ago, In English,

The USACO 2012 February contest is available February 3 through February 6.

Read more »

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

By imslavko, 7 years ago, In Russian,

Кто может поделиться решением задач F и H?

Read more »

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