Сегодня начался третий марафон-раунд TCO16 TerrainCrossing. Он продлится две недели, участники, занявшие первые 2 места, проходят в финал, топ-15 получают футболки, а участники первых двух раундов узнают наконец, кому достанутся два дополнительных места в финале (текущие лидеры). Я — автор задачи.

If you like Marathons but don't have two weeks to dedicate to participation in a typical match, consider taking a look at the match that will run for 28 hours right before the TCO16 NYC regional event. The coding phase will start on Thursday, June 16 at 8:00 a.m. EDT (in your time zone) and end on Friday, June 17 at Noon EDT (in your time zone). It will be a rated event featuring a somewhat easier than usual problem (I am the writer ;-)) and following the usual Marathon rules (apart from the shorter duration).

And if you happen to live in New York area, consider not only participating in the Marathon but stopping by at the TCO16 NYC regional event at the Google office afterwards: top participants of this match who will be present at the event will get prizes! Nothing as spectacular as a trip to TCO16 finals, I'm afraid, but I hear it's something quite special :-)

Everyone can participate in the match, but to get the prize you have to be present at the NYC regional event.

UPD: NYC Lightning Round ColorCapture is now live.

Сегодня начался второй марафон-раунд TCO16 StarTraveller. Он продлится две недели, участники, занявшие первые 2 места, проходят в финал, топ-15 получают футболки, а участники первого раунда продолжают соревноваться за два дополнительных места в финале! Идея и реализация — JacoCronje.

Во всех задачах, как и в примере, используется одинаковое определение глаголов для ввода-вывода данных:

print =: 1!:2&2
read =: 1!:1[3

Кроме того, скрипты завершаются командой exit ''.

640A - Ленивый блинорез

Как обычно, первая задача проверяет способность участника выполнять базовые арифметические действия языка. Даже в таком необычном языке, как J, арифметика выглядит довольно стандартно, за исключением того, что в отсутствие скобок операции выполняются справа налево, без приоритетов, и деление обозначается символом %.

Контест окончен; разбор задач доступен здесь.

Язык этого раунда — J.

Традиционная программа A+B (числа A и B записаны в одной строке и разделены пробелом) выглядит следущим образом:

print =: 1!:2&2
read =: 1!:1[3

in =. (read-.LF)-.CR
print +/ ". in

exit ''

Основной источник информации о языке — сайт http://code.jsoftware.com/wiki/Main_Page. Используется версия J804.

Сегодня начался первый марафон-раунд TCO16 CutTheRoots. Он продлится две недели, участники, занявшие первые 2 места, проходят в финал, а топ-15 получают футболки! Идея задачи моя, реализация — JacoCronje.

UPD: ТопКодер добавил еще два места в финале! Их получат люди, которые 1) не прошли в финал по основному критерию, 2) участвовали во всех трех отборочных раундах, и 3) имеют минимальную сумму мест, занятых в трех раундах.

В этом году 3 человека решили все задачи, что ровно на 3 больше, чем в 2014! А вот участников, решивших хотя бы одну задачу, было всего 1097.

656A - Da Vinci Powers

В этой задаче надо было определить последовательность целых чисел по двум примерам и названию задачи. Это оказалось неожиданно сложно, гораздо сложнее, чем мне казалось. Поиск по OEIS показывает, что хотя последовательностей, содержащих числа из примеров, довольно много, ровно одна из них имеет отношение к Леонардо да Винчи (а если сразу искать "Da Vinci", последовательностей находится всего две). http://oeis.org/A221180 — последовательность степеней двойки, вычисленная да Винчи с ошибкой и записанная в "Codex Madrid I".

656B - Scrambled

Одно слово: typoglycemia.

Контест окончен, надеюсь, вам понравилось :-) Разбор задач — здесь. До следующего года!

В пятницу 1 апреля состоится четвертый Первоапрельский контест — несерьезное соревнование, в котором решить задачу зачастую проще, чем догадаться, что же в ней надо сделать. В его подготовке мне помогал kit1980, а также команда Codeforces.

