dalex's blog

By dalex, 3 weeks ago, translation, In English,

Please put to main page. So we won't see blogs like https://codeforces.com/blog/entry/70236 in the nearest future.

In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.

Hope you remember it and will never make such a stupid mistake!

Read more »

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

By dalex, 3 months ago, In Russian,

Некоторое время назад я подумал, почему бы не загрузить наши древние контесты в тренировки. Некоторые из них можно найти на сайте http://contest.uni-smr.ac.ru/ — их я трогать не стал — можно и там решать. Некоторые контесты оказались безвозвратно утеряны. Но вот три штуки удалось откопать на жестком диске Shlakoblock-а.

Shlakoblock является автором всех трех, во втором из них я, тогда еще сине-зеленый, ему помогал. Первый контест личный, второй и третий командные. Держите:

За качество, разумеется, не отвечаю. Как и в любых контестах сине-зеленых авторов, тут будут встречаться и некачественные условия (факт, хотя я немного их подфиксил), и слабые тесты (не факт, но я почти уверен), и бояны из учебника (еще какой факт, но для того времени было норм). Тем не менее, несколько прикольных задач там есть. А еще ввод-вывод файловый: input.txt/output.txt — мы тогда не умели настраивать тестирующую систему под stdin/stdout.

Уровень я поставил три звезды, но может, было более правильно поставить две. Все-таки это 2010-2011 годы, тогда никто еще ничего не умел. Можно заценить, насколько с того времени вырос уровень олимпиадников. По моей оценке, современные фиолетовые должны решать все.

Read more »

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

By dalex, 4 months ago, In Russian,

Всем привет.

Можете ли вы представить, что монитор (тот, который положение участников контеста, а не который надо разбивать после этого контеста) может быть вреден? На самом деле такое встречается нечасто, но в этом посте мы разберем два таких примера, а также попробуем предложить возможное решение этой проблемы. По идее, для MikeMirzayanov не должно быть проблемой реализовать эту фичу.

Итак, первый пример, 2015 год, четвертьфинал Южного региона в Саратове. Пруфы тут будут такие себе, так как контест куда-то исчез с CF. Вот тут этот контест был, когда я его писал: https://codeforces.com/contest/589 (можете глянуть 14-ую страницу моих посылок, там еще задачи были пошаффлены), вот анонс: https://codeforces.com/blog/entry/20989, а сейчас ссылки на задачи ведут в тренировку с id 102042, закрытую от всех. Непорядок! Тем не менее, постараюсь рассказать, что там было.

Официальные стендинги: http://neerc.ifmo.ru/archive/2015/southern/standings.html Мы видим на первом месте с 11 задачами команду Нижнего Новгорода, на голову сильнее остальных (так оно и было на самом деле). Но давайте себя поставим на место одной из команд, решивших 7 задач. Вопрос: на часах 3:00, два часа до конца. Какую задачу решать восьмой по счету?

Мы видим, что все команды, пытавшиеся сдать 8-ую задачу, пробовали сдать задачу I. Именно задачу I сдала восьмой по счету команда Нижнего Новгорода. Между тем, когда этот контест проводился на Codeforces через пару дней после четвертьфинала, почти все команды из фиолетовых-желтых участников решили 8+ задач, а восьмой они сдали задачу, которая в официальном мониторе обозначена как G. Кроме того, команды, решившие 9 задач, примерно поровну сдавали I и K из официального монитора (к примеру, мы тогда сдали 9 задач, и девятой сдали именно K). Пруфов, как я уже написал, не будет, так как контест куда-то удалили.

Ошибка всех команд с онсайта состояла в том, что они пытались следовать за командой, в составе которой были vepifanov и KAN. Для этих ребят сложность 8-10 задач была примерно одинаковая: примерно very easy. Но для более слабых участников это вовсе не так! Им не стоило копировать порядок задач, стоило подумать своей головой, а не смотреть в монитор. И тогда бы они обнаружили и то, что G халява, и то, что K не очень то уж и сложнее I.

В случае с четвертьфиналом Южного региона 2015 правда о сложности задач хотя бы вскрылась на зеркале, но вот второй пример меня полностью поразил. Это случилось совсем недавно, когда мы выложили контест, проводившийся в этом году в Самаре: https://codeforces.com/gym/102215, анонс: https://codeforces.com/blog/entry/67178 Результаты как онсайта, как зеркала, так и того, что в нем происходило потом, в виртуальных участиях, абсолютно неадекватны. Не в том плане, что слабые обгоняют сильных, а в плане порядка решения задач. Постараюсь не особо спойлерить.

