Будьте осторожны с random_shuffle Всем привет! Может быть, эта тема уже обсуждалась, но по запросу "random" ничего похожего на Codeforces не нашел. Предыстория. Хотели с Сашей ([user:adrozdova,2015-03-26]) изучить декартово дерево. Для инициализации приоритетов рекомендуется использовать случайные числа, чтобы высота дерева не была очень большой. Соответственно, надо эти числа как-то получить. Я совсем не разбираюсь в структурах данных, поэтому не задумывался, насколько плохо будет дереву (и будет ли), если приоритеты нескольких вершин будут одинаковыми. Поэтому на всякий случай хотелось сделать их попарно различными (чего не гарантирует простое использование rand() при создании очередной вершины). Предложил следующий, "надежный" и "проверенный" метод — создать массив из N чисел, инициализировать его числами от 0 до (N-1) соответственно, применить к нему random_shuffle — и мы получим N различных ключей в случайном порядке. История. Саша стала сдавать задачи и на практике оказалось, что в нескольких за...

Full text and comments »

EZ Collections, EZ Life (new Java library for contests) Доброго времени суток, дорогие друзья. В этом посте я расскажу об одной из негативных сторон языка Java на соревнованиях по программированию (да и вообще), а точнее, как я попытался ее решить. Как известно, язык Java страдает недостатком при работе с коллекциями: ограничения этого языка заставляют программиста использовать объектные типы данных даже там, где этого как бы и не требуется. Сравните `ArrayList<Integer>` и `vector<int>`: в Java-варианте лист хранит объекты типа Integer, которые создаются при каждом добавлении элемента в список и распаковываются при каждом обращении, тогда как C++-ный вектор хранит обычные честные int-ы. Это замедляет работу программ на Java и много кому не нравится. Вся фигня в том, что нельзя просто так взять и написать примитивный тип внутри угловых скобок. Ну не спроектировали так Java, бывает. Несколько месяцев назад я подумал: а почему бы не обойти эту проблему? Ведь можно просто написать собственные коллекции, и дело в шляпе. Тем более что ни од...

Full text and comments »

Great Permutator — головоломка для программистов [важный UPD в конце записи] **важный UPD в конце записи** Всем привет! Хочу представить вам мой небольшой проект, над которым я тружусь в свободное время уже более полугода. Это игра, которая называется Great Permutator. <img src="http://media.indiedb.com/images/games/1/21/20335/wallpaper_small.png" alt="image"/> Почему здесь? Дело в том, что данная игра представляет собой головоломку особого жанра, так называемого engineering puzzle. Примеры игр такого жанра: LightBot, Manufactoria, The Codex of Alchemical Engineering и, конечно же, SpaceChem. Мне такие игры очень нравятся и, вроде бы, нравятся многим программистам. <blockquote>На самом деле первоначальная версия этой статьи была подготовлена для Хабра. Но я по глупости опубликовал ее не в тот хаб и меня забанили. Когда разбанят (и разбанят ли) - непонятно, поэтому публикую здесь.</blockquote> Чтобы было интереснее, я расскажу некоторые моменты о том, как создавалась эта игра. Такое повествование еще называют постмортемом, но здесь это слово, ...

Full text and comments »

