Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

maksay's blog

By maksay, 6 years ago, In Russian,

Внимание, присутствуют спойлеры по задачам!

Не далее как в минувшую субботу в Виннице и Бухаресте прошел полуфинал АСМ в юго-восточном европейском регионе. Этот контест запомнился мне больше всех остальных официальных контестов, и пока впечатления еще свежы, я спешу ими поделиться.

Надо сказать, что мы заранее боялись этого контеста — вспомнить только, что творилось в прошлом году. И если в прошлый раз организаторы откатились до более старой и непроверенной версии тестирующей системы в ночь перед контестом, то в этом году подготовка была явно лучше — за неделю до контеста пришло письмо, что теперь проверяющей системой будет e-judge, и что писать можно будет только из-под Ubuntu. Если первая новость была действительно радостной, то вторая означала отсутствие студии. Можно долго вести холивары на тему того, нужен ли дебаггер, но мы всегда использовали его, если была возможность (а на тренировках она была), и его отсутствие напрягало. Еще одним неприятным сюрпризом стало то, что у Shtrix в ночь перед отьездом поднялась высокая температура, и нам всем пришлось добираться в Винницу в разное время тремя разными поездами.

Пробный тур порадовал сразу несколькими вещами. Во-первых, сервер оказался в Виннице, что породило волну шуток в духе "А давайте 17 раз случайно споткнемся о провод? Да-да, тот, который ведет в Румынию" и "Ну что, на этот раз в Бухаресте пишут до 4:30?" и породила некоторую уверенность, что система все-таки не упадет. Скажу заранее, она таки не упала, и вообще на нее не было никаких нареканий.

Казалось бы, ну какие проблемы могут быть с задачами пробного тура, они уже несколько лет одни и те же.. Не тут то было. На 45ой минуте пришел клар — "Мы ошиблись. В этой задаче нужно посчитать не количество непустых строк, а количество пустых строк". И все-таки нашлись уникумы, сдавшие эту задачу с плюса, тем самым подтвердив гипотезу про четное число ошибок.

После одной из посылок, получившей СЕ на сервере и нормально компилировавшейся локально, мы вежливо поинтересовались, будет ли возможность посмотреть отчеты об ошибках компиляции, и правда ли, что локальная и серверная версии g++ совпадают. Нам ответили, что возможности не будет, а версии совпадает. Когда мы показали, что это не так, пришел совершенно гениальнейший ответ — в духе, "Да, вы правы, они различны. Но между ними нету никакой разницы.". Впрочем, на контесте было еще чудесатее:) А о таких мелочах, как запрет прикасаться к мышкам до начала контеста, я вообще умолчу.

Итак, контест начался. Начался с информации, что задачу А пока не стоит трогать. Проглядев ее и увидев 100 мегабайт аутпута, мы ее отложили. Быстро раздеребанив условия и вычленив С, в которой всего-то надо было запустить решето Эратосфена до 10М, мы быстренько подсунули ее KADR , который и сдал ее на 9ой минуте. Это была первая удачная сдача в контесте, что немного повысило нашу уверенность в себе. Пока он набирал, я нашел задачу I, в которой тоже было что-то несложное — для каждой вершины дерева найти максимально удаленную. Хотя у меня и были сомнения, что это вторая по сложности задача в контесте, ничего другого пока не было и ее тоже подсунули KADR. В то время, пока он читал свой не заработавший с первого раза код на бумажке, я набирал G, в которой оказалась простая симуляция с сэтом. После удачной сдачи I и неудачной G KADR пытался придумать уже кем-то сданную в то время B, а мы со Shtrix курили распечатку и условие G в попытке разобраться, что же не так. Наконец, в условии была обнаружена двузначность — фраза "энзим можно использовать в течении часа" могла означать как "купив энзим его надо использовать на протяжении близжайшего часа" так и "можно ждать целый час и использовать его в начале следующего". И на тестах из условия оба понимания дают одинаковые ответы, естественно. Отправив клар и получив ответ, мы сдали и эту задачу. В ответ на наши возражения что условие двузначно и просьбу снять попытку нам сказали, что оно однозначно, а когда мы привели пример, нам ответили замечательнейшей фразой "No comments". Решив, что спорить с жюри сейчас не время, мы забили. В этот момент мы уже шли на втором месте, отставая от Unicon где-то на 5 штрафных минут.