В принципе, что на онсайте, что в зеркале происходило одного и то же. Итак, начинается контест, и желтые участники начинают решать задачи по порядку. Читают первую — сдают за 10-15 минут. Читают вторую — она еще легче, сдают за 5-10 минут. Читают третью — тоже легкая, тоже сдают. Читают четвертую — ну тут конечно кода побольше, но тоже легкая, сдают уже за 20 минут. И так далее.

А между тем зеленые видят монитор и недоумевают, а чего это контест какой сложный. Почему вторая по сложности задача какая сложная, на нее полчаса нужно! А на третью еще полчаса, а на четвертую целый час! Ответ прост: не нужно следовать за теми, кто намного сильнее тебя. Для желтых почти все задачи в этом контесте легкие, желтые решают их буквально с прочтения. Как минимум три задачи, сложность которых я оцениваю как very easy, остаются почти неоткрытыми до третьего/четвертого часа, где их обнаруживают желтые после того, как они решили намного более сложные задачи. А на онсайте одну из этих very easy задач вообще first-accept-нул участник, решивший ТОЛЬКО эту задачу.

Я думаю, если написать этот контест, сначала прочитав все задачи, а потом вообще не смотря в монитор, результат будет лучше, чем если бы вы использовали монитор по назначению. И точно не будет (цитата) туплю, чтобы мне на четвёртом часу таблица предложила [решить задачу уровня Div2B]. Если вы слабо-желтый и ниже, можете попробовать, а потом взглянуть на таблицу и, мягко говоря, удивиться.

Ну а теперь feature request. Нужно добавить два параметра в монитор — верхнюю и нижнюю границу рейтинга участников, показываемых в мониторе и внизу монитора (там, где говорят, сколько человек какую задачу решило). В принципе, можно только верхнюю. Например, я бы поставил себе верхнюю границу 2300 или 2400 и мне бы это отлично подошло — мне неважно, сколько там решил условный турист, это для меня не показатель. Турист может решить за 5 минут то, что я не решу за 5 часов. Намного более важно, какие задачи решают люди, равные и чуть более сильные по скиллу (ну а более слабые точно не помешают). Сделаем результаты более адекватными!

Read more »

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

By dalex, 5 months ago, translation, In English,
 
 
 
 
  • Vote: I like it
  • +170
  • Vote: I do not like it

By dalex, history, 7 months ago, In English,

Hi,

I was allowed to upload two contests from Petrozavodsk camps, Yandex Cups 2018 and 2019, into Codeforces Gyms:

These contests are mostly authored by Zlobober and ifsmirnov, with the help of some other people. Yandex Cup 2018 has more easier problems and less hard problems.

The 2018 one is also known as Grand Prix of Khamovniki (discussion on CF), the 2019 one was never published before.

Enjoy!

Read more »

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

By dalex, history, 7 months ago, In English,
 
 
 
 
  • Vote: I like it
  • +44
  • Vote: I do not like it

By dalex, 12 months ago, In English,

Hello!
I want to solve different contests to learn a new language (Kotlin), but I have a busy shedule (and cannot write regular contests in suitable time), so the only way for me is to train using virtual contests.
There is a great variety of contests on Codeforces (thanks to Mike!) and consequently it is not easy to decide which contests to solve.
I love random, but I have a better idea. Let's make the list of not anime-themed contests! But I need your help (in comments) to find them all...

Read more »

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

By dalex, 19 months ago, translation, In English,
 
 
 
 
  • Vote: I like it
  • +88
  • Vote: I do not like it

By dalex, 20 months ago, In English,

Qualification Round has ended, but no blog on Codeforces yet. What happened to my Codeforces?

Main page: https://hashcode.withgoogle.com/

Judge system: https://hashcodejudge.withgoogle.com/

Our points: 10 / 176877 / 15824126 / 11808094 / 21465945, total score 49275052, 55th place.

How did you solve all the subtasks? I'm most interested in C and D.

Read more »

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

By dalex, 2 years ago, translation, In English,

Some weeks ago I read a Quora answer by I_love_Tanya_Romanova (link). The 4th paragraph attracted me, here is it's short content:

There are jokes about these typical problem statements: “Little Rohit got an array as a birthday present”. I’m also not getting why these trashy statements should be writtten instead of formal model of the task. It is awesome to have fictional statement when it makes sense, or when it comes from real life; it is at least funny to have stuff like problems I mentioned above. And I know that some of the platforms I mentioned are requiring problems with fictional statements and say that formal models are bad. Well, OK, “Parents asked little Chandan to perform following operations…”. May I go to some other site and solve normal problems, please? That’s a matter of taste — but for me this kind of statements is something that makes strong negative impression, and I think I’m not the only one.

