KhaustovPavel's blog

By KhaustovPavel, 4 years ago, In Russian,

478A - Initial Bet

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

478B - Random Teams

Если переформулировать задачу в терминах теории графов, то ее можно сформулировать следующим образом: Имеется граф, состоящий из n вершин и m компонент связности. Внутри каждой компоненты связности каждая пара вершин этой компоненты связана ребром. Другими словами, каждая компонента связности является полносвязной. Какое наименьшее и какое наибольшее количество ребер может содержать такой граф? Рассмотрим процесс построения графа из n вершин и m компонент связности. Для начала предположим, что каждая из m компонент содержит ровно одну вершину. Остается распределить оставшиеся n - m вершин так, чтобы минимизировать или максимизировать количество ребер. Заметим, что при добавлении новой вершины в компоненту связности размера k, количество ребер увеличивается на k (новая вершина соединяется с каждой из уже существующих одним ребром). Следовательно, для того, чтобы минимизировать количество образованных ребер на каждом шаге, требуется каждый раз добавлять вершину в компоненту связности наименьшего размера. Если действовать согласно такой стратегии, то после распределения вершин по компонентам связности появится компонент размера и компонент размера . Аналогично, для того, чтобы максимизировать количество ребер, на каждом шаге необходимо добавлять очередную вершину в компонентну связности наибольшего размера. Если действовать согласно такой стратегии, то образуется одна компонента связности размера n - m + 1, оставшиеся компоненты связности будут состоять из одной вершины. Зная количество компонент связности и их размеры, можно посчитать общее количество ребер. Для полносвязной компоненты, состоящей из k вершин, количество ребер равняется . Следует помнить про необходимость использовать 64-битный тип данных для хранения количества ребер, которое квадратично зависит от значения n.

478C - Table Decorations

Рассмотрим ситуацию, когда величина max(r, g, b) - min(r, g, b) ≤ 1, в таком случае, очевидно, ответ равен . Мы всегда можем украсить столько столов тремя воздушными шарами разных цветов. Очевидно, что оставшееся количество шаров будет меньше трех и, следовательно, не может быть использовано для украшения стола в любом случае. Все оставшиеся случаи имеет смысл свести к ранее рассмотренному. Если есть один цвет такой, что количество шариков этого цвета больше, чем суммарное количество шариков для оставшихся двух цветов, то всега выгодно украшать стол двумя шарами этого цвета и одним шаром того из оставшихся цветов, которого больше на данный момент. Далее можно разными способами группировать операции и выполнять более одной операции за раз. Другим решением можно назвать тот факт, что ответ будет отличен от , но только тогда, когда max(r, g, b) ≥ 2·(r + g + b - max(r, g, b)), в таком случае ответ r + g + b - max(r, g, b). В этом случае шарики двух наиболее редких цветов закончатся раньше, чем шарики одного наиболее популярного, если украшать каждый стол с использованием двух шариков наиболее популярного цвета.

478D - Red-Green Towers

Для начала можно заметить, что для того, чтобы построить красно-зеленую башню высоты h потребуется кубиков. Следовательно, высота полученной башни для заданных ограничений никогда не превысит 893. Эту высоту можно определить заранее, если предположить, что все кубики одного цвета. Попробуйте доказать это самостоятельно. Далее можно решить задачу с использованием динамического программирования. Пусть F(t, r) — количество способов собрать башню наибольшей высоты, если собрано t верхних этажей и остались незадействованными r красных кубиков. Среди аргументов функции нет количества оставшихся зеленых кубиков g — его можно однозначно определить из значений t и r: , где r0 и g0 — изначальное количество красных и зеленых кубиков, соответственно. Ну а дальше следует рассмотреть лишь два перехода: пострить t + 1-ый уровень из красных или из зеленых кубиков: F(t, r) = F(t + 1, r - t) + F(t + 1, r). Очевидно, кешировать данные в массиве размера 893 × 2·105 — не лучшая затея. В таком случае можно подсчитывать значения функции для всех значений t от 0 до h, храня в памяти только значения для текущего значения t и для предыдущего, от которого оно будет зависеть.

478E - Wavy numbers

Для решения этой задачи необходимо было заметить, что волнистых чисел на интервале от 0 до 107 намного меньше, чем 107. В таком случае можно решить задачу с использованием подхода meet-in-the-middle. То есть отдельно решить эту задачу для первых семи цифр ответа, и для последних семи цифр ответа. Для этого потребуется отдельно сгенерировать все волнистые числа на интервале от 0 до 107, которые начинаются с возрастания двух соседних цифр, и аналогичные волнистые числа, которые начинаются с убывания двух соседних цифр. Дальше для каждой первой половины мы можем посчитать rl — ее остаток от деления на n и, затем, определить количество подходящих вторых половин, которые должны иметь остаток от деления равный .

Для задачи было установлено ограничение времени равное 1.5 сек. На самом деле, если написать решение с подходом meet-in-the-middle достаточно оптимально, то решению потребуется гораздо меньше времени. Приведенная авторская реализация (8271836) умеет решать аналогичную задачу для 1 ≤ n, k ≤ 1016 примерно за 2.5 сек.

Read more »

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

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

Hi, everyone!

Regular Codeforces round #273 for participants from the second division will take place on 16 October, 19:30 MSK. Participants from the first division are able to participate out of the contest.

Problem setter: KhaustovPavel (Khaustov Pavel, Russia, Tomsk, Tomsk Polytechnic University)

Special thanks to Codeforces team and, in particular, Maxim Akhmedov (zlobober) for help in round preparations and Maria Belova (Delinur) for translations.