В этом раунде вас ждет 7 необычных задач, на решение которых дается два часа. Раунд будет проводиться по схеме ACM ICPC (без взломов, положение в результатах определяется количеством решенных задач и набранным штрафным временем) и будет нерейтинговым. Решения можно сдавать на любом языке, поддерживаемом Codeforces — если, конечно, иное не оговорено в условии задачи ;-) Чтобы получить представление о том, что вас ждет, можно взглянуть на контесты прошлых лет: 2012, 2013, 2014.

Как обычно, чувство юмора, совместимое с моим, является необходимым условием для успешного участия. Удачи!

ТопКодер опубликовал информацию об алгоритмической части TopCoder Open 2016. Несколько интересных моментов:

1. Футболки возвращаются! 120 футболок для участников раунда 3 в алгоритмах и по 10 — для топ-10 в каждом раунде марафонов.

2. 10 финалистов в алгоритмах и 6 — в марафонах.

3. Онлайн-раунды алгоритмов будут проходить в разные дни недели, а не только в выходные.

4. Региональные онсайты для алгоритмов остаются, но теперь они представляют собой отдельные соревнования. Из каждого регионального онсайта топ 10 участников попадает в вайлдкард, а оттуда 2 человека попадают в финал, минуя обычные онлайн-раунды.

Правила — алгоритмы

Правила — марафоны

Сегодня начался третий марафон-раунд TCO15 "PegJumping". Он продлится две недели, и это последний шанс попасть в финал. И снова я не автор задачи, а тестер :-)

Сегодня начался второй марафон-раунд TCO15 "PathDefense". Он продлится две недели, и участники, занявшие первые 4 места, проходят в финал. На этот раз я не автор задачи, а тестер :-)

Two papers by kit1980 and me:

• Declaratively solving tricky Google Code Jam problems with Prolog-based ECLiPSe CLP system, The 30th ACM/SIGAPP Symposium On Applied Computing (preprint: http://arxiv.org/abs/1412.2304)
• Declaratively solving Google Code Jam problems with Picat, Practical Aspects of Declarative Languages 2015 (preprint: http://arxiv.org/abs/1504.00977)

And for a lighter reading, Cognitive Biases in Competitive Programming :-)

Сегодня начался первый марафон-раунд TCO15 "SmallPolygons". Он продлится две недели, и участники, занявшие первые 4 места, проходят в финал. Я — автор задачи :-)

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

530A - Квадратное уравнение

Решение квадратного уравнения требовало использования библиотечной функции sqrt и конструкции if-then-else. Кроме того, эта задача должна была продемонстрировать, что в языке есть числа с плавающей точкой :-)

main =>
    A = read_real(), B = read_real(), C = read_real(),
    D = B * B - 4 * A * C,
    X1 = (-B - sqrt(D)) / (2 * A),
    X2 = (-B + sqrt(D)) / (2 * A),
    if D == 0 then
        println(X1)
    else
        printf("%w %w%n", min(X1, X2), max(X1, X2))
    end.

530B - Строка наизнанку

Задача на работу со строками: библиотечная функция slice позволяет получить подстроку заданной строки, reverse разворачивает ее, а ++ — оператор конкатенации.

Язык этого раунда — Picat, во многом похожий на Prolog. Мы постарались подобрать задачи так, чтобы большинство из них было удобно решать с использованием декларативного подхода.

Традиционная программа A+B (числа A и B разделены пробелом) выглядит следущим образом:

main =>
  A = read_int(),
  B = read_int(),
  C = A + B,
  println(C).

Основной источник информации о языке — сайт http://picat-lang.org/. Используется версия 0.9.

Marathon Match 86 "MovingNQueens" начинается сейчас и продолжается неделю, до следующего понедельника. В полном согласии с пожеланиями сообщества, в нем нет гигабайтов данных для анализа или ML-алгоритмов, зато есть призы для 4 победителей!

(Я — автор задачи. В этот блог просится фото в стиле Мориарти "Did you miss me?", но я не успела его сделать :-))

470A - Последовательность хрустального шара