I also don't like statements where characters were added just because there were no characters originally. You read such statement and think: "Why do they added this Alice with her birthday present? It has nothing to do with the problem".

I think there must be some rules that authors should use when they write a problem statement:

  1. If the problem comes from real life or from some situation that may appear in real life / fiction book / computer game — use the original statement. Those who will solve this problem will be clearly understand what's going on.
  2. If the problem originally had the formal statement (e.g. you have an array and you have to answer some queries, you have an array and you have to find a subarray with maximal xor / and / or, and so on): use formal statement.
  3. Never introduce a setting if the problem originally had formal statement.

Read more »

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

By dalex, history, 2 years ago, In English,

I've just met a comment with a link to a problem statement. There was such text in the statement:

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help her find all possible reconstructions of Anatoly’s code.

Don't you see something weird here? I think it should be:

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help him find all possible reconstructions of Anatoly’s code.

or:

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help them find all possible reconstructions of Anatoly’s code.

I know that people either use the gender that is more common for a person, e.g. he for drivers and she for nurses, or just use they (my English teacher said they is correct). I've wandered across Wikipedia (here is one of the links: https://en.wikipedia.org/wiki/English_personal_pronouns#Use_of_he.2C_she_and_it), but haven't found anything about preferrable usage of female pronouns.

However, I've read really a lot of English statements, and everywhere the female pronouns are used! For children and professors, for drivers and miners, for rabbits and foxes, for everything and everyone. Why?

Read more »

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

By dalex, 3 years ago, translation, In English,

Hello everyone,

Some days ago there was an annual programming contest in Samara University, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Saturday, 8 April, at 9:30 MSK. Site clist.by says that there are no intersections with something important that day.

Second time in a row it is a personal contest. So we ask everyone to participate solo. It must be very interesting for yellow and lower guys, and, who knows, maybe for reds too. You can start virtual participation at any time.

And as usual,

Read more »

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

By dalex, 3 years ago, In Russian,

Я совсем чуть-чуть заинтересованное лицо, но вроде бы стоит поднять немного шума, так как поведение организаторов чемпионата Урала выглядит так, будто им на все плевать.

Собственно, дело в том, что примерно неделю на этой страничке: http://acm.urfu.ru/chu/2017/ была информация, что отбор пройдет на опенкапе 2 апреля, но недавно ее поменяли, и на самом деле он пройдет 26 марта. Никому не кажется, что переносить дату отбора на неделю назад за неделю до начала — это очень подлый и неприемлемый поступок? Видя одну дату, люди начинают планировать свои дела, а спустя некоторое время все планы рушатся. Давайте может на завтра тогда перенесем? Там как раз какой-то контест от сборов МФТИ намечается. Вроде норм, да?

Например, у нас возникло пересечение с нашим ежегодным контестом (2012, 2013, 2014, 2015, 2016). Дата 26 марта довольно долго была свободна, но потом появляется опенкап, а затем на этот опенкап ставят отбор на чемпионат Урала. Если у вас крупное мероприятие — просто анонсируйте его заранее, чтобы организаторы мелких мероприятий могли подогнать даты. На самом деле я не верю, что команда из Самары прошла бы этот отбор, но, кажется, такие коллизии могут возникать где угодно и у кого угодно, и они не ограничиваются олимпиадами по программированию.

Read more »

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

By dalex, 3 years ago, In Russian,

Всем привет.

Раунд скоро закончится, примерно через 1 час 30 минут после публикации этого поста. Стартовать вроде бы уже нельзя, если верить расписанию. Ну и конечно же, давайте обсуждать задачи здесь, бла-бла-бла, тому подобное.

Но мне больше интересно вот что: https://www.diffchecker.com/1154oPEl

Попробуйте угадать, какой из вердиктов на задачу X даст решение слева и справа.

Read more »

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

By dalex, 3 years ago, translation, In English,
 
 
 
 
  • Vote: I like it
  • +147
  • Vote: I do not like it

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

Hello everyone,

Some days ago we had an annual programming contest in Samara, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Sunday, 17 April, at 11:00 MSK. Site clist.by says that there are no intersections with something important that day.

Previously, it was a team contest, but this year we decided to make it personal. So we ask everyone to participate solo. This is how the results will be the most adequate.