Participants will be given five problems and two hours to solve this problems.

Points distribution: 500-1000-1500-2000-2500

UPD: +10 minutes to start

Good luck!

Read more »

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

By KhaustovPavel, 5 years ago, In English,

424A - Squats

The problem is to find the number of standing hamsters. If it is less than half, we should make the required number of hamsters standing. Otherwise we should make some hamsters sitting.

424B - Megacity

We can sort all the cities by their distance to the Tomsk city di. After that we are to find the smallest index t for which the total population p0 + p1 + ... + pt >  = 106. In such case the answer is dt. We can sort all cities in O(NlogN) and find the value of t in O(N). Limits for N allow O(N2) sorting or any other O(N2) solution.

424C - Magic Formulas

Consider the following formulas:

Let . Lets compute the following function for each i (0 ≤ i ≤ n). One can do it in O(n) using .

Lets transform ci:

Also:

Thus:

That means, if n / i is odd, , otherwise — . ci can be computed in O(1), that's why the complexity of the whole solution — O(n).

424D - Biathlon Track

Due to the time limit for Java some of O(N4) solution got Accepted. The authors solution has complexity O(N3·logN). The main idea is to fix the top-border and bottom-border. Then, using some abstract data type, for each right-border we can find the most suitable left-border in O(logN) time. For example we can use set in C++ and its method lower_bound. For better understanding lets have a look at the following figure:

For such rectangle we fix the upper-border as row number 2 and bottom-border as row number 5. Also, we fix right-border as column number 6, and now we are to find some left-border. Now we can split the time value for any rectangle for two summands. One of them depends only on left-border and another one — on the right-border.

With the blue color the summand that depends only on the right-border is highlighted. With the red and yellow color — the other summand is highlighted. The red-colored value should be subtracted and the yellow-colored should be added. For any blue right-border's value we are to find the closest red-yellow left-border. That is the problem to be solved with the help of STL Set or any other similar abstract data type.

424E - Colored Jenga

A classical DP-problem on finding expected number.

Lets define some function F(S) for some state — the expected number of minutes to finish the game from this state. For each color we can compute the probability of showing this color by the simple formula , where c — the number of dice's faces of this color. Now we are to find the probability PL to stay in this state for the next minutes. That is the probabilty of showing black color plus the probabilities of showing colors with no blocks of that color to be removed from the tower. Now we can find the value via the following formula:

The only problem is to find how to encode the state. To reduce the number of states we can assume that there is only 18 different type of levels, but not 27. For better time-performance it is better to use hashing. The solution for this problem requires good understanding of DP and quite good implementing skills.

Read more »

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

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

Hi, everyone!

Regular Codeforces round #242 for participants from the second division will take place on 25 April, 11:00 MSK. Participants from the first division are able to participate out of the competition.

The contest is prepared by programmers from Tomsk Polytechnic University: Pavel Khaustov (KhaustovPavel), Olesya Golub (Taube), Nickolay Kuzivanov (bnick), Dmitry Savvinov (dsavvinov), Alexey Vetrov (noxwell).

Special thanks to Vladimir Chalyshev (cmd) and Alexey Dergunov (dalex) for their impact.

Also, thanks to Codeforces team and, especially, to Gerald Agapov (Gerald) and Maria Belova (Delinur).

Points distribution: 500-1000-1500-2500-3000

Good luck!

Read more »

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

By KhaustovPavel, 6 years ago, In Russian,

Вот и пролетела вереница новогодних праздников, большинство из нас неохотно возвращаются к трудовым будням. Кроме того, конец новогодних праздников совмещен и с началом последнего этапа голосования "Итоги 2012 года" на сайте проекта SnarkNews. Собственно, об этом событии мне бы и хотелось поговорить в этом посте.

Казалось бы, обычное голосование, которое вполне может быть результатом субъективности и чувства юмора участников олимпиадного движения. Но если взглянуть на это голосование под хотя бы сколько-нибудь отличным углом, то в нем можно увидеть неплохую попытку собрать в одном месте все самые значимые события и результаты прошедшего года, выделить людей, которые внесли наиболее значимый вклад в олимпиадное движение. Хотелось бы попросить не относиться пренебрежительно к такого рода голосованию. Если нет желания голосовать объективно — лучше просто не голосуйте.

Год выдался крайне богатым на события: ИТМО стал четырехкратным чемпионом Мира, Евгений Капун стал третьим в истории двукратным абсолютным чемпионом Мира, Роман Андреев стал победителем Facebook Hacker Cup 2012, Егор Куликов стал победителем TopCoder Open 2012, Геннадий Короткевич поступил в ИТМО, Владислав Епифанов первым откликнулся на слова Петра Митричева "Попробуйте, отберите в следующем году" на Russian Code Сup, школьники сборной России отрешались на четыре золотых медали на IOI, СпбГУ #4 уверенно победили на Всесибирской олимпиаде, а под конец года настоящий action развернулся в последние минуты заморозки на NEERC, победителем которого в третий раз подряд стала команда Национального исследовательского университета ИТМО. И это — только самые крупные победы команд и участников из России на сравнительно крупных соревнованиях. Если приглядеться повнимательнее, то можно вспомнить несколько не столь приятных для постсоветского сообщества олимпиадных программистов событий, таких как победа Johnny Ho на IOI 2012, победа Китая в суммарном зачете все того же IOI 2012, просто необъяснимуя неудача MIPT The Sun на NEERC с несданной задачей G, "железное" доминирование Saratov SU #3 над другими командами этого университета все на том же NEERC 2012. Если говорить о чем-то более радужном, то можно также отметить огромное количество раундов в 2012 году на Codeforces, золотое выступление MIPT Waterogers на финале ACM ICPC 2012, два Белорусских комплекта медалей все на том же финале ACM ICPC 2012, проведенные VK Cup и AI Cup. Об этих событиях помнят все, они обсуждались, многие из них неоднократно становились причинами разного рода шуток. Но есть события и, связанные с ними, люди, которые не столь заметны и обсуждаемы, насколько они этого заслуживают, исходя из их важности для нас и нашего сообщества. На одном из таких событий я бы и хотел сделать серьезный акцент. Но... Обо всем по порядку.