Как обычно, первая задача проверяет способность участника выполнять базовые арифметические действия языка и решается даже проще, чем пример — без единого цикла.

^'0-
$ 1+*3*1+.

470B - Гексакосиойгексеконтагексафобия

В этой задаче используются уже более сложные структуры языка — цикл, условное выполнение и даже именованные переменные! Переменные удобно использовать в качестве счетчиков циклов и накопителей результата, чтобы не возиться со стековыми манипуляциями с той же целью.

Контест окончен. 13 человек решили все задачи — это потрясающе!

Разбор задач будет доступен здесь.

Язык сегодняшнего раунда — FALSE, стековый эзотерический язык программирования, придуманный больше 20 лет назад.

Традиционная программа A+B (числа A и B разделены пробелом) выглядит вот так.

Для тестирования своих программ можно:

• скачать исходный код на C авторского интерпретатора здесь. Проверяющая система использует именно этот интерпретатор с опцией -q.
• использовать вкладку "Запуск".
• использовать онлайн-интерпретаторы (отличаются от эталонного интерпретатора, но сильно упрощают отладку): 1, 2.

Полезные ссылки:

• описание языка от автора, Wouter van Oortmerssen
• статья в Прогопедии
• сборник программ в Rosetta Code

Замечания:

1. В описании языка фигурируют команды ø и ß. Авторский интерпретатор обозначает их символами O и B (оба онлайн-интерпретатора поддерживают их неизменными).
2. Конец файла кодируется как #-1, перевод строки — как #13#10.
3. При завершении работы программы стек должен быть пустым, иначе интерпретатор выведет ошибку в стандартный вывод, и это будет считаться неверным ответом.

13 сентября вас ждет Surprise Language Round #7, посвященный Дню программиста.

Правила проведения раунда:

• Соревнование будет нерейтинговым для всех участников.
• Индивидуальное соревнование по правилам ACM ICPC: положение в результатах определяется количеством решенных задач, при равном количестве — набранным штрафным временем. Изначально штрафное время участника равно 0, при каждой сданной задаче оно увеличивается на время, прошедшее с начала контеста, + 20 минут за каждую неудачную посылку до отправки правильного решения. Решение считается правильным, если оно прошло все тесты из предопределенного набора; правильно ли посланное решение, становится известно сразу. Взломов чужих решений нет.
• В раунде будет 8 задач, примерно отсортированных по сложности, и 2 часа на их решение.
• Решения задач принимаются только на одном языке, который будет объявлен в начале контеста. Язык существует давно, а не придуман нами специально для раунда.
• Пожалуйста, в начале контеста перечитайте этот пост целиком: в нем появится объявление языка, рекомендации по установке компилятора (в интерфейсе контеста будет доступен запуск программы онлайн) и полезные ссылки на документацию. В остальном изучение языка — дело рук самого участника. Для решения задач вы можете использовать любые ресурсы (но не совместное участие); ограничиваться документацией, приведенной в посте, не обязательно.

Я надеюсь, что выбранный мной язык будет незнаком большинству участников раунда.

Тема подготовки задач для контестов, конечно, не так популярна, как извечный вопрос "как стать красным за три месяца", но все-таки вызывает некоторый интерес публики. Я уже писала про особенности подготовки Surprise Language Round и про эмоциональный аспект авторства задач; пора поделиться суровыми фактами о подготовке самых обычных контестов.

Задачи

Сколько времени у вас уходит на то чтобы подготовить, выбрать, вспомнить или подыскать сами идеи задач — происходит ли это в течение дня-двух, или они постепенно рождаются недельку-месяц а потом вы начинаете думать "не применить ли их в контесте?"

Как вы оцениваете — какой опыт решения задач СП (в штуках? годах) требуется чтобы уверенно изобретать задачи самому — или же это не коррелирует и есть люди которые только придумывают, но не решают (хаха)?

Генерация идей — процесс долгий, практически непрерывный. Когда я придумывала задачи, я все время генерировала идеи из чего попало (о, белка побежала... хмм, а это идея! — честное слово, задача до сих пор лежит, сложная :-) ) и конспектировала их. Когда у меня было время и настроение написать контест, я перетряхивала эти конспекты в поисках задач, которые были бы 1) решаемы, и 2) симпатичны и достаточно нестандартны, и собирала из них сет.

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