And as usual,

Read more »

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

By dalex, history, 4 years ago, In Russian,

Всем привет.

Мне сегодня скинули вот такую ссылку: https://inclass.kaggle.com/c/dota-2-win-probability-prediction

В этом соревновании надо по первым 5 минутам лога игры определить вероятность победы Radiant (одной из команд). Я бы с удовольствием в этом поучаствовал, но, похоже, что это соревнование закрытое, ибо там выдается вот такое сообщение: This competition is private-entry. You can view but not participate.

Я никогда не был на Kaggle, но здесь наверняка есть люди, знакомые с Kaggle. Можете ли вы рассказать подробнее о подобных закрытых соревнованиях? Можно ли получить на них инвайт? Если да, можно ли участвовать командой и как правильно зарегаться?

UPD. Решение нашлось: надо зайти вот по этой ссылке: https://kaggle.com/join/coursera_ml_dota2_contest. После этого сообщение изменится на This competition is private-entry. You've been invited to participate.

Read more »

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

By dalex, 4 years ago, In Russian,

Всем нравятся тренировки без мониторов? А даже если и с мониторами, то с кривыми логами сабмитов, автоматически сгенерированными Codeforces?

Я наконец-то выложил давно написанную утилитку для конвертации лога сабмитов. Называется она Standings Converter. На данный момент поддерживается только чтение из Ejudge-формата и запись в Testsys-формат, потому что это то направление конвертации, что нам приходится использовать каждые полгода, чтобы добавить очередной самарский контест в тренировки Codeforces. Но вы можете добавлять свои Parser-ы и Outputter-ы :)

Q: Я сгенерировал лог Testsys с помощью этой утилиты, как теперь его добавить в тренировку?
A: Назвать этот файл contest.dat, зайти по FTP в папку нужной тренировки, скопировать contest.dat в папку sandbox, а потом нажать в интерфейсе тренировки кнопку Обновить соревнование.

Q: У меня не установлен Maven и я не использую Java!!!11111
A: Пиши свой парсер :) Maven не совсем обязателен, можно просто запускать класс Main.

Q: import org.w3c.dom.*;
A: На момент написания я ничего другого не умел. Переписывать заново лень.

Read more »

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

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

Hi all!

On September 13, a qualification contest for ACM ICPC was held in Samara SAU. We always put our contests to Codeforces Gyms, so this Saturday, November 14, 11.00 MSK everyone will be able to enjoy it.

The contest will be held at Codeforces Gyms, it will be unrated and will last for 5 hours. The problems were prepared by craus and Shlakoblock.

And here is the full list of our previous contests:

Read more »

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

By dalex, history, 4 years ago, In English,

What's going on here? This contest was held two years ago. Just look at its id: it is 100187. Someone has managed to change its start date (and also to make it invisible for everyone but the author, which is fixed now), but how is it possible? Any permission settings? What if I go and reschedule all the contests in the gym? What if I hide them all? It must be a bug, admins, look into it, please.

P.S. Don't participate if you remember the problems.

UPD. Looks like gym vandals continue their work:

Read more »

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

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

540A - Combination Lock

For every symbol we should determine how to rotate the disk. This can be done either by formula: min(abs(a[i] - b[i]), 10 - abs(a[i] - b[i])) or even by the two for cycles: in both directions.

540B - School Marks

First count the number of marks that are less than y. If there are more than such marks, we can't satisfy the second condition (about the median), and the answer is -1. Otherwise we can get exactly such number of y marks so that the total number of marks greater than or equal to y is at least (maybe it's already satisfied). This is the required action for satisfying the second condition.

Now, in order not to break the first condition, get the remaining marks as lower as possible — all ones — and check the sum of the marks. If it is greater than x, the answer is -1, otherwise the correct answer is found.

540C - Ice Cave

There are three cases here, though some of them can be merged.

  1. If the start and finish cells are equal, let's count the intact neighbours of this cell. If there is one, move there and instantly move back — the answer is YES. Otherwise it's NO.
  2. If the start and finish cells are neighbours, the solution depends on the type of the destination cell. If it's cracked, the answer is YES — we can just move there and fall down. Otherwise it must have at least one intact neighbour to get the positive answer — we can move to the finish cell, then to this intact neighbour, and then return to the finish cell.
  3. In the general case, check if the path from the start cell to the finish cell exists. If it doesn't, the answer is NO. Otherwise check the type of the destination cell. If it's cracked, it must have at least one intact neighbour, and if it's intact, it must have two intact neighbours.