Где-то в этот же момент раздалось восклицание KADR что "да тут же просто фенвик и все" и я уступил ему место у компа, а сам сел более аккуратно выводить формулы для Е — простая симуляция, но надо разобрать 8 случаев. К 80 минуте обе эти задачи мы сдали, однако отставание от Unicon становилось все больше, заставляя нервничать.

Если задача G с ее неоднозначностями была еще так себе, то задача D оказалась уже классической румынской задачей SEERC, одних ограничений нету, другие — в формулировке "few millions", чтобы разобраться, понадобилось несколько кларов. Наконец, к 2 часам и она была сдана, однако отставание от Unicon уже было таково, что чтобы их обогнать, нам нужно было сдать на одну задачу больше. В голову нет-нет да и закрадывалась мысль "ну где же эта задача, на которой мы сможем оторваться, у нас все таки опыта побольше?". А задачи не было.

Быстро написав А, я получив WA1. Так как в коде было достаточно много индексов, мы в течении более чем получаса и еще одной штрафной "авось" попытки пытались ее сдать, безуспешно. Наконец, предположив, что тесты не соответствуют формату, в котором "после последней строки сразу идет конец файла", мы переделали ввод, чтобы он не был так зависим от пробела в конце, и получили АС. Порядком разозленные, мы написали в ультимативной форме клар, в котором говорилось о кривых авторах^W тестах и требовании снять штрафные попытки. Нам пообещали перетестировать, и мы чуть-чуть успокоились.

Увидев, что задача H была сдана sdya и Seyaua в начале 3его часа, мы решили, что она простая, и надо обязательно решать еще как минимум две. Задача F с ограничениями 4242 отпадала, так что пока я вбивал наивное решение на H, тиммейты думали над J. H в нашем решении свелась к нахождению общего члена арифметических прогрессий, вот только начальные элементы и разности там были до 263 - 1. Оказалось, что мы не так-то хорошо умеем находить эти общие члены — сначала неработающий кусок кода вписал KADR затем неработающую формулу написал я, но в конце концов мы все-таки написали решение, совпадавшее с наивным на маленьких тестах. К этому времени сначала sdya и Seyaua сдали 8 задач, со штрафом в 1006, затем румынская команда со штрафом в 1079, а затем и третья команда из нашего вуза, Reckless, со штрафом в 1005. Наше решение на с++ упорно давало ВА 1 и было принято решение перекодить его на яве. После перекоживания мы прикинули, сколько штрафных попыток мы можем сделать,чтобы после сдачи выйти на первое место, вышло около 5. До конца контеста оставалось пол часа, ситуация нервнее некуда, сдача на яве дает ту же ВА 1. Вылавливаем мелкий баг, и получаем ТЛ 3. 1000 запусков расширенного Евклида для BigInteger — и ТЛ 3. Ругаемся, переписываем Евклида на лонги, посылаем опять — и опять ТЛ 3. Это уже какая-то ересь.. До конца контеста 15 минут, и тут нам в голову приходят две полубезумные идеи. KADR предлагает пока числа маленькие, написать такое же решение и запускать его в лонгах, а я говорю, что еще стоит отсортировать инпут, чтобы члены прогрессий дольше оставались маленькими. Посылаем — ВА 9. Наконец, за 4 минуты до конца, уже не веря, что этот бред может работать, меняем константу того, когда работает решение в лонгах с 2млрд на 2млн, посылаем и получаем АС. Ощущения в этот момент передать сложно.. Быстро подсчитываю на бумажке наш штраф. До того 564, сдача почти в 300 минут, 7 штрафных =... 1004. Еще раз смотрим на монитор, где у Reckless 1005 и нашу команду дружно распирает истерический смех. Из-за кулис выходит Milanin смотрит на нас и стучит кулаком по голове:) Последние 4 минуты на последних нервах смотрим, не радуюется ли кто-то еще. Вроде нет, но мы все равно почти трясемся. Сразу после контеста узнаем, что все ОК, мы таки первые, но радоваться сил уже почти нет:) Думаем только, что свой запас везения мы исчерпали на много месяцев вперед.

Уже вечером после аппеляции нам и румынской команде сняли некоторые штрафные попытки, так что наш штраф стал равен 910, но это уже было не важно. Важно, что Kyiv NU BZFlags едут на финал. Увидимся:)

Read more »

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

By maksay, 7 years ago, In Russian,

Итак, совсем недавно завершился первый раунд Snark News Summer Series. Предлагаю тут его обсуждать, а также напишу небольшой разбор.


Задача А

Вероятно, самая простая задача раунда, с которой и начали большинство участников. Для ее решения следовало заметить, что существует ровно свободных бит в палиндромах с длиной битовой записи Х - биты, начиная с второго по сташинству, до середины строки. То есть палиндромов с длиной битовой записи Х всего . Таким образом можно узнать длину битовой записи палиндрома, который нам нужен, и номер нашего палиндрома среди всех палиндромов такой длины. Ну а само число тогда получить уже очень просто:
1). Пусть S - первая половина искомого палиндрома. Тогда ее старший бит - 1, а следующие биты - это двоичная запись номера нашего палиндрома, дополненная сначала нулями так, чтобы длина S была равна X / 2 + X%2.
2). Ответ - это S + S', если длина палиндрома четная, S' - перевернутая строка S. Если длина нечетная, то у S' надо просто откусить первый символ.

Интерестно, есть ли решение формулой.

Задача Б

Пожалуй, эта задача мне понравилась больше всего. Как раз то, что надо как одна из 6ти на 80 минут - немного покодить, немного подумать, есть, где допустить баг.

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

Задача С

Я эту задачу, как и многие другие, решал паросочетанием. Можно заметить, что четность суммы координат клетки, где стоит конь, и тех полей, куда он бьет, различна. Таким образом можно разбить все поле на два типа клеток, и проверсти ребра между теми парами невырезанных клеток, в которые находятся на расстоянии хода коня друг от друга. После этого в полученном графе построить максимальное паросочетание и поставить коней на паросочтенные клетки одной из доль (то есть только с четной суммой координат, к примеру). Могло показаться, что паросочетание не пройдет, но это заблуждение:) Тут 5000 вершин, из каждой по 8 ребер. В Харькове за 3 секунды почти все участники пропихнули паросочетание на 50000 вершин, из каждой из которых было 32 ребра (2011 год, 9 день, "Регулярное паросочетание").

И еще мне кажется, что тут проходила какая-то жадность. Идеи?

Задача Д

Не люблю такие задачи. 25с, 666 тестов. Непонятно, должно ли решение выполнять макстест на 25/666 с., или в файле не будет много макстестов, и пройдет какой-то пропих. Я пытался сдать в дорешивании динамику по подмаскам и перебор, оптимизированный запоминанием. Перефразируя Томаса Эдисона, я не зафейлил - я написал 26 кодов, которые делают что-то другое:)

ПС. Хотелось бы услышать, как сдавали те, кто сдали.

Задача Е

Неплохая задачка, но, по-моему, ограничения чуть-чуть переподкручены. Решение - две динамики:
F[V, M] - максимальный поток, могущий идти вверх из вершины V если мы на ее поддерево потратили M миллионов. (Пропускная способность ребра над этой вершиной не учитывается.)
G[V, M] - максимальный поток, могущий идти по ребру от вершины V вверх, если мы на ее поддерево и на ребро вверх от нее в сумме потратили M миллионов.

Ну и переход изящен и самоочевиден:
ПС: Если не самоочевиден - деньги вершины надо разделить между левым и правым поддеревом и ребром в поддерево. Деньги вершины и ребра в нее надо разделить на деньги в вершину и деньги, потраченные на ребро.
L, R - правый и левый потомок вершины. Для листьев F[Leaf, M] = C[Leaf] + M, где C[Leaf]- количество изначально вырабатываемой в листе нефти.


Что раздражает - другое, более сложное решение, с такой же ассимптотикой O(N * M2) не прошло по ТЛу, такое же решение, только не двумя циклами, а двумя функциями, которые друг друга вызывают - тоже. Это зашло меньше чем за 3с. при ТЛе в 4.

Задача Ф

Ну, построить двудольный граф по правилу "если в инпуте есть ребро i → j, то провести ребро из вершины i левой доли в вершину j правой", построить максимальное паросочетание и вывести его, если оно совершенное. Хм. Где-то выше я это уже писал. По-моему. И по-моему давать в одном контесте две задачи, которые решаются одним и тем же алгоритмом (хотя, может, могут быть решены и по-другому) - незачет.