На дворе начало августа. Близятся Петрозаводские сборы. Я усиленно готовлю контест для этих сборов. Во время подготовки я понимаю, что одну из задач неплохо бы было сделать интерактивной, но я не имею ни малейшего представления о том, как же грамотно подготовить интерактивную задачу. Я пытаюсь придумать хоть сколько-нибудь подходящую замену интерактивности, но получается какая-то ерунда. Как итог, одна из малопригодных замен интерактивности оформляется в polygon. К моему счастью, Павел Абизяев (Nyatl) и Владимир Чалышев (cmd) согласились мне помочь с подготовкой контеста (за что им отдельное "спасибо"). От Паши Абизяева я узнал о том, что уже в сентябре планируется Гран-При Удмуртии, автором которого является он сам (если я не ошибаюсь, идея одной из задач принадлежит его тренеру — Юрию Когану). И, казалось бы, нет в этом ничего удивительного, это — далеко не первый Гран-При Удмуртии, в подготовке которого участвует Паша Абизяев. Но дело в том, что контест этот — особенный, все десять предложенных в нем задач — интерактивные. Да, Паша сам разобрался с тем, как разрабатываются интерактивные задачи, сам подготовил десять интерактивных задач достаточно высокой сложности (за исключением окончательных условий, с ними отдельная песня была). Более того, он лично предложил модифицированные варианты этих же задач для второго дивизиона Открытого кубка, опять же, всех десяти. Чтобы больше не возвращаться к теме моего контеста, скажу, что с непосредственной помощью Паши Абизяева мы подготовили интерактивный вариант той самой злополучной задачи и дали его на Петрозаводские сборы. Да, не все так гладко прошло на контесте, как хотелось бы, но эта задача стала первой интерактивной задачей в истории Петрозаводских сборов. С ее помощью мы предупредили несколько серьезных ошибок на будущем Гран-При Удмуртии. Кроме того, тренер Саратовского ГУ и один из авторов проекта Codeforces — Михаил Мирзаянов на фоне всей этой Петрозаводской шумихи на тему интерактивных задач опубликовал на Codeforces пост, в котором описал свой взгляд на интерактивные задачи и поднял на обсуждение детали реализации интерактивных задач. Позже, это вылилось в модификацию библиотеки testlib и проекта polygon, а также первую интерактивную задачу на Саратовском четвертьфинале.

Стоит отметить, что Паша до последнего заботился о том, чтобы участники получали наиболее объективные и информативные вердикты. Буквально за считанные часы до начала Гран-При Удмуртии в ejudge еще вносились изменения с целью исправить неправильные вердикты, которые он периодически выдавал. Удивительно, но контест (не смотря на достаточно большую очередь тестирования, что вполне объясняется интерактивностью) удался на славу. После него — море положительных отзывов и огромное количество обсуждений на тему интерактивных задач. Стоит ведь задуматься над тем, что такое интерактивные задачи. Это — огромный пласт принципиально новых задач, решать и тестировать которые намного сложнее. Многие из этих задач без интерактивности вообще не имеют смысла. Без всякого преувеличения этот Гран-При можно назвать настоящим прорывом. Это был невероятный по сложности и времени подготовки эксперимент, который дал огромный толчок развитию спортивного программирования. Что касается самого Паши Абизяева, то мне бы хотелось отметить его невероятное умение придумывать задачи. Он видит задачи во всем, что его окружает. Фанатизм? Может быть. В плане участия в олимпиадах он не был настолько же заметен, насколько и такие гранды подготовки контестов, как Андрей Станкевич и Петр Митричев, но как автора задач я бы вполне мог поставить его с ними в один ряд. Если посмотреть на тот проблемсет, который удался ему на последнем Гран-При Удмуртии, то можно заметить, что кроме двух задач, каждую из задач решила хотя бы одна команда, но лишь одной команде удалось решить хотя бы половину задач. А одна из задач и вовсе ушла на Новогодний "Простой" контест.

Возвращаясь к теме, которую я затрагивал в самом начале этого поста, я бы хотел сказать, что этот проблемсет действительно заслуживает звания "Лучший проблемсет 2012 года". Хотелось бы, чтобы такая инициатива и такой труд были вознаграждены хотя бы таким образом. Все сравнимые с ним проблемсеты готовились целыми группами разработчиков, в то время как этот (за исключением окончательных текстов условий) Паша подготовил сам, без всякой помощи. Можно говорить о том, что это — агитация. Словом, я проконсультировался с Олегом Богдановичем, агитация отнюдь не запрещается. Моей основной задачей было обратить внимание общества на этот проблемсет и его важность для сообщества спортивных программистов.

На этом, господа, мои мысли и мой словарный запас исчерпаны. Спасибо за внимание.

Read more »

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

By KhaustovPavel, 6 years ago, In Russian,

Задача A (div2) — Шкафы

Автор: max777alex

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

Задача B (div2) — Котенок Гав

Авторы: max777alex, KhaustovPavel