Критерии удаления (должны выполняться одновременно):

• Автор поста — не в рейтинге.
• Автор поста — не в whitelist, состоящем из MikeMirzayanov и еще нескольких известных лиц с черными хэндлами.
• В прямом эфире есть два или больше постов от одного и того же автора. Обычный паттерн поведения здешних спамеров — опубликовать пять постов за раз и уйти навсегда. Ограничение на два поста сделано для того, чтобы оставить в прямом эфире одиночные посты честных нерейтинговых людей, если они знают меру в написании постов :-)

Собственно, вот сам скрипт: http://userscripts.org/scripts/show/486645. Если кнопка Install не работает (проблемы с сайтом userscripts.org), можно скопировать исходный код http://userscripts.org/scripts/review/486645 в файл cf-hide-spam.user.js и запустить отдельно.

Замечания по функциональности приветствуются :-)

Увы, из 9 задач контеста никому не далось больше 7 штук. Хотя бы одну задачу решило 1289 человек — меньше, чем в прошлом году, но тоже неплохо. Главное — суммарное количество фана, полученное участниками :-)

409A - Большая игра

Самая Интеллектуальная Игра В Мире на поверку оказалась широко известной камень-ножницы-бумага. До этого можно было догадаться по примерам — допустим, камень () не очень похож на себя, но бумага [] и тем более ножницы 8< — как живые!

Командная игра реализована так: участники разбиваются на пары, каждая пара играет между собой (в первой строке заданы ходы игроков первой команды, во второй — ходы игроков второй команды), и выигрывает та команда, у которой набралось больше побед в индивидуальных матчах.

Кстати, игра не так банальна, как кажется —

Контест окончен, надеюсь, вам понравилось :-) Разбор задач — здесь. До следующего года!

Во вторник 1 апреля состоится третий Первоапрельский контест — несерьезное соревнование, в котором решить задачу зачастую проще, чем догадаться, что же в ней надо сделать. В его подготовке мне помогали kit1980 и Skiminok, а также команда Codeforces в лице Gerald и MikeMirzayanov.

В этом раунде вас ждет несколько необычных задач (количество уточняется, по предварительным оценкам — от 6 до 10), на решение которых дается два часа. Раунд будет проводиться по схеме ACM ICPC (без взломов, положение в результатах определяется количеством решенных задач и набранным штрафным временем) и будет нерейтинговым. Решения можно сдавать на любом языке, поддерживаемом Codeforces — если, конечно, иное не оговорено в условии задачи :-) Чтобы получить представление о том, что вас ждет, можно взглянуть на контесты прошлых лет: 2012, 2013.

Как обычно, чувство юмора, совместимое с моим, является необходимым условием для успешного участия. Удачи!

Язык этого раунда — Ada, выбранный не за особую оригинальность (на мой вкус он слишком похож на Паскаль), а скорее за название. Язык, названный в честь Ады Лавлейс, как ничто другое подходит к профессиональному празднику программистов, а "язык Ада" — к контесту пятницы, 13-го, посвященному приметам и суевериям. Недостаточную экзотичность языка я постаралась компенсировать задачами, чуть более нетривиальными, чем обычно в SLR.

Традиционно, решение задачи "A+B" (числа могут быть заданы на одной строке):

with Ada.Integer_Text_IO;
use Ada.Integer_Text_IO;

procedure AplusB is
    A, B: Integer;

begin
    Get(Item => A);
    Get(Item => B);
    Put(Item => A + B, Width => 1);
end AplusB;

Система тестирования использует компилятор gnat версии 4.7.2. Для тестирования своих программ можно:

• воспользоваться вкладкой “Запуск” в интерфейсе контеста.
• воспользоваться ideone, язык Ada (gnat-4.6). Напоминаю, что по умолчанию анонимно присланные коды показываются в recent codes, для сохранения спортивного интереса рекомендую зарегистрироваться и использовать опцию приватности "private", или хотя бы использовать опцию “secret” (со времен прошлого раунда сайт претерпел радикальный редизайн, и названия опций изменились).
• установить его локально.