Еще сильно расстроил плохой тест по задаче Е - я-то с ним только в дорешивании боролся, а вот участники врея потеряли.

Read more »

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

By maksay, 8 years ago, In Russian,

На почту пришло письмо следующего содержания:

Hello,
Next weeks we will arrange several high level contest in order to allow the ACM ICPC World Finals contestants to prepare as better as possible. The first of them will take place this Saturday (April 23th) at 9:00 UTC. A really hard contest, a present from the great Rujia Liu to all of us.

На сайте увы сказано, что это контест на структуры данных. Также сказано, что он будет длиться 24 часа с отдельным зачетом по первым 5 часам.

Хотелось бы узнать у тех, кто уже учавствовал в подобных контестах/контестах этого автора, будет ли это вполне адекватный сложный тренировочный АСМ-контест, который можно написать как командную тренировку или же это будет жутко тематический контест с рассчитанными на 24 часа гробами, вместо которого лучше написать какую-то другую тренировку?

 

 

 

Read more »

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

By maksay, 8 years ago, In Russian,
Только у меня веб-интерфейс не грузится?
(Обсуждение задач - после конца контеста)

UPD: 
Извините, но это просто нет слов!
В 3:30 у нас было 5 сданных задач и подходила 6я. Внезано сначала ретестят Н, затем включают полный ретест и просят не сабмитить до сообщения от жюри. Ретест длится почти полтора часа, и никакого сообщения нету. Наконец в 4:40 жюри отвечает на чей-то вопрос, что оказывается, сабмитить уже можно. Впрочем, некоторые участники сабмитили во время реджаджа, но это их дело.

В теперь о совсем фееричном: задача Е, которая проходила до реджаджа, после дает ТЛ 3.. Задача Н, которая проходила до реджаджа, да ВА/ТЛ 19. При этом ограничения подкручены так, что на ней у нас не проходил достаточно оптимальный квадрат, та же ситуация в Д. В общем, не понравилось!

Хотел уточнить, как решали Е и Д и Н те, у кого она прошла? С какой асимптотикой? У нас был N^2logN и N^2 и N^2 соответственно.

Read more »

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

By maksay, 8 years ago, In Russian,

A

Итак, в этой задаче можно было просто выполнить то, что было написано в условии – перебрать все числа от A до B, для каждого из них перебрать все перестановки модулей и проверить, что не менее чем для 7 перестановок f(x)=x.

 

А еще можно было заметить следующее. Пусть p=min(p1,p2,p3,p4). Тогда если x<p, то, очевидно, при взятии любого модуля x не изменится, ведь он меньше любого модуля. Очевидно также, что в противному случае он изменится, потому что будет взят по определенному модулю, меньше или равному х. Таким образом, вне зависимости от перестановки модулей, для числа либо выполняется равенство f(x)=x, либо не выполняется. Некоторые участники просто проверили для определенной перестановки модулей, подходит ли каждое число из промежутка, и вывели количество чисел, для которых равенство выполняется. Однако достаточно было даже просто посчитать количество чисел в пересечении интервалов [0;p-1] и [a;b].

 

Read more »

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

By maksay, 8 years ago, translation, In English,
Hi everybody!

Today authors are me and Roman Iedemskyi (Shtrix). Big thanks for help in preparing problems to our teammate Iaroslav Tverdohklib, Artem Rakhov, Maria Belova and Dmitry Matov.

Hope you will enjoy the contest!

UPD: Congratulations to winner rng_58!

Read more »

Announcement of Codeforces Beta Round #62
 
 
 
 
  • Vote: I like it  
  • +134
  • Vote: I do not like it  

By maksay, 9 years ago, In Russian,
Как приятно осознавать, что после длинного пути TL 16->17->36->37->38->52 и крошечного оптимайза через 5 минут после конца задача наконец прошла *WALL* :)
Впрочем, не углубляясь в радиус кривизны моих рук и общий тупёж) 4я правда решается перебором, кто знает? Потому что вот это не пример хорошего решения, наверное)

if (sum>5000&&cnt>5) break;

Read more »

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