В данной задаче требовалось найти минимальное положительное N-значное число, которое делится без остатка на 2, 3, 5 и 7. Очевидно, раз все эти четыре числа являются простыми, то число, которое делится на все эти четыре числа, должно делиться на их произведение 2·3·5·7 = 210. Для N < 3 такого числа не существует. Для N = 3, конечно же, ответ равен 210. Для N > 3 следуем следующему алгоритму.

Найдем остаток R от деления 10N - 1 на 210. Далее требуется добавить 210 - R к 10N - 1, чтобы получилось число, кратное 210. Учитывая, что 0 ≤ R < 210, получаем, что последние три разряда числа определяются значением R, а оставшиеся разряды — совпадают с соответствующими разрядами числа 10N - 1.

Можно также было заметить закономерность для последних трех разрядов с изменением N и заменить вычисления остатков аккуратным разбором случаев.

Задача A (Div1), C (div2) — Электроник-футболист

Авторы: am-real

Для начала временно избавимся от радиуса мяча — сдвинем верхнюю стену на радиус вниз. Мяч, в таком случае, можно считать материальной точкой. Штанги не трогаем. Отразим центр мяча относительно сдвинутой верхней стены. Соединим полученный отраженный центр мяча и точку (0, y1 + r).

Далее остается аккуратно определить, не касается ли мяч левой стены. Очевидно, что точкой стены, наиболее близко лежащей к траектории центра мяча, будет штанга (0, y2). Таким образом достаточно проверить расстояние от этой точки до траектории мяча. Если оно меньше радиуса, значит ответа нет, иначе — точка пересечения проведенной ранее линии и сдвинутой на радиус вниз стеной и будет ответом.

Если целиться выше точки (0, y1 + r), траектория центра мяча только приблизится к штанге (0, y2), поэтому целиться в другие точки смысла не имеет.

Задача B (Div1), D (div2) — Конфеты — каждому!

Автор: KhaustovPavel

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

С ростом количества изначально имеющихся с собой конфет, время, которое требуется для угощения всех жителей может либо не изменяться, либо уменьшаться. Следовательно, здесь применим бинарный поиск по количеству конфет. С помощью бинарного поиска закрепим количество конфет, которые мы изначально взяли с собой. Идем слева направо (от первого участка, до последнего). Если находимся на участке с магазином — обязательно покупаем конфеты (денег у нас бесконечно много, значит, нет смысла не покупать конфеты). Если мы находимся на участке с домом, то при наличии конфет — угощаем жителей этого дома. Если же конфет у нас нет, то пропускам этот дом. Несложно доказать, что возвращаться назад выгодно только тогда, когда у нас достаточно конфет, чтобы угостить жителей всех пропущенных домов. Пусть первый пропущенный дом оказался на участке L. На участке R мы купили конфеты, и теперь их достаточно, чтобы угостить жителей всех пропущенных домов. Тогда участок от L до R мы дополнительно пройдем еще на два раза. Если попытаться угостить жителей пропущенных домов раньше, чем мы достигнем участка R (на участке T), то участок от L до T нам так же придется преодолеть дополнительно на два раза. Однако, так как мы не можем угостить всех жителей на отрезке от L до T, это говорит о том, что придется преодолеть некоторую часть этого интервала еще два раза, для чего нам еще на два раза придется преодолеть отрезок от T + 1 до R. Очевидно, что преодолев на два раза отрезки (L, T) и (T + 1, R) мы, фактически, преодолели на два раза отрезок от L до R. Помимо этого, какую-то часть отрезка от L до T нам потребуется преодолеть еще два раза. Получается, что количество времени, которое нам потребуется, будет строго больше, чем в первом случае. Аккуратно моделируем процесс за O(N), чтобы определить минимальное количество времени, которое потребуется на выполнение прохода по улице.

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

Результирующая асимптотика O(N·logN) (логарифм возникает из-за использования бинарного поиска).

Задача C (Div1), E (div2) — День рождения ослика Иа-Иа

Авторы: am-real, KhaustovPavel

Сформулируем ряд утверждений, которые помогут нам решить задачу. При любом действии Винни-Пуха количество нетронутых горшков на любой из полок не может быть увеличено. Таким образом, если на полке с номером i изначально находилось Ai горшков, то в любой момент времени нетронутых горшков на этой полке будет C, причем 0 ≤ C ≤ Ai. Несложно поддерживать вероятность P(i, C) того, что на полке с номером i находится C нетронутых горшков для всех возможных значений i и C. Это можно сделать с помощью динамического программирования.

Очевидно, ответом после каждой операции будет сумма P(i, 0) по всем возможным значениям i. Заметим, что после каждой операции число нетронутых горшков может измениться только на полке, с которой Винни-Пух берет горшки. Формулы для переходов между состояниями динамического программирования достаточно тривиальны. Какие-то трудности могут возникнуть при выводе формул для ki ≠ 1. Этих трудностей можно избежать, если разбивать запросы с ki ≠ 1 на ki запросов с ki = 1, ведь 1 ≤ ki ≤ 5, и, следовательно, время выполнения существенно увеличено не будет. Допустим и вариант, когда запросы не разбиваются. Для этого требуется аккуратно вывести несложные формулы переходов.

Несложно заметить, что перед первым запросом можно посчитать сумму P(i, 0) по всем значениям i. Далее, при выполнении каждого запроса ui, vi, ki, до его выполнения отнимать P(ui, 0) от ответа, а после его выполнения — добавлять новое значение P(ui, 0) к ответу.

Если обозначить наибольшее значение Ai по всем i, как MaxA, то асимптотика такого решения, очевидно, будет O(N·MaxA). Памяти такое решение так же требует O(N·MaxA).

