Today I want to introduce you some very very useful data structures.

In this lecture, we are trying to improve your data structures skills, stay with us and click on read more.

Привет, Codeforces!

12 января в 12.00 MSK пройдет очередной 285-й раунд Codeforces. Автором задач являюсь я(Савинов Евгений). Это мой первый раунд на Codeforces и, надеюсь, не последний.

Хочу поблагодарить Сергея Кияна(sokian) и Александра Голованова(Golovanov399) за помощь в подготовке и прорешивании задач, Макса Ахмедова(Zlobober) за неоценимую помощь в подготовке контеста, Алекса Фетисова(AlexFetisov) за прорешивание раунда, Марию Белову(Delinur) за перевод условий на английский язык и, конечно же, Михаила Мирзаянова(MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Кстати, сегодня(11 января) у Михаила Расиховича день рождения, давайте поздравим его с этим!

Раунд состоится в обоих дивизионах. Информация о разбалловке будет опубликована перед началом раунда.

UPD1: Будет использоваться динамическая разбалловка. Задачи расположены в порядке возрастания предполагаемой сложности.

UPD2: Разбор задач можно найти здесь.

Mapping a permutation to a number has attracted much social concern. In shortest-path problems, in case a node (or state) is a permutation, we should convert states to integers, in order to BFS or Dijkstra on new graph comfortably. Many coders have known using std::map or trie to do this work. However, both have certain disadvantages. My writing will introduce a new way to solve this problem.

It is hard to write both long and detailed blog. Therefore, you can comment anything which you didn't understand well. I will reply (or update this blog if it is necessary).

To understand the role of mapping a permutation to a number, consider problem POSLOZI from COCI. Our goal is to find the length of the shortest path from a permutation S to an other permutation T using allowed operations. A valid operation is swapping two elements in the permutation. We are given a list of pair (p, q) denote we can swap the element indexed p and the element indexed q. Any other swapping operations are not allowed. A possible strategy is to BFS simultaneously from both S and T.

.

Привет

Некоторое время назад я наткнулся на персистентные структуры данных и, в частности, на описание персистентной очереди на вики-конспектах ИТМО. Всё бы хорошо, только как-то сложновато: чтобы реализовать одну маленькую очередь используется пять (в другом варианте — шесть) стеков.

Кратно напомню историю проблемы, уложусь всего в четыре стека и заодно немного расскажу про персистентность вообще

I see lots of programmers write code like this one:

pair<int, int> p;
vector<int> v;
// ...
p = make_pair(3, 4);
v.push_back(4); v.push_back(5);

while you can just do this:

pair<int, int> p;
vector<int> v;
// ...
p = {3, 4};
v = {4, 5};

Здравствуй, 2015! Добрый день, Codeforces!

На календаре 2-е января, а значит оливье почти съедено. Итоги 2014-го года я как обычно подведу тезисно, без этого "коротенько, минут на сорок".

Честно говоря я почти опасался начинать подводить статистику 2014-го года, ведь в 2013-м году Codeforces показал настолько стремительный рост, что было бы неудивительно выглядеть бледненько на его фоне. Как бы не так! Я был приятно удивлен цифрам и отчетам!

Чуть ниже будет список основных событий и достижений Codeforces за прошедший год. Для вас это просто список, но обратите внимание — за каждым пунктом кроется напряженная многодневная работа команды Codeforces, авторов задач, организаторов контестов и турниров, помощь тестов и волонтеров. Ура! Мы вместе сделали всё это (а список неполный, много что просто опущено):

• разработан и открыт Codeforces API
• добавлены (и местами переработаны) все контесты Андрея andrewzta Станкевича
• режим работы Codeforces в виде iframe-виджета и поддержка задач-вопросов позволили помочь Google провести https://www.calltocode.ie/ для школьников Ирландии,
• почти 70 раундов для наших любимых пользователей
• почти 450 новых интересных задач подготовлены для раундов и соревнований на платформе Codeforces
• поддержаны новые языки программирования
• совместно с КРОК провели Coder-Strike 2014 (всех порвал Никита -imc- Уваров)

• провели незабываемый Первоапрельский контест 2014 от великолепной Марии Nickolas Михайловой
• совместно с жюри Russian Code Cup провели RCC 2014 Warmup, который открыл RCC для широкого круга пользователей Codeforces
• площадка Codeforces выступила пресс-партнером RCC, ACM-ICPC финала в Екатеринбурге, Яндекс.Алгоритма
• провели ZeptoLab Code Rush 2014 с клевыми задачами и Ом-Номами
• помогли замечательной компании RocketFuel провести Rockethon 2014 (конечно, у нас)
• на нашей площадке состоялся MemSQL Start[c]UP 2.0 с финалом в офисе MemSQL!
• провели 11 эпизодов второго сезона тренировок Codeforces
• совместно с жюри Bayan Contest провели Bayan Contest Warm Up
• обновили Полигон (http://polygon.codeforces.com/) внедрив бесконечное множество небольших улучшений
• поддержали разборы задач в Полигоне
• кэширование запросов к файловой системе в в Полигоне привело к заметному ускорению работы большинства страниц редактирования задачи
• вместе с GridDynamics провели пилотный GridGames (для студентов Саратова)
• побиты все рекорды: 6274 регистрации на предновогодний контест Good Bye 2014

В этот холодный январский день я шлю горячий привет команде и друзьям Codeforces: разработчикам, координаторам задач, авторам задач, тестерам раундов, неутомимым блогерам и всем вам — жадным до знаний участникам соревнований!

А вот и сравнение с прошлыми годами работы Codeforces. Наглядно. В картинках.

Как известно, C++ принимает, что программист всегда прав, и поэтому компиляторы C++ не вставляют в программу дополнительные проверки на, например, разыменование нулевого указателя или доступ вне границ массива. У этого есть хорошая сторона: программа на C++ выполняется максимально быстро, и плохая сторона: иногда мы проводим долгое время за отладкой, чтобы в конце найти какую-то глупую ошибку. Хотелось бы, чтобы компилятор подобные ошибки находил сам. И многие компиляторы это могут! В этом посте я расскажу о различных параметрах GCC, которые это делают. Эту тему ранее уже освещал zakharvoit в этой статье.

Все параметры, которые здесь будут приведены, надо добавлять к командной строке GCC. В различных IDE это можно сделать в настройках IDE или компилятора. Многие из параметров можно применять и с Clang (например, в Xcode). Для MSVC++, пожалуй, нет ничего лучше, чем Debug-режим и /W4.

В настройках профиля появился волшебный раздел. С Новым годом!

UPD: Новогодние праздники подходят к концу, магия рассеиваются. В эти праздники волшебной возможностью воспользовались 7482 раз. А вот статистика по цветам, в которые происходили превращения.

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

Хэндл можно сменить либо на совсем новый (ранее никем никогда не используемый), либо на тот, который у вас был когда-то ранее. И да, совсем скоро странички вида http://codeforces.com/profile/Alex_KPR будут автоматически редиректить со старого хэндла на новый. У нас все ходы записаны!

Касательно необдуманных хэндлов я всегда вспоминаю такую историю. Мне как-то написал пользователь с просьбой: "Прошу сменить мой хэндл с I_love_Valya на I_love_Sveta, так как Валю я больше не люблю..."

С новым годом!

Hey everbody.

Hello 2015 is a Div.1 + Div.2 contest that will be held in gym soon. As I said, there will be 2 divisions and in each divisions, users of that division can participate ( ( - ∞, 1699] and [1700, 9999]). So, anybody who participates in the wrong division will be out of competition (manually).

Duration is 3 hours and there will be 6 problems in each division. Last 4 problems of Div.2 will be same as first 4 problems of Div.1 . Problems are written by me (PrinceOfPersia) and tester's M.Mahdi.

The problems will be sorted according to the estimated order of difficulty according to my opinion but I strongly recommend you to read all of the problems.(sentence from matrix :D).

Problems are more Olympiad style than ACM. I hope you enjoy them.

It takes a while to prepare all problems. So, this contest is not in the gym contests list yet.

Oh, I almost forgot this : the main character of all problems will be my friend, De Prezer :)

UPD: Problems are designed for single participant (as mathlover said), so teams will participate out of competition too.

UPD2: It's in the gym contests list now.

UPD3: For making the contest more interesting, the winner of each division, gets a kiss ;)

UPD4: Round was delayed by 10 minutes for some technical reasons.

UPD5: Contest is over.

Congratulation to all winers specially sankear who solved all Div.1 problems.

Div.1 winners :

1.sankear

2.ikbal

3.kraskevich

4.tourist

5.dreamoon_love_AA

Div.2 winners :

1.cthbst

2.peterpan

3.que_roin

Now it's time to sankear and cthbst kiss each other ;)

See you in next rounds, good luck and have fun.

UPD6: Well, recently I'm a little busy and I'll just post some keywords and tags but maybe I'll write an editorial some time.

Div.2 A : Binary search, B : Partial sum

Div.1 A : Binary search, B : Dijkstra, C : DP,Two pointers,queue, D : 2-sat, E: Hash, Segment tree, F : Divide and Conquer.

UPD7: You can find the editorial here.