Релиз testlib.h — 0.8.5 **Update: Выпущен новый релиз 0.8.5**. Скачать новую версию вы можете с [сайта проекта](http://code.google.com/p/testlib/). Новая версия внедрена во все сервисы Codeforces и Polygon. Изначально этот пост содержал информацию о девелопмент-версии, но сейчас он используется для описания версии 0.8.5. Библиотека testlib &mdash; самая популярная и развитая библиотека для написания чекеров, генераторов, валидаторов и теперь интеракторов для задач. Первая версия testlib.h была написана мной в 2005-ом, и представляла по большей степени порт testlib.pas на С++. С тех пор многое было улучшено и расширено. В настоящий момент она активно используется в задачах Codeforces, разных этапах Всероссийской олимпиады школьников, многих петрозаводских контестах, всех саратовских соревнованиях и т.д. Вот основные изменения/улучшения. ### Комментарий программы: stdout -> stderr Теперь системные сообщения testlib-программ (чекеров, валидаторов, интеракторов) направляются в стандартный поток ошибо...

Full text and comments »

TCO 2011, days 2 and 3 <p>Продолжается TopCoder Open 2011.<br /><br />Вчера в 10 утра должен был начаться проводимый нами турнир по покеру, победителю которого мы приготовили очень ценный приз в виде MacBook Air. Желающих сыграть оказалось достаточно много, поэтому всех пришлось разбить на два полуфинала. Из 16 человек, желающих сыграть, 8 оказалось русских, и волшебный Random Seed как-то разбил участников так, что один стол оказался целиком русскоговорящим. За ним выиграли Петя и Миша Кевер. По неприятному стечению обстоятельств у меня не осталось фотографии самого полуфинала, но позднее в тот день мы сыграли еще раз, уже неофициально, на том же самом месте, поэтому можно увидеть как это примерно выглядело:<br /> <span> <img alt="" border="0" height="449" src="http://content.foto.mail.ru/bk/shd/_blogs/i-626.jpg" width="600" /> </span> <br /><br />В прошлый раз я почти не выкладывал фотографий места, где проходит TCO, кроме одного вида из окна. Проходит соревнование в отеле The Westin Di...

Full text and comments »

УрФУ. Учим студентов писать код  Всем привет! В данном посте я расскажу про то, как студенты учатся азам программирования. Этот курс несколько лет используется на ФИИТ УрФУ, а с 2023 года будет использоваться для **базовой** группы в новом [алгоритмическом бакалавриате](https://uralsp.ru/algorithm_bachelor?utm_source=cf_op), в продвинутой группе мы ожидаем абитуриентов, которые уже уверенно программируют и знают такие базовые алгоритмы, как бин.поиск/bfs/dfs/Дейкстру. Что за курс? ============ «Основы программирования» были сделаны Контуром для ФИИТ в 2013 году. Это большой курс на [ulearn.me](https://ulearn.me/), рассчитанный на весь первый год обучения. Для удобства он разбит на две части (один семестр — одна часть) по 15 и 13 тем соответственно. Чтобы привести всех студентов к одному уровню, курс начинается с азов — типов данных, условных операторов, циклов — и постепенно доходит до многопоточного и динамического программирован...

Full text and comments »

Разбор задач (Яндекс, раунд 2) <b>А. Зеркальные числа.</b><br> Во-первых, заметим, что если интервал содержит число, состоящее из $a$ цифр, а также число из $b$ цифр (где $a$ &gt; $b$), то нет смысла рассматривать число из $b$ цифр (так как вес числа $10^k$ больше весов чисел, меньших $10^k$).<br> Если же рассмотреть числа с фиксированным числом цифр $(s+1)$, то для них сумма числа и его отражения — константа. Таким образом, учитывая что произведение чисел с фиксированной суммой растет при их сближении, картина у нас следующая: вес числа растет от $10^s$ до $5 \cdot 10^s - 1$, затем он такой же у $5 \cdot 10^s$, затем он убывает и достигает своего минимального значения в $10^{s+1}-1$.<br> Это доказательство, решение же такое: максимальный вес достигается либо в $l$, либо в $r$, либо в числах вида $5 \cdot 10^s$ (можно, например, проверить все $s$, такие, что $5 \cdot 10^s$ лежит в интервале).<br> <br><br><b>B. И снова тетрис.</b><br>Легко видеть, что поле можно замостить фигурками всегда, ког...

Full text and comments »

'Algos' algorithm collection Всем привет! В процессе подготовки к финалу ACM-ICPC 2014, наша команда NU 1 собрала (и продолжает собирать) коллекцию полезных алгоритмов под названием [Algos](http://adilet.org/algos/). Сегодня мы решили поделиться ей с сообществом Codeforces. Для максимальной простоты использования кода из этой коллекции, все алгоритмы (за очень редким исключением) компилируются и работают без необходимости вносить какие-либо изменения в код. Кроме того, для проверки правильности кода и для лучшего понимания цели алгоритма, код каждого алгоритма базируется на определенной тестовой задаче. К каждому алгоритму также прилагается оценка асимптотики и краткое описание. Работа над библиотекой ведется в [репозитории на гитхабе](https://github.com/ADJA/algos). Мы будем рады, если вы захотите внести свой вклад! Все предложения, замечания и указания на ошибки приветствуются в комментариях :) ['Algos' algorithm collection.](http://adilet.org/algos/) [Github repository.](https://github.com/AD...

Full text and comments »

Библиотечка для отладочного вывода <p>Все олимпиадники делятся на два лагеря: те, кто отлаживает в отладчике, и те, кто отлаживает отладочным выводом. Можно бесконечно спорить о том, какой метод удобнее, но факт остается фактом -- и таких, и таких людей полным-полно. Я отношусь ко второму лагерю: во многих ситуациях применение отладчика невозможно, поэтому хочется быть от него независимым. Более того, лично для меня отладочный вывод удобнее (я использую отладчик только для того, чтобы понять, где именно программа упала).</p><div>Так о чем же этот пост? Большинство минусов отладочного вывода на C++ происходит из того, что, к примеру, чтобы вывести вектор, нужно написать довольно много байтов кода. Это не слишком удобно. Чтобы бороться с подобными проблемами, я написал маленькую библиотеку, которая лежит <a href="https://github.com/ilyaraz/debug_output">здесь</a>. Если вы напишете такой код: <a href="http://pastebin.com/9t87jmdp">http://pastebin.com/9t87jmdp</a>, то в результате в stderr выведется следующее:</div><div><br...

Full text and comments »

ICFP Programming Contest 2020 — 72 часа, одна неожиданная задача, команда любого размера **TL;DR:** В следующую пятницу, 17 июля, стартует ICFP Programming Contest — ежегодное открытое онлайн-соревнование, придуманное функциональными программистами. По духу это развлекательный 72-часовой марафон с неожиданными задачами и сложно передаваемыми ощущениями от участия (о них пишут длинные статьи). Если не пробовали, обязательно участвуйте в этом году. **Зарегистрируйтесь на [сайте](https://icfpcontest2020.github.io), подпишитесь на [твиттер](https://twitter.com/@icfpcontest2020).** В отличие от других соревнований, для участия в ICFP Contest собирают команды, причем любого размера. В 2019 году были команды от 1 до 12 человек, а в медианной команде было три человека. За 72 часа нужно решить всего одну задачу — но всегда неожиданную, сложную и многогранную. Например, **в 2018 году** нужно было оптимизировать 3D-печать с помощью наноботов. Вот впечатляющая визуализация решателя таких задач от команды _WILD BASHKORD MAGES_ ([user:Ripatti,2020-07-08], [user:LinesPrower,2020-0...

Full text and comments »

Почему не надо использовать Java.HashSet/HashMap для целых чисел. После небольших обсуждений, мы решили все-таки выложить код генератора, который вызывает #TLE у коллекций HashSet и HashMap в Java. Вот он --- [http://pastebin.com/qpyNcD3R](http://pastebin.com/qpyNcD3R) Идея: давайте заставим хеш-коллекции складывать все элементы в одну корзину. Особенность реализации HashSet/HashMap в том, что они использует линейное преобразование хеша, а затем как номер корзины использует остаток от деления хеша на bucketsNumber. Цитаты из оригинального кода: ~~~~~ static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) { return h & (length-1); /*length всегда степень двойки --- DK*/ } ~~~~~ Собственно, вся сложность...

Full text and comments »