Задача D (Div1) — Ежик и звезды

Авторы: am-real, KhaustovPavel

Для начала заметим, что задачу можно свести к более простому варианту аналогичной задачи. В первую очередь, можно избавиться от точек, которые не находятся между двумя заданными во входных данных лучами, выходящими из начала координат. После чего можно повернуть все точки относительно начала координат на такой угол, чтобы один из лучей совпал с одной из осей координат. Для определенности положим, что мы повернули все точки на угол α1 так, чтобы луч, который был пущен под этим углом совпал с осью OX.

Теперь задача существенно упрощается. Все точки лежат в первой координатной четверти (то есть все координаты строго положительны), и имеется прямая L0 под углом α2 - α1, которая проходит через начало координат и все точки лежат ниже нее. Добавим точку начала координат в наш набор, как фиктивную. Проведем через каждую из точек прямую Li параллельную прямой L0. Отсортируем точки в порядке убывания ординаты пересечения прямой Li с осью Oy. Пойдем с конца. Для каждой точки i будем считать длину наибольшей цепочки MaxL(i), которая начинается из этой точки (смотреть будем на те точки, которые уже рассмотрены в нашем обратном порядке обхода). Для каждой точки i мы будем рассматривать все точки j между заданными лучами и выбирать такую, что MaxL(j) максимально, после чего полагать MaxL(i) = MaxL(j) + 1.

Чтобы рассмотреть только те точки, которые находятся в области между лучами выходящими из точки i, требуется выбрать такие точки j, для которых Li пересекает ось Oy выше, чем Lj, и ордината Yj не меньше, чем ордината Yi. Заметим, что из-за порядка сортировки первое условие всегда выполняется, если аккуратно обработать точки с одинаковыми прямыми Li. Для соблюдения оставшегося ограничения достаточно воспользоваться стандартной идеей с деревом интервалов. Но гораздо лучше заметить, что эта задача эквивалентна задаче нахождения поиска наибольшей возрастающей последовательности. Ответом будет значение MaxL для фиктивной точки начала координат.

Как результат, имеем решение с асимптотикой O(N·logN) и O(N) затратами памяти.

Задача E (Div1) — Бесконечная матрица

Автор: KhaustovPavel

Несложно заметить ряд закономерностей. Для начала обратим внимание на первую строку матрицы. В i-ом столбце первой строки находится элемент со значением (i - 1)2 + 1. Несложно найти закономерность для первого столбца — там в чистом виде квадраты натуральных чисел. Диагональ тоже задается легкой закономерностью i2 - i + 1.

Дальше несложно заметить, что в любом столбце до элемента главной диагонали значения увеличиваются с шагом в единицу. После элемента главной диагонали элемент в i-ой строке равен i2 - i + 1. Как видим, можно и диагональный элемент отнести к этой же закономерности.

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

Теперь стоит выполнить все вычисления по модулю 1010. Для того, чтобы отследить, имеет ли число более десяти знаков, будем хранить (помимо остатка) частное от деления на 1010 по модулю нескольких различных простых чисел порядка 109. На практике достаточно и одного простого числа, но для генерации тестов использовалось сразу четыре.

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

Read more »

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

By KhaustovPavel, 6 years ago, translation, In English,

Hi, everyone!

The authors of Codeforces Round #152 are am-real, max777alex and me.

Special thanks to Gerald who helped us to prepare this round. Also, we want to thank Delinur for english statements. And we'd like to thank Seyaua and sdya for reading and testing problems of this round.

The round will be held on 25th of november at 19:30 in Moscow time, and it will take place in both divisions.

Score distribution div1: 1000 1000 1500 1500 2500

Score distribution div2: 500 1000 2000 2000 2500

Contest is over.

We appologize for ambiguity in the statement of the problem A. It was not clear whether it is possible to touch the goal post when the ball crosses the goal line. However, both ways to understand the problem statement were accepted. These solutions differ by an infinitesimal amount. The only thing that this ambiguity has effected a lot — hacks. All the hacks, which were based on the assumption that such touching is impossible, will be removed. Please, those who have done these hacks inform Gerald Agapov (Gerald).

We also apologize for the interuptions and problems with statements rendering.

Far from unanimous decision of the jury, it was decided to make this round rated. The rating will be recalculated on 26/11/2012 after removing of all relevant hacks.

Read more »

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

By KhaustovPavel, 6 years ago, In Russian,

Мы ждали этого, и это свершилось. В Новосибирске стартует онсайт элитного соревнования по программированию «Всесибирская олимпиада по программированию им. И.В. Поттосина». Миллионы взглядов прикованы к этому сверхзнаменательному событию.

Уже сегодня лучшие команды России и стран СНГ будут сражаться за престижное звание победителя Всесибирской олимпиады по программированию.

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

Read more »

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

By KhaustovPavel, 8 years ago, In Russian,
В последнее время для меня все актуальнее становится вопрос о том, какими же все-таки должны быть условия задач? Что должно содержаться в этих условиях и как это правильно сформулировать? Как избежать хотя бы малейшей двусмысленности?
При создании контеста я всегда считал составление условия самой сложной задачей. Всегда старался избегать написания условий задач, в которых нельзя обойтись коротким и понятным условием. Если при разработке контеста я читаю чужое условие, то я стараюсь максимально придраться к нему, чтобы ни у кого из участников не возникло ни малейшей двусмысленности. Я иногда рефлекторно защищаю свои (порой изначально двусмысленные) формулировки. Но, как только немного остываю, сажусь и стараюсь исправить все замечания до последнего. А после того, как исправляю, спрашиваю стало ли понятно теперь.
Часто бывает так, что ужасно хочется приплести к условию задачи какую-то жутко забавную легеду или, как зачастую кажется авторам, подходящую как нельзя кстати именно к этой задаче. При написании условия задачи надо всегда помнить, что легенда может увести участника от самой сути задачи настолько далеко, что лучше бы ему просто увидеть примитивное условие на языке математических обозначений. Часто легенды плохо согласуются с оригинальным пониманием условия, что сбивает с толку и заставляет участника непроизвольно додумывать какие-то дополнительные ограничения.
Если участнику непонятно какое-то обозначение из условия или как в примере получается именно такой ответ, то всегда можно написать примечание, которое снимет все вопросы. Тем не менее, примечание должно быть лишь вспомогательной составляющей условия. Условие без примечания не должно быть неполным и должно содержать все необходимые ограничения.
Очень важно заранее увидеть страницу, которую будет видеть участник. Некоторые важные элементы условия могут оказаться незаметны в конечном итоге из-за своего геометрического положения на листе бумаги или на экране монитора.
Важных пунктов при составлении условия - великое множество. Сложно перечислить все важные пункты, да я и не буду пытаться перечислить их все. Более того, всех пунктов я, наверное, и не знаю.
Всю эту тему я решил поднять из-за недавнего спора с одним программистом (если захочет, сам назовет себя) на тему того почему же я изначально неправильно понял условие задачи, которую мне недавно довелось порешать. Я погорячился и даже написал автору задачи (в индивидуальном порядке), что это условие написано некачественно. Лишняя агрессивность была вызвана тем, что я позорно слил этот раунд, и во мне бурлил негатив. Эту задачу я все-таки сдал во время раунда, но потратил на нее намного больше времени, чем потребовалось бы, если бы я изначально правильно понял формулировку. Спасибо тем, кто отвечал на вопросы, за то, что пояснили тест из примера. Это дало мне все-таки понять ту самую формулировку, которую подразумевал автор.
Для начала я полностью поясню ситуацию... Когда я прочитал условие, то сразу же обратил внимание на следующее предложение: "...Ктулху назовем такой неориентированный граф, который может быть представлен как набор из трех или более корневых деревьев, корни которых соединены простым циклом...". Я подумал, что конечно-же имеется в виду цикл, состоящий из трех и более вершин. Но зачем вот это "трех или более". "А! Наверное подразумеваются только деревья, состоящие из более, чем одной вершины" - подумал я. "Ну да, все логично! У Ктулху такая морда с висящими из нее штуками. Менее трех таких болтающихся из морды штук у Ктулху - не православно, вот отсюда и такое ограничение!" - вот, что я подумал следом и принялся набивать код решения именно такой задачи. Написав, я заметил, что на тесте из примера мое решение выдает не такой ответ. И действительно, если удалить цикл из него, то остается только два дерева. И тут в голове начинаю перебирать как же надо понимать условие: Может быть можно считать поддеревья отдельными деревьями? Может быть можно считать одинокую вершину тоже деревом? Я задаю вопрос жюри и свет проливается. Причем ответ был очень подробным пояснением, откуда же берется три дерева в тесте из примера. Да, теперь задача действительно решается одним дфс-ом, подумал я. В моем решении я просто убрал if на то, чтобы деревьев с количеством вершин больше 1 было не менее трех и отправил. Больше я к этой задаче не возвращался.
Позже, все кому я говорил о том, как много времени я потерял на этой задаче (таких было не так уж и много) тыкали меня носом в различные вещи. Кто-то в то, что я не додумал условие из теста из примера. А между делом, он и сам обратился к тесту из примера, чтобы разобраться. Кто-то винил меня в том, что я не прочитал примечание, а, соответственно, прочитал не все условие.
Лично я считаю, что условие должно быть таким, чтобы не требовалось разбираться в тесте из примера, чтобы понять, что же от меня требуется. А о существовании примечания я и знать не знал. Видимо, авторы не заметили того, что оно находится под двумя огромными тестами. А по скроллбару сложно ориентироваться, ведь в условии находится еще огромная (но не самая полезная) картинка. Как выяснилось, пояснение того, что дерево из одной вершины все же надо учитывать, находилось именно в примечании. А условие про "трех и более" означало тривиальный для меня факт того, что циклы не могут содержать менее трех вершин.
Человек, с которым я спорил, утверждает, что и без примечания все понятно и однозначно. Этот человек решил эту задачу, не задавая вопросов жюри, то есть понял с первого раза условие правильно. Именно он сказал, что я [начало цитаты] не полностью прочитал условие [конец цитаты].
Как мне показалось, ответ, который дали мне, был использован и ранее. Я могу ошибаться, но по-моему я не единственный из тех, кто задал такой вопрос.
И тут, собственно, остается много вопросов, по которым я бы хотел услышать мнение общества:
1) Было ли условие (без учета примечания) однозначным для понимания для Вас?
2) Можно ли выносить то самое ограничение на количество вершин в корневом дереве в примечание или же это часть условия? (опять же относительно Вашего мнения)
3) Достаточно ли заметны для Вас примечания под "примерами тестов" при больших высоте страницы и размерах этих самых примеров?

Read more »

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

By KhaustovPavel, 8 years ago, In Russian,
Кто-то участвует в Петрозаводских сборах, кто-то просто следит за ходом этих сборов, а кто-то участвует в зеркале этих сборов в славном городе Ижевске. Сборы проводит замечательный и достаточно титулованный в области олимпиадного программирования Ижевский государственный технический университет (ИжГТУ). Эти сборы проводились уже в седьмой раз и, сдается мне, что тем, кто на них не был недостаточно известно о них.
В этом отчете я постараюсь осветить все аспекты сборов. И, для начала, расскажу как попасть на эти сборы и зачем это нужно.

