Всем привет! Я вот тут решил немного поэкспериментировать с шаблонным метапрограммированием в С++. Начал с простого, а именно со старых добрых симпатичных узоров. В результате получилась следующая реализация.

Она даже быстро компилируется при N·M ≤ 30 и работает, например, при N = 5 и M = 100 (при больших никак, ибо максимальная глубина инстанцирования в GNU — 900). Она правильно считает, но у меня возникло несколько вопросов. Дело в том, что инстанцирование шаблона metaFor происходит для всех значений m, mask и cur_mask. Так вот этот самый cur_mask по сути просто счетчик цикла, не входящий в состояние динамики. Можно ли как-то убрать его из параметров шаблона, сохранив возможность итерирования с помощью него? Тогда можно было бы считать динамику при значительно больших N и M. Второй вопрос заключается в том, а можно ли как-то ускорить данную реализацию?

Всем привет! Не буду долгих предисловий тут писать, поэтому сразу к делу. Читая книгу Мейерса "Эффективное использование STL", я вдруг наткнулся на упоминание о наличии в некоторых версиях STL структуры данных rope. Если кратко, то эта структура данных позволяет быстро вырезать/вставлять куски массива в произвольные позиции, аналогично декартовому дереву по неявному ключу (с аналогичной сложностью — подробности смотрите в статье на вики). Она иногда используется для обработки сверхдлинных строк.

Как выяснилось, rope действительно реализована в некоторых версиях STL, например в SGI STL. Сразу замечу, что это наиболее полная документация по классу rope, которую мне удалось найти в сети. А теперь давайте разыщем rope в GNU C++. Поскольку кто-то ранее находил расширенную версию красно-черных деревьев в GNU, я подумал, почему бы и rope где-нибудь не заваляться. Для тестинга я взял вот эту задачу, в которой у меня уже была сдана дерамида по неявному ключу. После недолгого гугления получилось следующее решение:

#include <iostream>
#include <cstdio>
#include <ext/rope> //заголовочный файл с rope
using namespace std;
using namespace __gnu_cxx; //пространство имен, в котором находится класс rope и все, что с ним связано
int main()
{
    ios_base::sync_with_stdio(false);
    rope <int> v; //используем как самый обычный stl контейнер
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        v.push_back(i);
    int l, r;
    for(int i = 0; i < m; ++i)
    {
        cin >> l >> r;
        --l, --r;
        rope <int> cur = v.substr(l, r - l + 1);
        v.erase(l, r - l + 1);
        v.insert(v.mutable_begin(), cur);
    }
    for(rope <int>::iterator it = v.mutable_begin(); it != v.mutable_end(); ++it)
        cout << *it << " ";
    return 0;
}

Оно без всяких проблем зашло и уложилось в секунду, что в 2 раза медленнее варианта с рукописным декартовым деревом, но при этом с чуть более оптимальным расходом памяти. Полную документацию по всем методам можно найти по вышеприведенной ссылке на SGI STL. Судя по всему, в GNU полностью аналогичная реализация. Visual C++ как унылое го... не поддерживает rope.

Что касается применения, то есть несколько особенностей. Из документации SGI STL следует, что класс rope плохо дружит с изменениями отдельных элементов последовательности (поэтому методы begin() и end() возвращают const_iterator. Чтобы получить обычный итератор, необходимо вызывать mutable_begin() и mutable_end() соответственно.). Также нельзя просто взять и присвоить значение i-ому элементу последовательности (см. код ниже для подробностей). Но насколько это "плохо", я не знаю. По идее за классический логарифм от числа элементов. В то же время конкатенация (операция +=) вообще работает за O(1) (не считая затрат на создание объекта справа, конечно).

Особенности индексирования можно увидеть в этом коде: http://pastebin.com/U8rG1tfu. Поскольку разработчики очень не хотят, чтобы мы меняли отдельные элементы контейнера, оператор [ ] возвращает ссылку на константу, но специальный метод все же есть. Данный код работает столько же, сколько и предыдущий. И да, забыл упомянуть, что все итераторы RandomAccess, что не может не радовать.

Если кто захочет потестировать контейнер на более серьезных задачах, расскажите в комментариях. По моему ощущению, у нас теперь есть быстрый массив с логарифмическим временем выполнения всех операций и как обычно большой константой :)

UPD: сдал еще задачу. Здесь мало запросов, но последовательность подлиннее. Зашло тоже без проблем. Еще наткнулся на такую особенность, что erase может принимать только 1 индекс типа size_t (хотя метода с такой сигнатурой нет). И я не очень понимаю, что он делает в этом случае. Из-за этого можно случайно набажить, когда нужно удалять 1 элемент.

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

Как известно, на данный момент официальным стандартом С++ является ISO/IEC 14882:2011, или же, проще говоря, С++11. Поддерживается он не на всех серверах, но со временем, думаю, ситуация изменится. Codeforces, например, идет в ногу со временем. C++0x, доступный здесь, фактически ничем от С++11 не отличается, просто другое наименование ("рабочее" название в ходе работы над будущим стандартом на самом деле). По крайней мере, начиная с GCC 4.7, установленного здесь, это так. Сразу скажу, что я буду опираться на GCC, ибо в Visual C++ практически все новые фичи появляются только в 10 и, в основном, 11 версии, которые не шибко то распространены.

