Perlik's blog

By Perlik, 4 years ago, translation, In English,

Hello, guys! I decided to study template metaprogramming in C++, so I started with a simple task (it's a classic dynamic programming problem in Russia). And I got the following solution as a result.

It's compiled pretty fast if N·M ≤ 30 and works, for example, when N = 5 and M = 100 (but it can't be used to calculate answers for a bigger values, because the depth of instantiation doesn't exceed 900 in GNU C++). This solution works correctly, but I have several questions. As you can see, the template metaFor is instantiated for all values m, mask and cur_mask. But this argument cur_mask is just a simple loop counter. Is there any way to exclude it from arguments of the template without losing the ability to use it for iterating? If it could be done, this program would be able to calculate answers for much bigger N and M. And how can I speed up the above solution?

Read more »

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

By Perlik, 4 years ago, translation, In English,

Hello, guys! Recently I read the book "Effective STL" written by S. Meyers and found a mention about rope data structure, which is implemented in some STL's versions. Briefly speaking this data structure can fastly insert arbitrary blocks of array to any position and erase them. So it's very similar to implicit cartesian tree (you can find some details in the wiki article mentioned above). It's used sometimes to handle a very long strings.

As it turned out, the rope is actually implemented in some versions of STL, for example, in SGI STL, and I should say that it's the most complete documentation of this class I've ever seen. And now let's find the rope in GNU C++. I used this task for testing. Here you should quickly move the block [l,r] to the beginning of the array 105 times and besides the size of array is not greater than 105:

#include <iostream>
#include <cstdio>
#include <ext/rope> //header with rope
using namespace std;
using namespace __gnu_cxx; //namespace with rope and some additional stuff
int main()
{
    ios_base::sync_with_stdio(false);
    rope <int> v; //use as usual STL container
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        v.push_back(i); //initialization
    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;
}

It works perfectly, but 2 times slower than the handwritten implicit cartesian tree, but uses less memory. As far as I can see, GNU C++ has the same implementation of rope as SGI STL. Visual C++ doesn't support the rope class.

There are several points, that you should know about rope in C++. From SGI STL's documentation it's known that the rope doesn't cope well with modifications of single elements (that's why begin() and end() return const_iterator. If you want to use classic iterators, you should call mutable_begin() and mutable_end().). But my tests show that it's pretty fast (about ). Simultaneously operator += performes for O(1) (Of course, if we don't consider the time needed to construct the object on the right side).

You can see some features with [ ] operator in the following code: http://pastebin.com/U8rG1tfu. Since developers want to maintain the rope in permanent state, the operator [ ] returns const reference, but there is a special method to overcome it. This solution works with the same speed. Futhermore, I forgot to mention that all iterators are RandomAccess.

If you test this container, please, tell about your experience in comments. In my opinion, we got a pretty fast array with complexity for all operations :)

Read more »

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

By Perlik, 4 years ago, In Russian,

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

Как известно, на данный момент официальным стандартом С++ является 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, но я думаю понятно, что он неявно подразумевается.

Read more »

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

By Perlik, 5 years ago, In Russian,

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

Read more »

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

By Perlik, 5 years ago, In Russian,

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

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

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

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

Read more »

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

By Perlik, 5 years ago, In Russian,

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

Read more »

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

By Perlik, 5 years ago, In Russian,

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

Read more »

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

By Perlik, 5 years ago, In Russian,

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

Read more »

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

By Perlik, 6 years ago, In Russian,
Всем привет. Погуглив по данной теме, нашел много советов, но решил спросить еще тут. Может кто-нибудь посоветовать парочку хороших книг по криптографии? Хотелось бы не простой сборник алгоритмов, а сочетание теоретической и прикладной частей.

Read more »

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

By Perlik, 6 years ago, In Russian,
На Beta Round 93 послал решение: вот. Вердикт виден, я лично не пойму.

Read more »

 
 
 
 
  • Vote: I like it  
  • -7
  • Vote: I do not like it  

By Perlik, 6 years ago, In Russian,

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

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

Read more »

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

By Perlik, 6 years ago, In Russian,

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

Read more »

 
 
 
 

By Perlik, 6 years ago, In Russian,
Кто-нибудь может подсказать, как реализовать rand на отрезке [l;r], где l,r приблизительно равны 10^200?

Read more »

 
 
 
 

By Perlik, 6 years ago, In Russian,
Вдохновившись этим постом, решил изучить LCA. За логарифм получилось быстро, но этим методом эту задачу не решишь. Алгоритм с препроцессингом O(N) и ответом на запрос за O(1) не понял, поэтому написал простую sparse table (то есть с препроцессингом за NlogN). Вот мой код, но он почему-то получает WA #3. Может я неправильно написал динамику? Уже и не знаю, что неправильно.

Read more »

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

By Perlik, 6 years ago, In Russian,
Всем привет. Столкнулся с проблемой и не знаю как решить. Загрузил генератор тестов во вкладке Files. Захожу в Tests, проверяю, он его успешно компилирует. После сохранения скрипта (пишу GenTest > {15-20}) во всех этих тестах появляется запись GenTest и стоит параметр Script, но как заставить его запустить этот генератор, чтобы он эти тесты сделал?

Read more »

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

By Perlik, 6 years ago, In Russian,

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

a1
b3
выдает:
0 0 1 2
0
Если же комментарий оставить, то вывод просто 44)  Почему с cout следующее после него условие выполняется, а без него нет?? Запускаю на codeblocks в ubuntu 9.10.

Read more »

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

By Perlik, 6 years ago, In Russian,
Планируется ли добавка Python 3 в список поддерживаемых языков? Опыт Neerc показывает, что сделать это по-видимому не так трудно. Я думаю многие участники будут этому рады, поскольку 3-я версия во многом удобнее, да и к тому не каждый знает все отличия между двумя версиями, и человеку, пишущему на 3-ем питоне немного неудобно каждый раз думать о совместимости.

Read more »

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

By Perlik, 6 years ago, In Russian,
Там такие есть? если есть, может кто-нибудь подсказать, какие именно?

Read more »

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

By Perlik, 7 years ago, In Russian,
Собственно недавно придумал решение, которое кажется мне правильным. Получаю WA на 39. Может ли это быть из-за неправильного алгоритма? Или же если решение прошло 38 тестов, то алгоритм верный, но есть ошибки в реализации?

Read more »