Read more »

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

By KhaustovPavel, 8 years ago, In Russian,
Задача А. Бар
Ответом на задачу является количество посетителей, которые удовлетворяют одному из предложенных ограничений:
1) Указан возраст посетителя и он меньше 18 лет
2) Указан напиток посетителя и он является алкогольным
Далее остается аккуратная реализация.

Задача B. Испорченная перестановка
Задача имеет множество решений. В разборе будет расказанно решение с асимптотикой O(N), где N - количество элементов последовательности.
Найдем такое наименьшее i, такое что Ai не равно i (элементы нумеруются с единицы). Если такого i не существует, то все числа стоят на своих местах и, соответственно, ответом являются два нуля. Иначе, предполагаем, что ответом являются числа i и Ai (мы можем быть точно уверены, что i < Ai). Переворачиваем подпоследовательность элементов с i-ого по Ai-ый и проверяем всю полученную последовательность на то, везде ли Ai равно i. Если да, то ответом является пара (i, Ai), иначе ответ - два нуля.

Задача C. Почта в корпорации
Для решения задачи вполне подходит решение за O(N2L), где N - количество людей в иерархии, а L - средняя длина имени сотрудника. То есть сравнение строк можно выполнять без использования хэш-функции.
Первая часть решения - аккуратная реализация примитивного парсинга строки. Наиболее простой способ - рекурсивная функция, которая читает сначала имя сотрудника, а потом и всех его подчиненных до тех пор, пока не достигнет точки. Далее потребуется хранить в памяти дерево из N вершин. Хранение дерева можно организовать как с помощью динамической памяти, так и простой матрицей смежности. Далее можно просто для каждой вершины запустить обход в глубину из нее и посмотреть скольким вершинам в этом поддереве сопоставлено такое же имя. Стоит обратить внимание на то, что сама вершина, из которой изначально запускается обход в глубину, не должна быть посчитана в ответ.
Такое решение можно улучшить до сложности O(NlogN), используя хэширование и более сложные структуры данных (например map). При данных ограничениях это было бы пустой тратой времени. Даже грубой оценки N < 500 достаточно, чтобы решение уложилось в time limit.

Задача D. Получаем строку
Наиболее простым решением этой задачи является решение с использованием динамического программирования. Обозначим первую строку за A, а вторую за B. Длина первой строки равна N, а второй - M. Тогда решение имеет асимптотику O(NM).
Обозначим за S(i, j) - подстроку строки S с i-ого по j-ый символ.
Введем функцию F(x, y) - сколько минимум действий надо выполнить, чтобы из подстроки A(x, N - 1) получить подстроку B(y, M - 1) (индексы символов нумеруются с нуля). Тогда значание F(x, y) это минимум из:
F(x + 1, y + 1), при x < N, y < M и A[x] = B[x]
F(x + 1, y + 1) + 1, при x < N, y < M
F(x + 1, y), при x < N
F(x, y + 1), при y < M
Очевидно, что F(N, M) равно нулю.
Если при обработке очередного перехода не только обновлять значение функции, но и запоминать тип перехода, то по окончании подсчета функции F(0, 0) можно будет восстановить набор необходимых операций для превращения строки A в строку B. Ну а само значение F(0, 0) и будет искомым ответом.

Задача E. Принцип домино
Задача вполне может иметь множество решений, но в данном разборе будет рассказано одно из наиболее тривиальных.
Для начала отсортируем все доминошки по координате x слева направо, запомнив изначальную нумерацию. Эта нумерация потребуется только для вывода ответа в правильном порядке. Далее нужно сформулировать несколько тривиальных утверждений:
1) Если толкнуть какую-либо доминошку вправо, то среди упавших доминошек все (кроме самой доминошки) будут находиться справа от той, что толкнули.
2) Если какая-либо доминошка упала, то упали и все доминошки, которые находятся левее этой, но не левее той, что изначально толкнули.
3) Для каждой доминошки можно определить номер наиболее правой доминошки такой, что она упадет, если толкнуть данную.
Обозначим за F(i) номер наиболее правой доминошки, которая упадет, если толкнуть i-ую доминошку. Сама по себе i-ая доминошка может не упасть на F(i)-ую, но из-за "принципа домино" F(i)-ая все же упадет. Если доминошка при падении вообще не задевает никакую другую доминошку, то F(i) = i. Очевидно, что такое равенство выполняется для самой правой доминошки. Для остальных доминошек можно найти значение F(i) с помощью уже найденных F(j), где j > i.
Для каждой доминошки с номером i можно найти такую доминошку с номером j, что при падении i-ая повалит j-ую (непосредственно), и такое j максимально. То есть найти самую правую из доминошек, которую повалит непосредственно i-ая. Далее F(i) = max(F(k)), где k принимает значения на интервале [i + 1, j].
Реализация решения с асимптотикой O(N2) точно не влезет в ограничения по времени. Поэтому необходимо написать решение как минимум за O(NlogN), для чего достаточно воспользоваться структурой данных типа дерева интервалов. Короче говоря, решить задачу Range Maximum Query.

Read more »

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

By KhaustovPavel, 8 years ago, In Russian,
Задача A. Футбол
Классическая задача A второго дивизиона. Можно было решить без хранения в памяти всех N строк входного файла. Хотя тесты проходило и любое решение, которое только можно себе представить.
Решение без сохранения всех N строк в памяти: считывать все строки, при встрече незнакомой строки присваивать ей идентификатор. Для каждого идентификатора завести счетчик, который будет отражать, сколько раз строка встретилось во входном файле. Из двух строк выбрать ту, у которой значение счетчика больше.