Тем не менее, если просмотреть многие посылки на КФ, то заметно, что мало кто пользуется нововведениями. Это вполне естественно, учитывая, что спортивное программирование — это, прежде всего, математика да алгоритмы. Знание языка же роли большой не играет. Имея циклы, массивы и if, можно решить любую олимпиадную задачу. Если, конечно, это не Python, ибо только Иисус поможет вам запихнуть задачу на нем в строгий TL. Однако же, хорошее знание языка может сэкономить кучу времени при написании решения (один из основных аргументов тех же питонщиков), да и в будущем пригодится.

Опираясь на свой достаточно богатый опыт участия в олимпиадах, я собрал здесь нововведения С++11, которые могут пригодиться в спортивном программировании, например, непосредственно здесь, на Codeforces. Нововведений этих очень много, но я постарался выбрать лишь то, что может быть интересно олимпиаднику, не более. Например, я не буду описывать следующее:
- Расширение механизма шаблонов. Variadic templates, например, и вытекающий из этого класс Tuple.
- Все, что касается ООП.
- Объединения, перечисления со строгой типизацией.
- "Умные" указатели.
- Определяемые пользователем строковые литералы.
- constexpr (хотя рекомендую все же почитать про это)
Ну и многое другое... Достаточно подробный список с краткими описаниями можно найти на википедии.
Помимо кратких характеристик, для новых структур данных я также провел замеры времени работы. Там, где это нужно, также приводятся ссылки на подробные описания. Мне было лень в примерах писать префикс std, но я думаю понятно, что он неявно подразумевается.

Всем привет. У меня появилось 2 вопроса, нагуглить которые эффективно я не смог, поэтому сюда напишу.
1. Может кто-нибудь дать ссылки на задачи на двумерное дерево отрезков?
2. Кто-нибудь может рассказать немного про квадродерево? Ну или хотя бы дать ссылки на толковые статьи, а то все, что я смог найти, так это описание в вики, да вот эта небольшая статейка. Суть я понял, но вот как именно строить все равно не очень понятно. Плюс нигде не могу найти внятной асимптотики. PavelKunyavskiy писал где-то, что работает за корень, на вики написано, что за log, а здесь вообще я не пойму, что значит "за O(N)".

Всем привет! Имея уже некоторый опыт в программировании (хоть и олимпиадном, но все же), я, пожалуй, так и не научился нормально работать с вещественными числами. И, думаю, не только я :) Поэтому в данном блоге мне бы хотелось увидеть, например, ссылки на полезные статьи, практические рекомендации от опытных участников, ну и тому подобное.

Например, как понять, когда стоит использовать eps, а когда он только мешает? Как оценивать собственно, какой надо использовать eps?

Также очень интересует, как обрабатывать вещественные числа в деревьях поиска (например, map или set ), хеш-таблицах (потому что домножение на степень 10 и приведение к long long с последующим вычислением хеш-функции не очень хорошо себя показывает) с заданной точностью. Как правильно сравнивать их при сортировке?

Когда на С++ следует использовать long double, а когда double? Ну и так далее... Прикольно бы было увидеть всякие хаки с вещественными типами (ну типа этого). Надеюсь, я не слишком многого прошу :)
UPD: Обсуждение, по-видимому, переехало сюда.

Предлагаю здесь обсудить задачи. Как правильно решать I?

Начал изучать, возникла пара вопросов. Сдал эту задачу, по времени не сильно отличается от декартова. Так ведь и должно быть? Или может у меня не очень эффективная реализация? Второй вопрос по неявному дереву. Операцию merge по-моему можно делать как в обычном дереве, а вот если в обычном дереве split выполняется через splay, то здесь так нельзя. Нужно ли его делать, как в декартовом? Не ухудшит ли это время работы?
UPD: В неявном все как и в обычном, с этим разобрался, спасибо. Тогда другой вопрос. На вики написано, что эту жуть легко персистентной сделать. Может кто знает как?

Может кто-нибудь дать пару ссылок на online judge? В частности, на дерево отрезков. А то не могу найти нигде задачи на них.

У меня в кодблоксе при запуске Console Application в окошко, куда подается ввод, нельзя ничего вставить - можно ввести вручную, а вот из буфера обмена никак. Хочется это как-то исправить, так как неудобно каждый раз компилировать из терминала и запускать там. Может кто сталкивался с этой проблемой? Нашел в настройках параметр Terminal to launch console programs, и там установлено xterm -T \$TITLE -e (без \ разумеется - я его добавил, а то он текст не отображает)

UPD: Оказывается, нужно просто было нажать среднюю кнопку мыши :)

Огромная просьба ко всем участвующим в X Открытом Кубке Е.В. Панкратьева! Вернее к тем, кто уже зарегистрировался в этом году или участвовал в прошлом, но по каким-либо причинам не сможет участвовать сейчас. Дело в том, что очень хочется поучаствовать в данном кубке, а куратор нашего сектора даже о нем не знает. Если вдруг есть кто-то, подходящий под мое описание, слезно прошу написать в личные сообщения.

Решая задачу 38B столкнулся с неожиданной проблемой. Написал следующее решение: http://pastebin.com/bm1fR9Qw. Там в 29 строке взят в комментарий cout. Если убрать комментарий, то на тест: