Recently I returned from the Workshop and wanna share my impressions.

The post will be divided into several parts depending on an aspect I am covering in it.

Несколько недель назад на просторах блогов CF было очередное обсуждение на тему "почему так долго не обновляют рейтинг!?!?". В своем ответе MikeMirzayanov назвал несколько причин: 1. читеров проверяют руками; 2. раунды, как правило, проводятся вечером и Майку нужно потратить какое-то время, чтобы добраться домой; 3. иногда его маленькая дочь просит поиграть с ней и Майк, конечно же, не может отказать.

После того, как 1k_trash, Maxim и я узнали о третьей причине, мы начали думать, что можно с этим сделать. Немного подумав, к нам в голову пришло решение, которе делают счастливыми и участников, и дочь Майка. Решение заключалось в создании браузерного расширения, которое пересчитывает рейтинг в любой момент соревнования, когда вы обновляете страницу. Как-то так:

К счастью, CodeForces дал нам все карты в руки: API и детальная реализация метода пересчета рейтинга.

Раньше мы практически ничего такого не делали, но нам очень хотелось сделать что-то для CodeForces. В конце концов, мы не пожалели и получили много фана в процессе создания расширения. Сначала нам не удалось заставить расширение работать для больших контестов, вроде див2 и общих раундов. API не мог обслуживать тяжелые реквесты относительно начального рейтинга участников. В итоге, нам пришлось свичнуть все на бэкграунд при запуске браузера. Другими словами, при запуске мы выкачиваем начальные рейтинги всех юзеров, чтобы не делать это при каждом обновлении страницы.
Когда мы закончили с этим, было ясно две вещи:

• на 5к участников наше расширение работало около 30 секунд. Да, мы писали его на JS :)
• рейтинги были посчитаны неправильно!
  

К счастью, мы могли сравнить нашу реализацию с реализацией Майка чуть ли не по буквам. Проблема была в типах: официальное решение юзает int, а мы...var :). parseInt почти везде решил проблему, вот и хорошо :)
К этому моменту у нас был правильно работающий пересчет, но он был очень медленным. Наша команда немного приуныла, поскольку мы были уверены, что CF юзает самое быстрое возможное решение, и что у нас нету шансов как-то ускорить процесс. Однако, немного подумав, мы увидели, что "int везде" дает нам возможность сделать некоторую меморизацию. В итоге у нас было решение за O(min(N * K), N² * log(N)), где N — количество участников раунда, а K — количество разных целых значений рейтинга. В текущих реалиях, K лежит в районе 3-4k, таким образом решение ускорилось раз в 20! В конце концов, мы закончили некоторые мелкие детали и выкатили расширение в хром стор.

Установить расширение

Everybody is welcome to contribute to our Github repository.
Hope you love it!

UPD

Thank you all guys for your feedback. After the extensions attracted so much attention we have no choice but to do our best in order to make it better. We will make a lot of changes this week: fix bugs you reported, add requested features, switch to backend in order to decrease pressure on CF servers during the contest.
A special shoutout goes to people, who contributed to our repository. We are very grateful and will look at every pool request these days.
A big thanks to Mike Mirzayanov for being friendly, ready to collaborate and giving few pieces of advice.

Всем привет!

Этот пост не несет в себе особой смысловой нагрузки. Просто скажите, понимаете ли вы условие этой задачи? Если да, то после какого по счету прочтения оно стало понятным?

UPD

Понял задачу после коммента про вес корзин. Действительно, зачем автору упоминать про вес корзин в условии, ведь это так естественно...приблизительно так же, как и корзина нулевого веса в сэмпле.

CodeChef invites you to participate in the December Cook-off 2014.
Time: 21st December 2014 (2130 hrs) to 22nd December 2014 (0000 hrs). (IST — +5:30 GMT) — Check your timezone.

Details

Registration: Just need to have a CodeChef user id to participate.

New users can register here.

Problem Setter: Rubanenko

Problem Tester: ddldyj237

Russian Translators: vadimmm & Rubanenko

Editorialist: fchirica

Mandarin Translator: MinakoKojima

It's my third CodeChef Cook-Off. The contest is quite balanced and I think that this contest will bring you something new and unusual. Don't be afraid of being creative! As always I'd love to hear from you after the competition is over.

Special thanks go vadimmm for discussing the problemset.

Don't forget that top ten contestants will receive CodeChef T-shirts!

UPD

Contest has started with some lagging and delays. I'm sorry for that and, unfortunately I could do nothing with it.

Strongest active ACM ICPC Belarus competitor kostya_by takes the lead! uwi has two penalty submissions in margin.

uwi submits the last problem from the first try and wins the contest!

dreamoon_love_AA seemed to be trying to do the same as he does on codefoces these days, but the problems were too easy, so he didn't succeed and accidentally solved all of them. Congratulations!

By the way, it seems that I forgot to say that you should be not only creative, but attentive as well..:)

I'm sorry that the problemset was too easy for some contestants. Problem RRPLAYER turned out to be known and easy. As you will see from the editorials, I had more complicated(and I thought cool) solution. I'm really sorry and probably won't set public contests in future :(

Hey guys! December Clash at HackerEarth is taking place this Saturday. The contest lasts for twelve(!) hours, so almost everyone can find a time slot to participate.

There are five tasks, four of them are standard algorithmic problems with partial solutions allowed, while the last one is an approximation problem which will allow to determine the best participant.

I think that this format of competition is interesting for everybody because newcomers can do better than stronger competitors with a help of "12-hours dedication" strategy, while the strongest guys will enjoy fighting each other on the approximation problem.

The complete problemset is prepared by laoriu. It was very exciting to work over the contest with him. You may know this guy from preparing the Codeforces Round 277 (Div. 2). I did the testing part for this contest and would like to say that I wouldn't be able to solve all the problems without laoriu's help. So I find the problemset pretty challenging and strongly recommend you to participate! I believe that both math_lovers and implementation_lovers will find something interesting for them.

Hope to see you at the scoreboard ;)

Rubanenko

Marathon24 is starting soon. I simply wonder whether there is someone else who have just waken up because of the bug in clist.by schedule. According to it the contest was to start at 3:00 AM. Yeah, it seemed strange, because Poland is almost in the same timezone as me, but I thought that they simply wanted to please Japanese guys which always have to get up at night to compete. The most impressive part was telling one of my teammates that he had to ride back home, and come in the morning instead. I am not sure he will :D

I might be wrong, but it seems I have seen the same starting time somewhere at the Marathon24 website.

Hey guys,

I can't log in arena for last three days. Does everyone else have the same problem?

I've implemented a solution for the last contest's problem D which works correct but dramatically slow! It works more than ten minutes on my PC which seems to be quite slower than naive approach. I divide the data into blocks, and store cnt[] array in every block and a deque for maintaining update queries. I cut blocks sometimes, so I rebuild structure when the number of blocks is above 2 * initialNumberOfBlocks. Probably the problem is that I'm a Java noob, who knows :D

If you have a couple of minutes, please have a look at my code. I tried to make it readable... hope it is :)

Thanks!

UPD

After I fixed the but mentalist found, the program got ML. It's also quite strange because I didn't rely on garbage collector and create no more than 400 Blocks. Each Block has int cnt[100000] inside, so total memory usage should not be more than something about 40 mb, but it exceeds 256 mb on practice. Code

It seems corresponding thread was not created by anybody else...

How to solve 1000?

CodeChef invites you to participate in the July Cook-off 2014.
Time: 20th July 2014 (2130 hrs) to 21st July 2014 (0000 hrs). (IST — +5:30 GMT) — Check your timezone.

Details

Registration: Just need to have a CodeChef user id to participate.

New users can register here.

Problem Setter: Rubanenko

Problem Tester: msh_shiplu

Russian Translator: Witalia

Editorialist: PraveenDhinwa

Mandarin Translator: gediiiiiii and MinakoKojima

It's my second CodeChef Cook-Off. I believe this round is more interesting than my first one and hope you'll enjoy it! I think almost every problem can be solved by almost everyone, so everybody has a chance to place in top ten and win a T-shirt from CodeChef.