Задача B. Письмо
Самое простое решение - это для каждой буквы (другие символы просто игнорировать) в обеих строках посчитать число ее вхождений. Если какая-то буква входит во вторую строку большее число раз, чем входит в первую, ответ "NO", иначе ответ "YES". Очевидная асимптотика решения O(L), где L - ограничение на длину строки во входном файле.

Задача С. Счастливые билеты
Всем известно условие делимости числа на 3: "Число кратно трем, тогда и только тогда, когда сумма цифр этого числа делится без остатка на 3". Соответственно, чтобы при склеивании двух чисел получить число кратное трем, необходим чтобы сумма цифр первого числа плюс сумма цифр второго числа было кратно трем.
Стоит отметить, что оперировать в условиях этой задачи можно только с остатками от деления на 3. Несложно понять, что есть смысл соединять числа, которые дают в остатке от деления на 3 двойку с теми, кто дает в остатке единицу. Числа, которые нацело делятся на 3 можно объединять только с числами, которые так же делятся нацело на 3. Если посчитать количество чисел на кусках билетов с остатком от деления на 3 равным 0, 1, 2 (обозначим их как R0, R1, R2 соответственно), то ответом будет min(R1, R2) + [R0 / 2]. Здесь [] - операция округления в меньшую сторону.

Задача D. Путешествие
Задача не требует знания каких-то алгоритмов, математики или даже банальной логики. От Вас требуется найти все частные случаи и не забыть рассмотреть каждый из них.
Теста "1 1" быть не могло (ограничения такие).
Для тестов "1 2" и "2 1" ответом служит последовательность из трех клеток (1 1, оставшаяся клетка, 1 1). Телепортов не требуется.
Для тестов "1 M" и "N 1" (2 < N, M) ответом служит последовательность 1 1 -> 1 2 -> ... -> 1 M (ну и аналогично для перевернутого случая) и снова 1 1 в конце. Требуется один телепорт (1 M -> 1 1).
Далее логика простая. Если хотя бы одна из сторон - четная, то пройти можно следующим алгоритмом:
Рассмотрим случай, когда количество строк нечетно. При нечетном количестве столбцов можно действовать так же, поменяв строки и столбцы местами.
Из клетки 1 1 шагнем в 1 2 и далее пойдем змейкой по прямоугольнику Rect(1, 2, N, M). То есть во время обхода змейкой не посещаем первую строку. Такой обход закончится в клетке с координатами 2 M. После чего можно шагнуть на 1 M и спокойно прийти по первой строке в 1 1.
Для случая, когда N и M четные, можно воспользоваться тем же алгоритмом. Очевидно, что телепортов строить во всех этих случая не потребуется.
Для случая, когда N и M нечетные всегда потребуется один телепорт. Если действовать по той же стратегии, то в конце обхода змейкой можно попасть только в клетку с координатами N M, откуда необходимо телепортироваться в клетку 1 M и пройтись по первой строке до клетки 1 1.

Задача E. Гонка
Задача не требует знания каких-то сложных формул из физики. Сразу открою занавесу и выпишу все формулы, которые потребуются при решении.
X0 = 0
Xn + 1 = Xn + Vn (Tn+1 - Tn), где Xi - координата, Ti - момент времени
Несложно понять, что решение с асимптотикой O(SN2) получит заслуженный Time Limit. Решение с асимптотикой O(KN3) вполне сойдет. Впрочем, скорее всего существует решение с гораздо более хорошей трудоемкостью.
Далее будет рассказано решение за O(KN3), которое имеет множество других достоинств.
Будем рассматривать всю гонку, как набор некоторых событий упорядоченных во времени. События - изменение скорости какого-либо участника в какой-либо момент времени. Для каждого участника несложно (еще при чтении) получить все события, которые с ним связаны. Каждое из них обладает двумя параметрами: время, когда была сменена скорость и сама величина скорости. Все события можно объединить и упорядочить хронологически (в порядке неубывания времени, когда происходит событие).
Теперь нет смысла идти по всем моментам времени (от 0 до S). Есть смысл рассматривать только моменты времени, в которые происходит хотя бы одно событие. Всего смен скоростей будет O(NK). Для дальнейшего решения можно сделать несколько утверждений:
Между двумя соседними моментами времени (в которые происходят события) скорости автомобилей остаются постоянными. Соответственно, автомобиль i обгонит на участке между этими двумя моментами времени автомобиль j если Vi > Vj (иначе обгон точно не возможен). А далее требуется соблюдение одного из двух условий:
  • Координата автомобиля i в первый момент времени меньше, чем у автомобиля j, а во второй момент времени координата автомобила i уже больше координаты автомобиля j.
  • Координата автомобиля i в первый момент времени такая же, как у автомобиля j, а во второй момент координата автомобиля i больше координаты автомобиля j. При этом на предыдущем этапе координата автомобиля i была меньше (то есть он сравнялся с автомобилем j на прошлом интервале времени).
На каждом временном интервале можно за O(N2) проверять для каждой пары (i, j) обгоняет ли автомобиль i автомобиль j.
Каждое из вышеописанных условий можно проверить в целых числах (32 бита вполне хватает). Ответ так же не потребует 64-битовой переменной.
Стоит отметить, что решение не использует значение S, которое дается во входном файле.  Дописав один IF можно получить решение, которое будет правильно обрабатывать даже случаи, когда автомобили некоторое время ехали бок о бок.

Read more »

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