540D - Bad Luck Island (my code: http://pastebin.com/3s6dRK3A)

Let's count the values dp[r][s][p] — the probability of the situation when r rocks, s scissors and p papers are alive. The initial probability is 1, and in order to calculate the others we should perform the transitions.

Imagine we have r rocks, s scissors and p papers. Let's find the probability of the rock killing scissors (the other probabilities are calculated in the same way). The total number of the possible pairs where one species kills the other one is rs + rp + sp, and the number of possible pairs (rock, scissors) is rs. As all meetings are equiprobable, the probability we want to find is . This is the probability with which we go the the state dp[r][s — 1][p], with the number of scissors less by one.

In the end, for example, to get the probability of the event that the rocks are alive, we should sum all values dp[i][0][0] for i from 1 to r (the same goes to the other species).

540E - Infinite Inversions (my code: http://pastebin.com/QFEMRbNP)

At first find the position of each element which is used in swap (using map). Now let's find the answer. It consists of the two parts. First part is the number of inversions formed by only whose elements which took part in the swaps. They can be counted by one of the standard ways: mergesort or Fenwick tree. The second part is the number of inversions formed by pairs of elements where one element has been swapped even once, and the other element stayed at his position. Let's consider the following test:

2
2 6
4 8

The global sequence will look as follows: [1 6 3 8 5 2 7 4 9 ...], and here is the array of swapped elements: [6 8 2 4].

Let's understand with which numbers the number 8 forms the inversions. The only elements that could do that are the elements between the initial position of the number 8 (where the number 4 is now) and its current position: [5 2 7]. There are two numbers on this segment which didn't take part in swaps: 5 and 7. The number 2 should not be counted as it took part in the swaps and we have already counted it in the first part of the solution.

So we should take the count of numbers between 8's indices in the global sequence (8 - 4 - 1 = 3) and subtract the count of numbers between its indices in the swaps array (4 - 2 - 1 = 1). We'll get the number of inversions formed by the element 8 and the elements which haven't moved at all, it's 2. Counting this value for all elements which have been swapped at least once, we get the second part of the answer. All operations in the second part of the solution can be performed using sorts and binary searches.

Read more »

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

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

Hi all,

I was honored to open the fourth hundred of Codeforces Rounds. Unfornunately, neither I nor my friends couldn't invent any hard problems, so it's only a Div. 2 Round. But we'll definitely prepare a full round in the future! As always, I thank Zlobober for his help in preparing the problems, Delinur for English translations and MikeMirzayanov for the Codeforces itself.

The problems must be pretty easy for Div. 1 guys, so let's start a challenge: reds should solve everything in 30 minutes, yellows — in 1 hour, and violets — in 1 hour and a half. How many people will be able to make a success?

The score distribution will be standard. Wish you accepted solutions and successful hacks!

UPD 1. Congratulations to the winners in Div. 2:

  1. PauGra
  2. 233333333
  3. tgehr

and in Div. 1:

  1. niyaznigmatul
  2. I_love_Tanya_Romanova
  3. dreamoon

UPD 2. This is the editorial: /blog/entry/17643.

Read more »

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

By dalex, 5 years ago, translation, In English,

Hello guys,

I'm going to tell you about one of the negative aspects of Java on programming contests (actually, not only on contests), or, more precisely, how I have tried to resolve it. As you may know, Java has the disadvantage related to its collections library: the constraints of this language make you use object types even when using primitive types should be enough. Compare ArrayList<Integer> and vector<int>: Java list stores objects of type Integer, which are created every time when you add an element into the list (it's called boxing / unboxing), whereas C++ vector just stores ints. This behaviour slows down Java programs, and many people don't like it.

All this shit comes from the language design: you can't simply write a primitive type inside the angular brackets in Java. Some months ago I was thinking about this problem and came to the solution: why not just write my own collections library, with primitive types? Moreover, I haven't found any library with really all collections in the Internet.

That's how my small project EZ Collections (Github repository) was born. Of course, I haven't written all possible collections for all possible datatypes. Instead of that I have written each collection only once, leaving some hints for Maven plugin to generate everything as needed.

I have to say that this library is designed to use on programming contests or private purposes. It's thread-unsafe, it has some missing validations, it's prohibited to modify the collection during the iteration, it doesn't support serialization and maybe something else. But the problems on the contests can be solved without any troubles.

To use this library, you need:

  1. Install Git and download the repository using git clone command (the URL is specified on the main page of the project). Or you can just download it using Download ZIP button.

  2. Download Maven (link to the download page), install and configure it (if you don't know anything about it — use Google, but, as far as I remember, it's enough just to set the path to Maven in the system variables).

  3. Enter the root directory of the library and execute command mvn clean install. After that two jar files will appear in your local Maven repository, and also in the target folder. One of these jars contains class files, and the other one — source files. Now you can use them in your Java project.

But it's still unclear how to use it on contests. You need Egor's plugin CHelper for IntelliJ IDEA. After it had moved to Github, it became possible to merge the pull request that fixes some problems. The last pre-built version (commit 29dc20b), which includes my pull request, can be downloaded from here and installed in IDEA on your own.

After plugin update you can include the library into your contest project, specifying the path to the jar file with sources. That's all!

This is the example: let's solve the problem 118E - Bertown roads

  • use List<Integer>[] for storing the graph: 8293080 — 1060 ms, 39100 KB
  • use EzIntList[] for storing the graph: 8293086 — 654 ms, 12148 KB

(this problem has quite large input, the larger it is, the more performance you gain)

One more example: solve the problem Timus 1521

With the TreeList's help the solution takes only a few lines:

int n = in.readInt();
int k = in.readInt();
EzIntList a = new EzIntTreeList(n);
for (int i = 0; i < n; i++) {
    a.add(i);
}
int idx = 0;
for (int i = 0; i < n; i++) {
    idx = (idx + k - 1) % a.size();
    out.print(a.removeAt(idx) + 1);
    out.print(' ');
}

What do we get using EZ Collections? For now, the following data structures are implemented:

  • ArrayList
  • ArrayDeque (with the possibility to get the element by its index)
  • Heap
  • Sort (guaranteed NlogN implementation)
  • HashSet
  • HashMap (I've used open addressing approach. I'm quite sure that it's not hackable)
  • TreeSet
  • TreeMap
  • TreeList (the array that can perform add, set, insert and removeAt operations in logN time)
  • Pair classes

Also I have to mention that there is famous Trove library (its repository can be found here) which has the similar idea, maybe some of you use it at work, but the problem is that only ArrayList, HashSet and HashMap are implemented in Trove. It's not enough for programming contests.

Some notes and plans:

  • NaN, POSITIVE_INFINITY and other similar stuff is not supported. You know who you are, if you use such things.

  • As it's impossible to return null (because EZ Collections store primitive types), method returnedNull() is added in every class where it's necessary. You must call it to perform null-check immediately after calling the method which could have returned null in usual Java Collections. For instance, these code fragments are identical:

    TreeSet<Integer> set = new TreeSet<Integer>();
    Integer lower = set.lower(42);
    if (lower == null) {
        ...
    }

    EzIntTreeSet set = new EzIntTreeSet();
    int lower = set.lower(42);
    if (set.returnedNull()) {
        // don't use the lower variable, it's not guaranteed that it has some certain value
    }
  • The current source generation mechanism is ugly and doesn't support some cases that I want to support, so I'm planning to rewrite it. But all collections I wanted to implement in the first version already work.

  • boolean is considered to be uncomparable type, so Pairs with booleans don't implement Comparable. It will be fixed after rewriting the source generation.

  • Next collections I want to implement are LinkedList (on arrays). But it's only when I rewrite the source generation.

  • The next planned thing is to implement maps which have primitive key and object value types, or vice versa. It also should speedup programs a bit.

Please write any suggestions and feedbacks using the private messages on Codeforces.

Version history:

  • Feb 21, 2015 — version 0.1.0 is released. It contains the identical content comparing to standard Java collections library.
  • Mar 15, 2015 — version 0.1.1 is released. TreeList was added. Also the possibility to specify custom hash functions for HashSet/HashMap was added.

Read more »

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

By dalex, 5 years ago, translation, In English,
 
 
 
 
  • Vote: I like it
  • +104
  • Vote: I do not like it

By dalex, 5 years ago, In Russian,

Добрый вечер. Столкнулся с задачей, никак не могу решить. Выдает Wrong Answer на 2 тесте. Перепроверил код уже тысячу раз, не знаю, где ошибка.

Вкратце условие: надо поддерживать множество чисел и выводить его размер после каждой операции.
В первой строке задано число n (1 ≤ n ≤ 100000) — количество операций. В n следующих строках заданы операция (add или remove) и число (от  - 109 до 109), через пробел. Если операция — add, надо добавить число в множество, если remove — удалить его оттуда.

Код: http://paste.ubuntu.com/7857687/

Read more »

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