В Linux эта версия есть в репозиториях (на моем Kubuntu получилась версия 4.4.3). После установки компилятора команда gnat make file.adb компилирует код и создает исполняемый файл. При установленном mingw можно устанавливать mingw-get install ada и запускать командой gnatmake file.adb.

13 сентября вас ждет Пятница, 13-ое, День Программиста, в этом году — не только профессиональный праздник, а еще и Surprise Language Round!

Правила проведения раунда:

• Соревнование будет нерейтинговым для всех участников.
• Индивидуальное соревнование по правилам ACM ICPC: положение в результатах определяется количеством решенных задач, при равном количестве — набранным штрафным временем. Изначально штрафное время участника равно 0, при каждой сданной задаче оно увеличивается на время, прошедшее с начала контеста, + 20 минут за каждую неудачную посылку до отправки правильного решения. Решение считается правильным, если оно прошло все тесты из предопределенного набора; правильно ли посланное решение, становится известно сразу. Взломов чужих решений нет.
• В раунде будет 7 задач, примерно отсортированных по сложности, и 2 часа на их решение.
• Решения задач принимаются только на одном языке, который будет объявлен в начале контеста. Язык существует давно, а не придуман нами специально для раунда.
• Пожалуйста, в начале контеста перечитайте этот пост целиком: в нем появится объявление языка, рекомендации по установке компилятора (в интерфейсе контеста будет доступен запуск программы онлайн) и полезные ссылки на документацию. В остальном изучение языка — дело рук самого участника. Для решения задач вы можете использовать любые ресурсы (но не совместное участие); ограничиваться документацией, приведенной в посте, не обязательно.

Мы надеемся, что выбранный нами язык будет незнаком большинству участников раунда.

Контест окончен; надеюсь, вам понравилось. 1465 человек решило хотя бы одну задачу — по-моему, отличный результат. Увы, все 6 задач не дались никому; мои поздравления ShadowSong, который выиграл контест, решив 5 из них с наименьшим штрафом!

290A - Таинственные строки

Год назад было экспериментально установлено, что отсутствие условия не мешает участникам благополучно решить и сдать задачу, а автору экономит немножко усилий по его написанию. Сегодня мы еще раз в этом убедились. Можно было бы сочинить длинную и запутанную легенду о том, как вас, юного, но многообещающего программиста, вызвали в Белый дом и дали важнейшее задание: составить интерактивный список президентов Соединенных Штатов от основания страны до наших дней. В ней могли бы фигурировать долгие и напряженные поиски нужной информации, погони, перестрелки, умирающий напарник, последними словами которого было "Восьмой — Van Buren, не забудь... вывести Van, просто Buren... не пройдет..." Но зачем?

Контест окончен; разбор задач доступен здесь.

Некоторые шутки забавны только в первый раз и от повторения теряют свою прелесть. Я очень надеюсь, что первоапрельский контест не принадлежит к их числу, но проверить это можно только одним способом :-) Приглашаю вас поучаствовать в проверке в понедельник 1 апреля. Сразу опровергну страшные подозрения, зародившиеся было в некоторых умах: шуткой будет содержание контеста, а не сам факт его наличия или отсутствия — это было бы слишком просто :-)

В этом раунде вас ждет несколько необычных задач и два часа времени на их решение. Раунд будет нерейтинговым (еще бы!), и проводиться он будет по схеме ACM ICPC (без взломов, положение в результатах определяется количеством решенных задач и набранным штрафным временем). Решения можно сдавать на любом языке, поддерживаемом Codeforces. Чтобы составить представление о том, что вас ждет, можно взглянуть на прошлогодний контест.

Сразу предупреждаю -- для успешного и позитивного участия в контесте требуется чувство юмора, совместимое с моим! В конце концов, это первое апреля. Удачи!

Upd. Регистрация продлена до конца раунда.