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

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

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

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

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

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

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

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

• Связанные списки, двусвязаные списки и lock-free версии
• B+ сбалансированное дерево, как мы помним они еще используются в файловой системе
• Двусвязаные списки отсортированные по приоритетам (их используют mutex локи)
• Красно-черные сбалансированные деревья используются очень много где
• Дерево интервалов (НЕ дерево отрезков как в e-maxx, а дерево интервалов, где в каждой вершине сбалансированного бинарного дерева лежит два числа: от и до)
• Radix tree (более знакомый нам как Бор)
• Куча с приоритетами используется в cgroups: ограничение ресурсов доступных процессу. Модная нынче контейнеризация (LXC использует cgroups, а модный Docker использует LXC), также не удивлюсь, если линуксовская версия runexe использует cgroups.
• Хэширование по Кнуту: раз и два
• Хэш-таблицы используются для inodes — структура хранящая мета-даныне о файлах на файловой системе
• Битовые массивы (прям как Си++шный bitarray)
• Бинарный поиск, бинарный поиск в B-дереве
• Поиск в глубину и ширину
• КМП и Бойер-Мур
• Сортировка слиянием иcпользуется для системы сборки мусора

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Problem Classifier
• Декартово Дерево
• DP
• Flow
• Gauss
• Хэширование -
• Need Some Nim Game Problem
• Bitmask Problem
• симплекс-метод
• Задача на префикс функцию
• Алгоритм Кнута-Морриса-Пратта
• дерево отрезков
• суффиксный массив
• Динамика по профилю
• Динамика по дереву
• префиксное дерево(бор)
• Подскажите задачи на лемму Бернсайда / теорему Пойа
• Meet-in-the-middle
• K-я порядковая статистика на отрезке
• Динамика на суффиксном дереве/суффиксном автомате
• DP with Bitmask
• Подскажите задачи на применение дерамиды

Интересное

• ios_base::sync_with_stdio(0)
• Форматированный вывод на Java
• Math.sqrt() vs Math.hypot() или как находить расстояния.
• Game Theory 1
• Game Theory 2
• О языках программирования и технических аспектах
• Джентельменский набор Java-программиста
• Установка размера стека в Java
• Командная работа — памятка для новичков.
• Hashing
• Что же читать?
• Техминимум
• Dynamic Programming Type
• Немного классики: динамика по подмножествам и маршруты в графах
• Не макс. поток мин. стоимости
• How many spanning trees?
• Полезные ссылки
• Basic Binary Indexed Tree (English version)
• A median problem — solution
• Число делителей числа N
• PCMS2 client
• XOR maximization- Codeforces
• Длинная арифметика
• Non-recursive Implementation of Range Queries and Modifications over Array
• Чекеры, testlib.h и просто по теме
• Теоретический минимум для программиста [Кросспост]
• Численные методы решения СЛАУ
• (Головоломка) Слияние массивов за O(N) времени и О(1) памяти
• Перемножение long long по модулю
• Архивы олимпиад и тренировок
• СНМ
• Код Укконена (теперь с картинками)
• Ускорить двоичный поиск на 60 процентов? Легко!
• Быстрое умножение многочленов при помощи преобразования Фурье — это просто
• Сумма Минковского
• Convex Hull Trick
• Функция Гранди
• Быстрое умножение с использованием целочисленного БПФ
• Обратная функция Эйлера
• Java vs AntiQuickSort
• Динамика по профилю
• Basic Graph Theory
• Segment Tree
• Как улучшить dsu?
• Библиотечка для отладочного вывода
• Nim (Algorithmic Game)
• Педагогика, или что вы об этом думаете?
• Cartesian tree
• 3 тонкости C++
• 4-я тонкость С++
• Нахождение всеx пар вершин, путь между которыми бесконечно малый по величине, за O(n*m)(добавлено по просьбе автора)
• Еще две задачи
• Сжатое дерево отрезков/Неявное дерево отрезков
• Операции с суфф.массивом
• phi(n) для первых n чисел
• suffix arrays

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

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

last update: 4078

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

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

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

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

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

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

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

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

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

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

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

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

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

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