Problem statements are dedicated to Ukrainian National Team at IOI — Scorpy, NegaTeeF, seland and Omelianenko. I had a pleasure to help them with preparing for the IOI and they invented a nice solution for one of the problems in this contest! I'd also like to thank vadimmm for discussing and sharing ideas about the problemset.

As you will see from the editorials, every problem has at most 50-60 lines neat solution. I'd love to hear from you about your impressions, especially your solutions for RRDAG and RRTREE. I also wonder whether there exists O(N²) solution for RRFRNDS. During the setting process I tried to invent such solution, but eventually ended up with O(N³) solution with constant optimization.

Сегодня прошел ежегодный открытый чемпионат Харькова. Очень хотелось бы узнать, какое решение проходило в задача G? Мои сокомандники клянутся, что написали божественную декартку, но она не проходила по времени. У кого-то вышло пихнуть ее?

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

В этот раз двое из участников (Furko & Rubanenko) уже имеют опыт участия в ioi, а двое участников присоединились лишь в этом году. Зато fedimser уже выигрывал золотую и серебряную медали на международной олимпиаде по астрономии, а Scorpy только закончил девятый класс, а значит с большой вероятностью к окончанию школы тоже будет иметь несколько международных наград.

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

На сегодня все, to be continued :)

Фото перед вылетом:

Прибыли в аэропорт в Дубае, встретили команду Македонии :) Через 2 часа следующий самолет. Скоро залью фото.

Первую ночь провели в отеле, фото из номера:

Фото со сборной Грузии в терминале в Дубае:

Дозаправились в Сингапуре, летим уже до конечной:)

Первую ночь провели в отеле, фото из номера:

Фото со сборной Мексики:

Бтв, всем реквестирующим обещаю фото со сборной России:)

Веселый получился тур. Уже на первом часу начала образовываться очередь длинной 10-15 минут. После 3 часа уже практически ничего не тестировалось. Задачу про картинки без фидбэка очень неинтересно писать, да и последние субтаски по вомбатам тоже, по-видимому нужно/можно было пропихивать. Лично я коряво написал проверку на одну компоненту в первой задаче, и это заходило на 65. Почти весь контест думал, что неправильная идея, ведь на 65 баллов — это решения для спецэффических графов. То есть в первых 4 группах не было тестов с одной компонентой >.<

На artclass периодически слал решения, за полчаса до конца узнал, что там все нули, так как забыл убрать дэбаг-аутпут в проге. За 5 минут до конца что-то послал, но уверенности у меня в этом решении немного.

Лично у меня нервы на пределе, как и у всех ребят, которые не успели нормально заслать арткласс до начала "веселья".

Кстати, в столовой тоже громадные очереди:)

Пара фоток с закрытия. А вообще, их очень много, так что через день-два отдельным постом все залью)

In less than half an hour the third Round 3 will begin. Top 25 participants will go to London to compete in Wordl Final. I wish everybody good luck and interesting problems.

Всем привет!

Меня интересуют два вопроса:

Первый: Как вы генерируете случайную перестановку? Я обычно беру перестановку 1,2,3..N, а потом О(N) раз свопаю рандомную пару. Насколько хорош этот метод и есть ли другие?

Второй вопрос: Как выбрать случайно подмножество размером К из N элементов за О(K)? Если за О(N), то можно ведь ответить на первый вопрос, а потом взять первые К элементов, да?:)

Сегодня в 16.00 по московскому времени пройдет вторая индивидуальная олимпиада на neerc. Правила, как я понимаю, будут абсолютно такие же как и в прошлый раз.

Всем желаю удачи!

Завтра, в 12.00 по Москве, начинается сезон мною очень любимых личных олимпиад на neerc.ifmo.ru/school! Не забудьте заново зарегистрироваться. Всем желаю удачи!

Разумеется, предлагаю после контеста здесь же обсудить задачи.

Как найти последнюю ненулевую цифру N! быстрее чем за О(N)?