Блог пользователя imslavko

Автор imslavko, 11 лет назад, По-русски

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

Автор imslavko, 11 лет назад, По-русски

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

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

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

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

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +53
  • Проголосовать: не нравится

Автор imslavko, 11 лет назад, перевод, По-русски

Ссылка на новость ТехКранча.

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

А что вы думаете?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +85
  • Проголосовать: не нравится

Автор imslavko, 11 лет назад, По-русски

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

Задача: 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мб.

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится

Автор imslavko, 12 лет назад, По-русски

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

Автор imslavko, 12 лет назад, перевод, По-русски

Всем привет, недавно я нашел эту ссылку: http://62.183.105.236:30080 .

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

Также хочется спросить, кто владелец сайта? Судя по сайту, он говорит по-русски.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +53
  • Проголосовать: не нравится

Автор imslavko, 13 лет назад, По-русски

На сайте есть много полезного и/или интересного обсуждения. Вчера ночью я потратил 4 часа и пол гига трафика на то, чтобы просмотреть все 3900 записей и выделить те, которые мне показались интересными.

Тут две основные категории: "подкиньте мне задач на тему Х", "интересная техническая информация или обсуждение алгоритма", также во вторую категорию входят туториалы и другие обучающие материалы.

Чего нет? Нет "Hello world!"ов, "помогите решить задачу", анонсов соревнований и их разборы с обсуждениями. Нет CHelper и других утилит, парсеров условий. Естественно нет тем "Спортивное программирование и Х" и прочего флуда. Стихов и песен тоже нет.

Дайте задачу на ...

Интересное

Я судил о содержании темы по названию, то есть я запустил скрипт for((i=1;i<3921;i++)); do wget codeforces/blog/entry/$i done и парсил заголовок. Поэтому некоторые топики могут остаться не замеченными.

Если надо, можно выложить это, как страницу html, чтобы импортировать в закладки браузера.

last update: 4078

Полный текст и комментарии »

  • Проголосовать: нравится
  • +132
  • Проголосовать: не нравится

Автор imslavko, 13 лет назад, По-русски

Странно, что еще нет этой темы, ведь соревнование уже почти началось.

Надеюсь вы не забыли и уже готовитесь его написать. Удачи.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

Автор imslavko, 13 лет назад, По-русски

Здравствуйте! Когда-то была тема, где добрые посетители сайты кидали много ссылок на задачи, которые можно решить данным методом. Но автор скрыл тему в черновики и уже больше 2 месяцев не отвечает на личные сообщения. Может ли кто-нибудь накидать ссылок на любые задачи, которые решаются как СЛАУ?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

Автор imslavko, 13 лет назад, По-русски

Здавствуйте! Все знают, что |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]

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

Автор imslavko, 13 лет назад, перевод, По-русски

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

Контест доступен с 3 по 6 Февраля 2012 года. Участие открытое, 3 дивизиона. 3 задачи на 3 часа.

На сайте написано, что результаты будут 12 февраля, всем удачи!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

Автор imslavko, 13 лет назад, По-русски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится