NALP's blog

By NALP, 6 years ago, In English,

Hello everyone,

I guess almost everyone knows that the ICPC Challenge takes place every year before the ICPC World Finals. Of course, this year isn’t an exception. If someone doesn't know, the ICPC Challenge is an additional AI-contest for the ICPC finalists where they have two weeks to solve a single game problem. After that, a double-elimination tournament will be held between the team's submissions. The results will be announced at the Finals.

The ICPC Challenge 2013 has started several days ago (on the 3th of June, to be exact) and I want to solemnly declare that this year ICPC Challenge has been prepared by the team from Baylor University, North Carolina State University and Saratov State University, which I represent! We introduce you a new game called CodeRunner.

About the Game

The 2013 ICPC Challenge game, CodeRunner, has a playing field that looks something like the following figure. A red player and a blue player compete to collect gold, while avoiding several enemies that are moving around the map. Each player directly controls a single runner character, who can move left and right, climb up and down ladders and break temporary holes in the floor with a large hammer. In addition to collecting gold, the players earn points by exploring the map and trapping enemies and their opponent in holes.

Surprise

But the point of my speech is that everyone can compete in the challenge this year! In addition to the regular ICPC Challenge, a contest among ICPC World Finalist teams, we are running a new competition called the Open ICPC Challenge. This competition invites any competitive programmers worldwide to compete head-to-head on the same programming problem as the 2013 ICPC World Finalists.

You can find more information here and here.

We invite everyone to take part in this event!

Good luck and have fun!

Read more »

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

By NALP, 6 years ago, In Russian,

279A - Point on Spiral

Из-за небольших ограничений в данной задаче можно было просто промоделировать шаги коня. Удобнее всего это делать, храня текущее направление движения и счетчик со значением, сколько шагов в эту сторону осталось. Заметим, что конь движется по спирали по следующему шаблону: 1 шаг вперед, поворот, 1 шаг вперед, поворот, 2 шага, поворот, 2 шага, поворот, 3 шага, поворот, 3 шага, поворот, 4 шага и так далее.

279B - Books

При решении этой задачи проще всего было воспользоваться методом двух указателей: левый указатель означает начало отрезка, правый — конец. При передвижении левого указателя на единицу вправо, правый надо двигать до тех пор, пока сумма ai внутри отрезка меньше или равна t. Так мы сможем для каждого левого конца найти максимально удаленный правый, а ответ на задачу — это максимальная длина из этих отрезков.

279C - Ladder

Давайте перед выполнением запросов выпишем в массив down отдельно все позиции i, для которых ai > ai + 1, и в массив up такие позиции i, такие что ai < ai + 1.

Теперь заметим важный факт для решения: отрезок [l, r] является лесенкой тогда, когда все позиции i, где ai < ai + 1 левее всех позиций j, в которых aj > aj + 1 (l ≤ i, j < r).

Для того, чтобы проверить это условие, давайте воспользуемся массивами up и down, в них с помощью бинарного поиска можно надо найти наибольший индекс i в отрезке, где происходит возрастание, и наименьший индекс j в отрезке, где происходит убывание, и если i < j, то отрезок — это лесенка. Отдельно необходимо рассмотреть случаи, когда числа в отрезке образуют невозрастающую или неубывающую последовательность.

279D - The Minimum Number of Variables

Давайте решать задачу методом динамического программирования по бинарной маске. Пусть текущее состояние — это mask. Через count(mask) обозначим количество единичных битов в маске, а через b1, b2, ..., bcount(mask) их индексы (здесь и далее будем использовать 0-нумерацию).

Наше состояние означает, что в данный момент у нас имеется count(mask) переменных, которые равны ab1, ab2, ..., abcount(mask). Будем считать, что дойдя до такого состояния, мы уже сумели произвести count(mask) операций, а значит, сейчас нам надо получить x = abcount(mask) + 1.

Если это число x не представимо в виде x = bi + bj, то тогда точно следующее значение мы получить не можем, и это состояние тупиковое, а иначе даже неважно какие именно значения i, j мы возьмем, главное — убедиться, что такие существуют.

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

В терминах масок первая операция выглядит как выкидывание одного из битов bk, и добавление нового бита, а вторая — просто добавление нового бита.

Начальное состояние в нашей динамике — это mask = 1, конечное — любая маска, в которой есть единичный бит на позиции n - 1 (в 0-нумерации).

При аккуратной реализации такое решение будет работать за O(2n·n). В частности, следующий хитрый прием поможет добиться этого: когда нам требуется проверить, что в маске есть такие два бита bi и bj, что acount(mask) = abi + abj, то будем использовать предподсчитанный массив diff[q][p], в котором будет записан индекс такого элемента массива a, который равен разности aqap.

Это позволит нам при проверке перебирать лишь значение bi.

279E - Beautiful Decomposition

Будет опубликовано чуть позже…

Read more »

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

By NALP, 6 years ago, In Russian,

257A - Sockets

Очевидно, что выгоднее использовать сетевые фильтры с наибольшим количеством розеток на них. Поэтому сначала отсортируем их по убыванию этой величины. Теперь переберем ответ, то есть, сколько фильтров мы будем использовать, пусть это значение равно p, а фильтры имеют a1, a2, ..., ap розеток. Очевидно, что если соединить эти фильтры, то итого будет доступно k - p + a1 + a2 + ... + ap розеток. Это значение надо сравнить с m и выбрать минимальное подходящее p. Если ни одно значение p не подходит, то следует вывести  - 1.

257B - Playing Cubes

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

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

257C - View Angle

Сначала давайте избавимся от координат точек, а именно, заменим все точки лучами от (0, 0) до каждой из точек.

Тогда очевидно, что искомые стороны угла – это пара соседних лучей, причем из двух углов, образованных выбранными лучами, надо выбрать тот, который покрывает все остальные лучи. Получается, что выгоднее всего выбрать такую пару соседних лучей, между которыми наибольший угол, пусть он равен a, и вывести величину 360 - a (в градусах).

Отдельный случай — когда все точки лежат на одном луче, в этом случае ответ равен 0.

257D - Sum

У нас есть последовательность переменных a1, a2, …, an. Возьмем две переменные с максимальными значениеми (допустим, i и i + 1), удалим их и вставим в последовательность новую переменную x = ai + 1 - ai так, чтобы сохранилось свойство неубывания последовательности. Так будем делать до тех пор, пока не останется единственное число s, которое и будет искомой суммой. Очевидно, что если мы будем разворачивать последовательность замен с учетом знаков, то в итоге узнаем, какой знак стоит у каждой из начальных переменных так, чтобы их сумма была равна s.

Теперь осталось понять, почему число s подходит под ограничения 0 ≤ s ≤ a1. Очевидно, что оно не может быть отрицательным, так как при всех заменах мы из большего числа вычитаем меньшее. Также несложно понять, что при всех заменах минимальное число в последовательности не может увеличиваться, значит, оно до последней замены будет максимум a1. Аналогично, второе число в последовательности также не может перед последним шагом быть больше a2 и так далее. Несложно понять, что при последней замене мы получим s ≤ a2 - a1 ≤ a1.

257E - Greedy Elevator

Эта задача решается классическим методом – событиями во времени. Событиями являются: «человек встал в очередь к лифту», «человек вошел в лифт», «человек вышел из лифта».

Будем поддерживать множество будущих событий, текущее время T и текущее положение лифта x.

В каждый момент времени будем выполнять следующие действия:

  1. если есть люди, которые в текущее время T пришли к лифту, то поставим их в очередь на их стартовом этаже;
  2. если на текущем этаже есть люди, то посадим их в лифт, таким образом очередь на этом этаже опустеет;
  3. если в лифте есть люди, которые должны выйти на текущем этаже, то высадим их и запомним для них ответ – текущее время T;
  4. найдем количество людей, которые ждут выше этажа x или которые едут выше, а также найдем количество людей, которые ждут ниже этажа x или едут ниже, и согласно условию выберем направление движения.

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

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

Это можно сделать с помощью структуры «множество» с операциями «найти следующее число в множестве после данного» и «найти предыдущее число в множестве перед данным». Это умеет стандартные структуры set в С++ или TreeSet в Java.

Также для действия номер 4 нам понадобятся две структуры данных, которые умеют находить сумму чисел на определенном отрезке в массиве, для этого можно использовать, например, деревья отрезков или деревья Фенвика. Одна из структур хранит, сколько людей ждут лифта на каждом из этажей, а вторая – сколько людей в лифте хочет выйти на каждом из этажей. В принципе, эти две структуры можно объединить в одну.

Таким образом, для каждого из людей мы будем обрабатывать ровно по три события, и итоговое время решения будет равно O(n·log(n)).

Read more »

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

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

Hi to all!

A few hours later you're lucky to participate in Codeforces Round #159 for Div.2 participants, but traditionally the others can take part out of the competition. It has been prepared by me (NALP), Ivan Fefer (Fefer_Ivan), Pavel Holkin (HolkinPV), Vitaly Aksenov (Aksenov239) and Gerald Agapov (Gerald). Also we express thanks to Mary Belova (Delinur) and Mike Mirzayanov (MikeMirzayanov).

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

UPD: Today it is decided to use dynamic scoring system. But the problems will be sorted from low difficulty to high by authors' opinion!

UPD: The contest finishes, congratulations to the winners!

1.Leonidas

2.CarlyPlus

3.Dakurels

4.ytqiaqia

5.SuccessfulHackingAttempt

Read more »

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

By NALP, 7 years ago, translation, In English,

242A - Heads or Tails

This problem was very easy, we should only use two cycles with i and with j (a ≤ i ≤ x, b ≤ j ≤ y), iterate all possible outcomes of the game and print such in that i > j. The time is O(x·y).

242B - Big Segment

At first, we must note that the answer is always unique, because if segment i covers segment j, that segment j can't cover segment i. It possible if and only if there are coincide segments in the set, but it's not permissible by the statement. Let's pay attention the answer covers the most left point of all segments and the most right point of all points too. Now then we should found L = min(li) and R = max(ri) and print index of segment [L, R], or  - 1 if there is no such segment in the set. The time is O(n).

242C - King's Path

The most important thing for accepted solution is that it is guaranteed that the total length of all given segments doesn't exceed 105. We should use this feature, let's number allowed cells and found shortest path by BFS. It's easiest to use associative array such as map in C++ for numbering. The time is O(n·log(n)).

242D - Dispute

Denote current value of counter number i as bi. Let's describe an algorithm. It takes any counter i such that bi = ai and presses its button. The algorithm finishes if there is no such i.

Let's proof correctness of the algorithm:

  1. Why does Valera win the game? Because there is no such counter which has bi = ai else we must press the button.

  2. Why doesn't algorithm press some button multiple times? Because it presses button number i only if bi = ai, and after this pressing the value bi is increased and the equation will be true never.

  3. Why is the algorithm fast? Because of paragraph 2 it does no more n pressings which produces no more n + 2·m increases of the counters. We should use queue for fast seaching counters which has bi = ai like this: every time we change value of the counter numbered i we check equation bi = ai and if it's true then we push value i to the queue. It's easy to understand that all indexes i will be in queue no more one time.

Also these paragraphs proof that the answer always exists. You must print  - 1 never. The time is O(n + m).

242E - XOR on Segment

Let's write numbers a1, a2, ..., an as a table which has size n × 20, and bi, j is jth bit in ai. Then sum of numbers on segment [l, r] equals . The last notation helps us to process queries.

For fast implementation we should use 20 binary trees like cartesian trees or range trees. Every tree matchs one of bits (and matchs one of the columns of the table bi, j).

  1. calculation of sum is equal to counting 1-s from l-th to r-th.

  2. operation "xor" equals reversing all bits from l-th to r-th (i.e. 0 changes to 1, 1 changes to 0).

The first operation executes for all bit numbers, the second executes only for bits in which input number xi has ones.

These operations may be easy implemented with binary trees. The time is O(m·log(n)·20).

Read more »

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

By NALP, 7 years ago, translation, In English,

Hi to all!

A few hours later you're lucky to participate in Codeforces Round #149 for Div.2 participants, but traditionally the others can take part out of the competition. It has been prepared by me (NALP), Igor Kudryashov (KudryashovIA), Pavel Holkin (HolkinPV) and Gerald Agapov (Gerald). Also we express thanks to Mary Belova (Delinur) and Mike Mirzayanov (MikeMirzayanov).

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

The standart scoring system will be used: 500-1000-1500-2000-2500

UPD: The contest is over, thanks to all!

UPD: Congratulations to the winners:

  1. fio

  2. ballmaids00

  3. mihaipopa12

  4. Yukari

  5. chlxyd

UPD: the tutorial has been published.

Read more »

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

By NALP, 7 years ago, In Russian,

Привет!

Спешу поделиться с вами отличной новостью: с понедельника 29 октября 2012 года 00.00 часов по Московскому времени мы запускаем новое соревнование для программистов под названием Russian AI Cup 2012: CodeTanks! Но это будет не совсем обычное соревнование, так как в этот раз вам надо будет написать игровую стратегию и принять участие в танковом сражении.

Поучаствовать в этом мероприятии можно тут: http://russianaicup.ru

Что?

Russian AI Cup — это новый проект команды проекта “Одноклассники”, реализованный силами Mail.Ru Group и Саратовского Государственного Университета. Это соревнование — третье мероприятие компании Mail.Ru Group для талантливых IT-специалистов, ранее из этой серии мероприятий проводились Russian Code Cup и Russian Design Cup.

Где?

Заходите на http://russianaicup.ru и регистрируйтесь (мы рекомендуем для этого пользоваться аутентификацией для социальных сетей). Для участия в соревновании достаточно одной принятой посылки, и вы сразу попадете в рейтинг!

Когда?

  • Песочница: с 29 октября по 2 декабря;
  • Раунд 1: 10–11 ноября;
  • Раунд 2: 17–18 ноября;
  • Финал: 24–25 ноября.

А ништяки?

Конечно же, без них не обойдется :) Лучшие участники получат самые современные гаджеты в крутых комплектациях, среди которых MacBook Pro with Retina, MacBook Air, iPad и iPod.

Призы

Вау, как интересно, а можно поподробнее?

Подробнее вы можете прочитать на самом сайте http://russianaicup.ru, вот полезные ссылки:

Let’s have fun! :)

Read more »

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

By NALP, 7 years ago, In Russian,

Приветствую всех участников раунда!

237A - Free Cash

Из условия задачи легко понять, что если в некоторую минуту придут k человек, то Валере нужно иметь в кафе не менее k касс. Значит, требуется найти максимальное количество людей, которые придут в одну и ту же минуту, а это делается очень просто множеством способов, например, просто насчитав в массив cnt[h][m] количество людей, которые придут в час h и минуту m, а потом найдя в этом массиве максимум.

237B - Young Table

Решение, которое опишем ниже, почти никак не использует хитрую форму таблицы (кстати, такая таблица называется диаграммой Юнга). Заполним таблицу числами от 1 до s следующим способом: будем идти по строкам таблицы начиная с первой слева направо, после конца текущей строки переходим на начало следующей, и в процессе каждой из клеточек присвоим число по порядку обхода от 1 до s. Очень просто показать, что такой порядок чисел удовлетворяет оба неравенства из условия.

Теперь опишем алгоритм приведения таблицы из того вида, как она нам дана во входных данных, в описанный выше вид.

Возьмем число 1 и посмотрим, где оно находится в этих двух таблицах. Если это число стоит не на своем месте, то поставим его на свое место, соответственно то число, которое там стояло, встанет на старое место единицы. Аналогично сделаем для 2, 3, ..., s. Очевидно, что этот алгоритм сделает не более s шагов и приведет таблицу в вид, описанный в первом абзаце.

237C - Primes on Interval

Для начала с помощью решета Эратосфена выделим все простые числа от 1 до b и пометим их единичками в массиве d, то есть если p — простое, то d[p] = 1, иначе d[p] = 0.

Заметим, что если l — корректное число, то l + 1 тоже корректно. В самом деле, для позиций x от a до b - l количество простых в отрезке с началом в x могло лишь увеличиться (мы же длину отрезка увеличили, а значит, количество простых в нем никак не могло уменьшиться). А кроме того исчез из рассмотрения один отрезок с началом в точке b - l + 1, так как при увеличении длины его правый конец стал больше, чем число b.

Таким образом, мы показали, что функция f(l), возвращающая TRUE или FALSE (корректно число или нет) монотонна, а значит, мы можем с помощью бинарного поиска найти наименьшее l, для которого f(l) = TRUE, или ответить, что такого не существует.

Функция f(l) считается очень просто — можно проитерироваться по всем числам от a до b - l + 1 и найти для каждого начала количество простых чисел в соответствующем отрезке длины l, это можно сделать с помощью частичных сумм, насчитанных по массиву d.

237D - T-decomposition

Возьмем любое ребро начального графа, очевидно два его конца принадлежат некоторому множеству xi, значит, вес любой его Д-декомпозиции как минимум 2. Покажем, как постороить декомпозицию именно такого веса. Для этого каждое из ребер исходного графа превратим в отдельное множество xi, то есть все они будут состоять из двух элементов.

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

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

Несложно понять, что такой граф не будет содержать циклов, будет связен, а значит является деревом. Постоенная Д-декомпозиция будет иметь вес 2, и количество вершин n - 1.

237E - Build String

Эта задача несложно решается алгоритмом поиска максимального потока минимальной стоимости на трехслойном графе:

  1. первый слой состоит из n вершин, каждая из которых отвечает за свою строку из входных данных; в i-ую вершину этого слоя входит по одному ребру из истока с пропускной способностью ci и стоимостью i;

  2. второй стой состоит за 26·n вершин, каждая из которых отвечает за количество определенных букв в каждой из строк из входных данных; в вершины этого слоя входят ребра только из первого слоя стоимостью 0 и пропускной способностью равной количеству соответствующих букв в соответствующей строке;

  3. третий слой состоит из 26 вершин, каждая из которых отвечает за количество соответствующих букв в строке t; в вершины этого слоя входят ребра только из второго слоя стоимостью 0 и бесконечной пропускной способностью; кроме того, из вершин третьего слоя выходят ребра в сток стоимостью 0 и пропускной способностью, равной количеству соответствующих букв в строке t.

Если максимальный поток в этой сети меньше, чем |t|, то ответ равен  - 1, а иначе — минимальной стоимости максимального потока.

Read more »

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

By NALP, 7 years ago, translation, In English,

Hi!

A few hours later you're lucky to participate in Codeforces Round #147 for Div.2 participants, but traditionally the others can take part out of the competition. It has been prepared by me (NALP), Igor Kudryashov (KudryashovIA), Pavlik Holkin (HolkinPV), Gerald Agapov (Gerald), Mary Belova (Delinur) and Mike Mirzayanov (MikeMirzayanov).

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

The standart scoring system will be used: 500-1000-1500-2000-2500

UPD: The contest has ended, congratulations to the winners:

  1. try_skycn

  2. AntiKismet

  3. dianbei_03

  4. Uncia

  5. tourist2

Read more »

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

By NALP, 7 years ago, In Russian,

Тема интерактивных задач становится все популярнее, такие задачи каждый год встречаются на NEERC, иногда на этапах OpenCup и в других местах. Но все-таки на данный момент это непаханое поле, так как совсем немногие полноценно поддерживают инфраструктуру для тестирования подобных задач.

На Codeforces эту тему недавно поднимал MikeMirzayanov в своем посте. Вот цитата оттуда (**рекомендую прочитать этот пост для того, чтобы быть в курсе темы**):

Первый случай, первым завершилось решение:

  • Если завершилось по причине превышения каких-то ограничений, то сразу возвращаем вердикт Time Limit Exceeded, Memory Limit Exceeded или Idleness Limit Exceeded (последний, если программа продолжительное время вообще не расходовала процессорное время).
  • Если завершилось с кодом возврата неравным 0, то возвращаем Runtime Error.
  • Если завершилось благополучно и с кодом 0, то продолжаем ждать пока завершится интерактор.

Второй случай, первым завершился интерактор:

  • Если завершился по причине превышения каких-то ограничений, то сразу возвращаем вердикт Judgement Failed.
  • Если завершился с кодом возврата неравным 0, то обрабатываем его как обычный чекер:
  • код 1: возвращаем вердикт Wrong Answer,
  • код 2: возвращаем вердикт Wrong Answer (или Presentation Error, если такой вердикт поддерживается),
  • код 3 или любой другой: возвращаем Judgement Failed.

А теперь рассмотрим два очень даже вероятных случая:

  • Решение выводит интерактору какую-нибудь неадекватную информацию и ждет ответа. Интерактор понимает, что дальше невозможно продолжать протокол и кончает жизнь суицидом — завершается с вердиктом WA (ну или PE, если этот вердикт поддерживается). Таким образом он завершает потоки ввода-вывода со своей стороны, в частности stdin решения. Напоминаю, что решение в данном случае ждет ответа интерактора, но так как поток с его стороны завершен, у решения не получается считать ответ и оно падает с RE;

  • Второй вариант противоположен. Решение пытается что-то вывести интерактору, но в середине этого занятия падает с RE, завершая поток stdin интерактора со своей стороны. Однако что-то на этот момент все еще лежит в буфере, и интерактор это "что-то" читает, считает, что решение просто вывело ерунду и логично завершает работу с вердиктом WA или PE.

Эти две ситуации с точки зрения тестирующей системы абсолютно равны, так как решение падает с RE, а интерактор выносит вердикт WA. Но между ними есть большая разница в причине такого поведения, а именно, это Runtime Error или Wrong Answer решения. Эта ситуация лечится определением того, какой из процессов раньше завершился. Если первым упало решение, то это RE, а если первым упал интерактор, то это WA, и казалось бы проблем нет...

НО! Оказывается, что нельзя гарантированно определить порядок завершения процессов, то есть на то, что скажет ОС, полагаться нельзя!

Вот мы и пришли к концу повествования, а именно к вопросу: а как же определить истинную причину и сказать настоящий результат участнику? Разумеется, совершенно не хочется категорично менять инфраструктуру, описанную в посте MikeMirzayanov'а, хочется обойтись минимальными дополнениями в существующую модель.

Any ideas?

Read more »

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

By NALP, 7 years ago, In Russian,

Запускаем у себя следующий код:

#include <iostream>
using namespace std;
int main() {
    cout << "??-" << endl;
    return 0;
}

Фишка появляется в Visual C++ 2005, 2008. Кто знает почему так?

UPD: круто, что можно спросить тут что-нибудь, и ответ придет почти сразу :) Всем спасибо

Read more »

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

By NALP, 7 years ago, translation, In English,

Hi to all!

215A - Bicycle Chain

Because of small constraints we can iterate i from 1 to n, iterate j from 1 to m, check that bj divide ai and find max value of . Then we can start this process again and find amount of the pairs in which is max value.

215B - Olympic Medal

Let amagine we have values of r1, p1 and p2. Then:

r22·(B·p1 + A·p2) = r12·B·p1

Now it’s easy of understand, we must take maximum value of r1 and p1, and minimum value of p2 to maximize r2. You could not use three cycles for iterating all values, but you could find property above about at least one value and use two cycles.

215C - Crosses

Let’s iterate n1 = max(a, c) and m1 = max(b, d) — sides of bounding box. Then we can calculate value of function f(n1, m1, s), and add to the answer f(n1, m1, s)·(n - n1 + 1)·(m - m1 + 1), where two lastest brackets mean amount of placing this bounding box to a field n × m.

Now we must calculate f(n1, m1, s). At first, if n1·m1 = s then the result of the function is 2·(⌊ n1 / 2⌋ + 1)·(⌊ m1 / 2⌋ + 1) - 1 (you can prove it to youself).

If n1·m1 > s then we must to cut 4 corners which are equal rectangles with square . We can iterate length of a one of sides, calculate another side, check all constraints and add 2 to the result of the function for all such pairs of sides.

The time of a solution is O(n3), but it’s with very small constant, less then 1.

215D - Hot Days

You can use only two features about this problem: the solution is independenly for all regions and there are only 2 possible situations: all children are in exactly one bus or organizers must take minimum amount of bus such no children got a compensation. It’s bad idea to place some children to hot bus and to place some children to cool bus simultaneously.

For solving you must calculate this 2 values and get minimum.

215E - Periodical Numbers

Will be soon…

Read more »

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

By NALP, 7 years ago, translation, In English,

Hi!

A few hours later you're lucky to participate in Codeforces Round #132 for Div.2 participants, but traditionally the others can take part out of the competition. It has been prepared by me (NALP), Edvard Davtyan (homo_sapiens), Vitaly Aksenov (Aksenov239), Gerald Agapov (Gerald), Mary Belova (Delinur) и Mike Mirzayanov (MikeMirzayanov).

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

Especially, we want to wish grand results and good luck to all sportsmens, who are representing their countries on XXX Olympic Games in London!

Today it is decided to use dynamic scoring system. But the problems will be sorted from low difficulty to high by authors' opinion!

UPD: The Round is finished, thanks to all for participation! We hope you have got fun!

UPD: Congratulation to winners!

  1. yooo — solved all problems!

  2. zzy

  3. High_Rich_Handsome

  4. bookcity_clock

  5. capythm

UPD: Tutorial in English is published!

Read more »

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

By NALP, 7 years ago, In Russian,

Приветствую всех участников раунда!

203A - Two Problems

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

203B - Game on Paper

В этой задаче очевидно следующее тривиальное решение: после каждого хода нужно проверить, не появилось ли черного квадрата со стороной 3 на поле, но ограничения не позволяют так решать задачу. Однако заметим, что как только Вася закрашивает некоторую точку (x, y), то требуется проверить лишь 9 возможных кандидатов на черный квадрат, а остальные квадраты со стороной 3 не поменяют своей раскраски.

Таким образом, решение работает за O(m) с константой порядка 80 и требует O(n2) памяти.

203C - Photographer

Заметим, что если Вася хочет обслужить клиента номер i, то ему понадобится ровно f(i) = a·xi + b·yi мегабайт памяти на фотоаппарате. Также заметим, что так, как мы хотим максимизировать количество клиентов, то гораздо выгоднее брать тех, у кого величина f(i) меньше. Таким образом мы приходим к решению: сразу при чтении данных запомним для каждого клиента величину f(i), отсортируем всех клиентов по этой величине и будем обслуживать в порядке возрастания до тех пор, пока хватает памяти в фотоаппарате.

Время работы — O(n·log(n)).

203D - Hit Ball

Эта задача имеет два разных решения.

Решение 1. Будем последовательно двигаться по траектории мяча до тех пор, пока не влетим в поверхность двери. Для этого будем считать от каждой точки следующую точку, где текущий луч пересекает какое-либо препятствие (стена, дверь и так далее). Каждая точка на луче имеет вид (x + t·vx, y + t·vy, z + t·vz), где t > 0 — параметр. Подставим уравнения всех препятствий в этот вид и найдем минимальное t, а значит, и точку, где луч пересечет препятствие первый раз. Осталось только пересчитать vx, vy,vz и повторить процесс дальше до тех пор, пока мяч не влетит в дверь. Пересчитывать компоненты вектора скорости очень просто — при столкновении соотвествующую компоненту нужно просто умножить на  - 1.

Время работы такого решения — O(X2), где X — максимальная из координат мяча в начальный момент времени.

Решение 2. Как известно, траекторию отражения луча света от зеркала можно считать прямой, если отразить относительно зеркала все остальные объекты. Для уточнения приведем рисунок: на нем можно построить траекторию движения луча от точки A к точке B отразив точку в B в B' и нарисовав отрезок AB.

Аналогичную идею будем использовать в нашем решении. Каждую координату x или z будем находить независимо, рассмотрим для x, для z аналогично.

Допустим у нас нет стен, тогда мяч прилетел бы в точку с координатой . Теперь допустим x0 > 0, а стена представляет собой прямую x = a. Тогда мысленно отразим наш коридор (то есть полосу между прямыми x = 0 и x = a) несколько раз, то есть получим множество прямых x = ka, где пространство между соседними прямыми — это одно из отражений коридора.

Посмотрим, сколько раз отрезок между точками (a / 2, m) и (x0, 0) пересекал прямые, и в зависимости от четности можно понять, от какой стороны коридора последний раз отразился мяч, прежде чем попал в дверь. А сам ответ несложно найти отложив величину x0 (mod a) (где "mod" означает остаток от деления нацело) от соответствующей стены.

Таким образом, описанное решение позволяет найти ответ за O(1).

203E - Transportation

В этой задаче требуется рассмотреть два случая.

Первый — пусть все роботы едут самостоятельно. Тогда выделим множество роботов, у которых li ≥ d, отсортируем их по возрастанию количества требуемого горючего, и будем брать в этом порядке и отправлять в багажное отделение пока не кончится топливо. Этот случай похож на решение задачи C этого же раунда.

Второй случай рассматривает тех роботов, которые вкладывают друг в друга. Выделим множество роботов, у которых ci > 0, пусть из всего k штук, и пусть . Тогда несложно понять, что если мы всех этих роботов упакуем так, чтобы лишь из них ехало самостоятельно, а остальные были вложены в другие роботы, то еще у нас останется свободных слотов для других роботов.

Таким образом, выделим множество роботов у которых ci > 0, li ≥ d — то есть эти те роботы, которые могут везти других роботов и при этом могут самостоятельно добраться до багажного отделения.

Переберем, сколько из таких роботов на самом деле поедут своим ходом (не забываем про ограничения на топливо), и по формуле выше найдем количество свободных слотов. Заметим, что мы уже в любом случае отправили всех роботов, у которых ci > 0, а значит остались только те, у которых ci = 0, пусть таких всего num.

Каждый робот может иметь 3 состояния: он займет один из слотов, он поедет своим ходом, если у него li ≥ d и если хватит топлива, или он вообще не поедет.

Известно, сколько имеется слотов, а значит можно найти, сколько роботов или поедут своим ходом, или останутся, а точнее их . Таким образом, нам надо найти среди всех роботов с ci = 0 и li ≥ d максимальное количество роботов (но не более, чем g штук), на которых осталось достаточно топлива. Остальные роботы поедут на свободных слотах или останутся (их известное количество).

Эта подзадача решается предподсчетом величины f(i), означающую минимальное количество топлива, необходимое чтобы отправить i роботов среди тех, для которых выполняется ci = 0 и li ≥ d. По этой функции, очевидно, можно делать бинарный поиск.

Таким образом, соберем элементы решения: сначала переберем количество роботов, которые поедут своим ходом среди тех, у которых ci > 0, а затем с помощью бинарного поиска по предподсчитанной величине найдем, сколько роботов из оставшихся уместятся на свободные слоты, сколько поедут также своим ходом, а сколько останутся.

Не забудем про случай, когда вообще все роботы едут самостоятельно.

Мы получаем алгоритм, который можно реализовать за время O(n·log(n)).

Read more »

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

By NALP, 7 years ago, translation, In English,

Hello, friends!

A few hours later you're lucky to participate in this remarkable Codeforces Round #27 for Div. 21 participants, but traditionally the others can take part out of the competition.

It has been prepared by a small band of authors: me (NALP), Igor Kudryashov (KudryashovIA), and Pavel Kholkin (HolkinPV). There were Gerald Agapov (Gerald), Maria Belova (Delinur) and Mike Mirzayanov (MikeMirzayanov) with us as always.

It’s well-known that you can participate in this Round into competition only today! There won’t be another Codeforces Round #27!

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

UPD: Points are standard: 500, 1000, 1500, 2000, 2500.

UPD: Round is over, thanks to all! We hope you have got a fun. Don't forget, system testing will be soon.

Read more »

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

By NALP, 7 years ago, In Russian,

Приветствую всех участников раунда!

Давайте проведем разбор задач в примерном порядке их сложности

182B - Vasya's Calendar

Обратим внимание, что Вася должен вручную прибавлять номер дня только тогда, когда заканчивается один месяц, и начинается следующий. Значит, пусть у нас в текущем месяце было x дней, а в следующем уже y. Тогда в первый день следующего месяца часы будут показывать день x + 1 (не забываем про модуль d), а должен показывать номер 1.

Очевидно, что Вася должен вручную прибавить d - x дней, чтобы часы показывали то, что нужно.

Значит, ответ — это сумма всех чисел d - ai, где 1 ≤ i < n.

182D - Common Divisors

Эта задача решается многими способами, но самый простой подход следующий: найдем все делители строки s1, все делители s2 и найдем пересечение этих двух множеств.

Как же найти все делители строки? Пусть t — это делитель строки s. Тогда очевидно, что |s| = 0(mod|t|), а также t является префиксом строки s. Эти соображения и позволяют найти все делители строки, а именно переберем длину префикса, проверим делимость, а потом проверим, что префикс записанный подряд нужное количество раз совпадает с s.

Всего подходящих префиксов не более , проверка каждого работает за O(|s|), значит, итоговое решение за , где n = max(|s|, |t|).

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

182E - Wooden Fence

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

Основа решения этой задачи — это динамическое программирование.

Состояние — (last, type, l), где last — номер последней доски, type характеризует поворот последней доски, а l — длина оставшейся части забора.

Пересчитывать эту динамику тоже очень просто: переберем номер следующей доски, ее поворот, проверим подходит ли она в текущее состояние, и прибавим нужную величину.

Асимпотика решения — O(n2·len).

182C - Optimal Sum

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

Пусть мы зафиксировали положения окошка, теперь посчитаем ответ. Для этого отдельно запишем все положительные и все отрицательные числа в окошке. Если положительных не больше, чем k, или отрицательных не больше k, то мы можем все числа сделать одинакового знака, и ответ — это сумма модулей чисел в подмассиве. Это простой случай.

Несложно понять, что невыгодно некоторые отрицательные числа делать положительными и одновременно некоторые положительные — отрицательными. То есть мы обязательно выберем знак <<+>> или <<->> и k чисел этого знака сделаем противоположными. Также несложно понять, что всегда при смене знака у некоторых чисел выгодно брать ровно k максимальных по модулю чисел этого знака.

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

Если в вершине дерева хранить пару (количество чисел в поддереве, сумма этих чисел), то такая структура умеет возвращать сумму k максимальных чисел, что нам и требуется.

Асимптотика решения — O(n·log(n)).

182A - Battlefield

В этой задаче есть два главных момента:

  1. длина любой траншеи в метрах численно не превосходит b

  2. траншеи не пересекаются

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

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

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

Два тонких момента:

  1. мы не можем перебегать между траншеями, если между ними расстояние больше a

  2. пусть Вася прибежал в момент времени t, теперь нам нужно найти момент, когда он сможет убежать дальше. Для этого нужно найти следующий момент времени, когда лазер будет перезаряжаться. Эта величина T несложно ищется по формуле:

Асимптотика решения — O(n2).

Read more »

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

By NALP, 7 years ago, translation, In English,

Dear friends!

The next competition — Codeforces Round 112 for participants Div. 2 will take place through a pair of hours, but the others can traditionally participate out of competition. It has been prepared by a small command of authors: me (NALP), Artem Rakhov (RAD) and Pavel Holkin (HolkinPV). There were Gerald Agapov (Gerald), Maria Belova (Delinur) and Michael Mirzayanov (MikeMirzayanov) with us as always.

Especially I would like to wish good luck to my teammates Artem Rakhov and Max Ivanov (e-maxx) who recently flew to the U.S. to participate in Onsite Round Facebook HackerCup.

We hope that this problems will be pleasant to all participants and everyone will take the deserved high place in the standings :)

UPD: The contest is over, thanks to all for taking part :) We hope you have fun.

UPD: You can find the tutorial here http://codeforces.ru/blog/entry/4124

UPD: Congratulations to the winners!

  1. Miriam

  2. woshisb

  3. Senjougahara_Hitagi

  4. KotonohaKatsura

  5. pqxdcel

  6. UranusX

  7. QDkAc

You can see the full standings here: http://codeforces.ru/contest/165/standings

Read more »

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

By NALP, 7 years ago, In Russian,

160A - Twins

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

160B - Unlucky Ticket

Запишем в массив a первые n цифр, а в массив b — последние n цифр, и отсортируем эти массивы. Нетрудно понять, что если для всех i выполняется a[i] < b[i], или для всех i выполняется a[i] > b[i], то билет точно является несчастливым. Но также нетрудно понять, что для любого несчастливого билета выполняется или первое условие, или второе. Таким образом, мы придумали критерий несчастливости, можно реализовать за время O(n·log(n)).

160C - Find Pair

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

Пусть число k и массив a заданы в 0-нумерации, а сам массив отсортируем. Тогда если все числа различны, то очевидный ответ – это пара (a[k / n], a[k % n]), где операция % означает остаток по модулю. Однако, если в массиве есть повторяющиеся числа, то ситуация становится немного хитрее, рассмотрим пример: пусть дан массив (1, 1, 2, 2), тогда пары записаны следующим образом: (1, 1), (1, 1), (1, 1), (1, 1), (1, 2), (1, 2), (1, 2), (1, 2), (2, 1), (2, 1), (2, 1), (2, 1), (2, 2), (2, 2), (2, 2), (2, 2), каждая пара учитывается и никуда не девается, всегда рассматриваются ровно n2 пар чисел.

По-прежнему верно, что первое число – это a[k / n]. А второе число – это a[(kn·cnt) / num], где cnt – количество чисел в массиве строго меньших, чем a[k / n], а num – количество чисел в массиве, которые равны a[k / n].

В этой формуле несложно убедиться, рассмотрев пару примеров с повторяющимися элементами. В крайнем случае, можно написать тривиальное решение за O(n2·log(n)) и убедиться, что вы правильно придумали формулу.

P. S. Претест 3 имеет вид: в массиве (1, 1, 2) нужно найти 3-ю по лексикографичности пару. Она равна (1, 1).

160D - Edges in MST

Во-первых, разберем случай, когда все веса одинаковы. Тогда очевидно, что любое ребро может быть в дереве, но в случае, если ребро – мост, то оно является единственным способом соединить две компоненты, а значит, оно принадлежит любому MST. Итак, для мостов ответ равен «any», а для всех остальных – «at least one».

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

А значит, мы можем решать задачу по слоям: на каждом слое мы рассматриваем одновременно все ребра с данным весом, а сами слои – в порядке возрастания веса.

Построим на каждом слое отдельный граф, причем вершинами будут являться уже сформированные на данный момент компоненты связности, а ребра добавляются между соответствующими компонентами. Если ребро – петля, то значит, что существует способ связать два конца этого ребра за меньшую стоимость, и это ребро никогда нам не нужно, ответ для него – «none».

Если ребро в построенном графе – мост, то по ранее разобранному случаю, ответ для него «any», а для всех остальных – ответ «at least one». При разборе этих случаев нужно быть аккуратным, потому что при сжатии графа появляются мультиребра, ответ для них всегда «at least one», потому что ни одно из повторяющихся ребер не является мостом.

Решение это задачи можно реализовать за время O(n·log(n)).

160E - Buses and People

Для начала, промасштабируем все координаты и времена, а также, так как все ti различны, то запомним для каждого ti номер автобуса, который поедет с этим временем.

Для каждого автобуса создадим событие вида «при координате si появляется автобус, который поедет в момент времени ti и уедет до точки fi». Для каждого человека создадим событие вида «при координате li появляется человек, который поедет в момент времени bi и уедет до точки $r_i$».

Эти события отсортируем в порядке возрастания координаты (si, если это автобус, и li, если это человек) и будем выполнять в этом порядке.

Будем поддерживать структуру данных, в которой для каждого времени ti будем хранить максимальное fi автобуса, который едет в этот момент. Тогда если текущее событие означает автобус, то нужно просто обновить соответствующее значение в структуре данных. А если текущее событие означает человека, который в момент времени bi поедет до остановки ri, то нужно с помощью структуры данных отвечать на запрос «найти в структуре минимальную позицию t, которая не менее bi, а соответствующее ему значение не менее ri», тогда соответствующий этому t номер автобуса и есть ответ.

Вопрос в том, какую структуру данных использовать. Проще всего это делать с помощью дерева отрезков по максимуму, тогда на этот запрос можно отвечать за время O(log(n)), но также можно было использовать и другие структуры данных, например декартово дерево с неявным ключом и др.

Таким образом авторское решение работает за время O((n + mlog(n + m)).

Существует достаточно простое решение с двумерным деревом отрезков, работающее за O((n + mlog2(n + m)), но не гарантировалось, что оно уложится в Time Limit.

Read more »

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

By NALP, 7 years ago, translation, In English,

149A - Business trip

First, it is clear that if the sum of all numbers ai is less than k, then Peter in any case will not be able to grow a flower to the desired height, and you should output <<-1>>.

Secondly, it is easy to see that if we want to choose a one month of two, in which we watered the flower, it is better to choose one where the number of ai is more. Thus, the solution is very simple: let's take months in descending order of numbers ai and in these months water flowers. As soon as the sum of the accumulated ai becomes greater than or equal to k — should stop the process, the answer is found.

149B - Martian Clock

In this task required only the ability to work with different numeral systems. Let's try to go through numeral bases, each base to check whether it is permissible, as well as convert hours and minutes to the decimal system and compared with 24 and 60, respectively.

What is maximal base, that we need to check? In fact, it is enough to 60, because 60 — upper limit on the allowable number. It follows from the fact that if the number in an unknown number system consists of one digit, then its value in decimal not ever change, otherwise its value is not less than the base.

It is also worth to consider the case with the response <<-1>>, for this example, you can check a big base, such as 100, and even if the time for him correct, then for all large, it is also correct and the answer is <<-1>>.

149C - Division into Teams

Sort all the boys on playing skill. Then, if we send in the first team all the boys standing in a sorted array for odd places, and the second — even standing on the ground, then all requirements for division executed.

The first two requirements are obviously satisfied.

To prove the third we consider the geometric representation: Let each child designated point on the X axis with a value equal his playing skill. Connect the points with segments numbered 1 and 2, 3 and 4, and so on. If n is odd, then join the last point with the nearest the previous one.

Obviously, all these segments don't intersect in pairs, except at the points, and their total length is equal to the difference amounts to play boys' skills contained into the first team and second team. It is also clear that all of these segments completely contained in the interval [0, max(ai)], as well as the pairs are a length of zero crossing, the third requirement is satisfied, which we proved.

149D - Coloring Brackets

We introduce the notation of colors: 0 — black, 1 — red, 2 — blue. Note that a single pair of brackets has 4 different coloring: 0-1, 1-0, 0-2, 2-0.

Consider the dynamic programming, where the state is (l, r, cl, cr), where the pair (l, r) defines a pair of brackets, and cl and cr denote a fixed color for them. The value of the dynamic is a number of ways to paint all the parenthesis brackets inside the interval (l, r) in compliance with all conditions.

We write down all the pairs of brackets that are directly placed into a pair of (l, r), let k of their pieces. Moreover, we consider only the first level of nesting, it is directly attached.

In order to calculate the value of the dynamics for the state, within this state shall calculate the another dynamic, where the state is a pair (i, c) which means the number of correct colorings of the first i directly nested parentheses, and all inside them, if the latter closing bracket has a color c. Calcing the values of this dynamic is very simple, let's try to paint a (i + 1)-th parenthesis in one of four variants, but you should keep in mind possible conflicts. In such dynamics the initial state is a pair (0, cl), and the final result is sum over the states of the form (k, c), where c must not conflict with the cr.

The answer to the whole problem may be calced as the internal dynamic. Time of solution — O(n2) by a factor of about 12.

149E - Martian Strings

We will solve the problem separately for each m strings. Thus, suppose we have a string p, its length is l, and we need to check whether the Martian be seen.

We introduce additional arrays: let pref[i] is minimal position in the s of the begin of occurrence p with length exactly i, and let suff[j] is the maximum position in the s of the end of occurrence p with length exactly j

It is easy to understand that a Martian could see the p, if there exists an i, that suff[l - i] ≥ pref[i] + l - 1.

How to calculate the arrays? For pref array is sufficient to find Z-function p#s, but for an array of suff — Z-function r(p)#r(s), where r(t) means the reversed string t. Using an array of Z-functions calcing of arrays suff and pref is trivial.

Read more »

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

By NALP, 7 years ago, translation, In English,

Dear friends!

The next competition - Codeforces Round 101 for participants Div2 will take place through a pair of hours, but the others can traditionally participate out of competition. It has been prepared by a small command of authors: me (NALP), Polina Bondarenko (Polichka) and Gerald Agapov (Gerald). There were Artem Rahov (RAD), Maria Belova (Delinur) and Michael Mirzayanov (MikeMirzayanov) with us as always.

It is a little bit about authors: all of us study at the Saratov State University at faculty of Computer Sciences and Information technology on 4th course. Now in free time from competitions and problems we pass the exams :) I’m a 1/3 part from command Saratov SU#2, and Gerald with Polina - 2/3 from Saratov SU#1. We would like our rounds became kind tradition on Codeforces and you have seen us among authors soon again.

We hope that this problems will be pleasant to all participants and everyone will take the deserved high place in the total table. Today you will help Santa Claus, Elf, Vasya and the other characters. All the similarities to real people are casual :)

The points on problems are distributed today in this way: 500-1000-2000-2000-2500

UPD: You can read the tutorial here.

UPD: Thanks all for participation! The round has turn out difficult enough and only one person among all participants (including Div. 1) has solved all offered problems - akim239. Our congratulations for him!!

UPD: our congratulations for Top-10 participants in competition:
3. frp
6. hex539
7. not
10. ggbuaa

Read more »

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

By NALP, 8 years ago, translation, In English,

Registration to SRM 523 is open! See time on your timezone here

Read more »

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

By NALP, 8 years ago, In Russian,

Задача А (Div-2). Игрушечные армии

Утверждение первое: пусть пусть первым ходом было убито x солдат, а вторым y, тогда третьим ходом количество убитых будет равно min(n - x, n - y) = n - max(x, y). Значит, общее количество убитых будет равно x + y + n - max(x, y) = n + min(x, y), и именно эту величину нам нужно максимизировать. Рассмотрим ограничения на эти переменные: 0 ≤ x ≤ n, 0 ≤ y ≤ n - x. Значит, нам нужно найти максимум функции f(x, y) = n + min(x, y) в этой области. Понятно, что если мы скажем, что y = n - x (то есть для y примем крайнее положение), то ответ не уменьшится, а значит, можем свести нашу функцию к f(x) = n + min(x, n - x) на отрезке [0, n]. Очевидно, максимум этой функции равен n / 2 в точке x = n / 2.
Ответ: n / 2.

Задача E (Div-1). Две последовательности

Для начала, попробуем нашу задачу решить, не задумываясь об асимптотике. Рассмотрим динамическое программирование, где состояние - это пара (i, j) (а значение - это минимальная суммарная длина двух последовательностей), которое означает, что первая последовательность у нас заканчивается строкой i, а вторая - строкой j. Переходы тогда выглядят следующим образом: мы должны взять элемент с номером v = max(i, j) + 1 и добавить в одну из последовательностей, таким образом перейти в новые состояния (i, v) и (v, j), пересчитав нужным образом значение.

Выпишем более формально, но теперь использовав динамическое программирование "назад", считая, что i > j:


Теперь придумаем окончательное решение. В силу постановки нашей задачи, можно задачу свести к другой динамике - D(i, s), где состояние означает, что одна из последовательностей заканчивается на строку номер i, а вторая - на саму строку s, причем, заметим, что под строкой s будем подразумевать не только строки из входных данных, но и все их суффиксы длиной от 0 до l. Вспомним, что строки у нас бинарные длиной не более 20 символов, а это значит, что строки можно закодировать двоичными числами, в этом случае строка кодируется парой - длиной и самим числом (это строка, если ее интерпретировать как двоичную запись; эта тонкость нужна, т.к. в строках, возможно, присутствуют лидирующие нули, в этом случае разные строки будут переводится в одно и то же число), причем, общее количество пар будет не более 221.

Будем итерироваться по i и поддерживать наш массив со значениями динамики (одномерный, размером 2l). При переходе, нам нужно обновить его в соответствии с формулами выше: по первой нам нужно ко всем элементам массива прибавить величину f(i - 1, i) - это можно сделать, поддерживая дополнительную переменную balance и прибавлять к ней (таким образом, реальное значение элемента i будет равно balance + d[i], хотя в самом массиве значение хранится будет d[i]). А второе обновление еще проще, мы должны перебрать какой длины у нас будет наложение строки на последовательность, взять соотвествующее значение в массиве, и по всем таким перебираемым величинам взять минимум и записать его в соответствующее место в массиве.

Реализовать этот алгоритм можно за асимптотику O(n * l) с требуемой памятью O(n + 2l).

Read more »

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

By NALP, 8 years ago, translation, In English,

Task A. Double Cola

Let's designate characters on the first letter of the name. The queue looks like: SH-L-P-R-G, through 5 cans: SH-SH-L-L-P-P-R-R-G-G, through 10 cans: SH-SH-SH-SH-L-L-L-L-P-P-P-P-R-R-R-R-G-G-G-G.

The regularity is clear, and the solution is very simple: we will be iterated on p - we will find such minimum p that 5· 2p > n (thus if this number is less or equally we will subtract it from n) then we know that at first 2p Sheldon's stand, then 2p Leonard's and so on. And now we can easily answer who took a can number n (namely there was a person with number n / 2p in sequence SH-L-P-R-G (in 0-indexation).

Task B. Sets

For the solution the following important fact is required to us: we will admit elements v and u are in one set then in any of n· (n - 1) / 2 of sequences from the input data where meets v  u necessarily meets. And also if v and u are in different sets there is such sequence in which is v, but isn't present u. Then it is possible to enter the equivalence relation for all elements of all sets - two elements are equivalent, if there is no sequence where one element meets, and another isn't present. Classes of equivalence also are required sets.

It was possible to consider the answer as following algorithm: we will write out for each number the list of numbers of sequences where there is this number, and will unite two numbers if these lists are equal. This algorithm can be realized for O(n2 * log(n)) however the solution for O(n3) passes all tests with time large supply too.

The special case is a test with n = 2. This test was used for a considerable quantity of hacks.

Task C. General Mobilization

At first we will estimate from above the maximum time to which all divisions will reach capital - obviously it is required no more n days for this purpose. Therefore restrictions quite allowed model movements of divisions. The key moment of the solution - we will always consider divisions in priority order. Then in every day we will consider the list of those divisions who hasn't reached yet capital, and we will put in priority order on the necessary train. If the train is already filled, the division remains in a current city, differently we will change its position, and in day when the division will reach capital we will write down the answer. Total: in total days which it is necessary model, no more n, and every day we move no more n divisions. So our solution has asymptotic form no more O(n2)

The solutions using various structures of the data (sets, turns with priorities etc.) work for O(n2· log(n)) and it didn't always keep within in TL.

Task D. Two out of Three

The problem dares the dynamic programming. We will consider a state (i, j) meaning that in the current turn there is a person number i and also all people from j to n inclusive. Any turn achievable of the initial can be presented by corresponding condition. The quantity of conditions is O(n2), the quantity of transitions is only 3, that is O(1). So the total asymptotic form is O(n2).

Task E. Corridor

This problem has some solutions based on the various methods of the search of the area of the association of the figures on a plane. One of such methods is the method of vertical decomposition (more in detail you can esteem in various articles) and also it was possible to notice that among figures there are no three having non-zero crossing and consequently was to learn to find a total area of two figures enough. For this purpose also it was possible to use the various methods, for example, the author's solution is based on algorithm of cutting off of a convex polygon by a semiplane. Authors supposed the solution for O(n2).

Read more »

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

By NALP, 8 years ago, translation, In English,

I'm glad to welcome all fans of programming!

The second qualifying round Yandex.Algorithm will take place today, and it was prepared for you by Artem Rakhov, Michael Mirzayanov and me.

Please pay attention that as well as during the previous qualifying round Codeforces's functionality will be a little cut down for the period of the competition. Don't worry, all will return into place after the round termination.

I remind the best 500 participants pass in Yandex. Algorithm 2011 Round 1 which will take place on May, 20th at 19.00

Good luck!

UPD: the contest is over, congratulations to the winner - tourist!

I recall this competition was a qualifying round, and the best 500 will take part in Yandex.Algorithm Round 1!

Today two participants were the most lucky - Hossein_Hima and ss.nurboolean, - they have taken 499-500 places together with result 978 scores.

Read more »

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

By NALP, 9 years ago, In Russian,

Задача F. "Умный мальчик"

Эта задача решается методом динамического программирования, где состояние - это текущая записанная на доске строка, а хранимое значение - это тройка , где result - это результат игры для игрока, который в данный момент ходит (проиграл он, или выиграл), a - это максимальное количество очков у него, и b - минимальное количество очков у соперника.

Тогда мы перебираем букву, перебираем куда мы ее поставим, и пытаемся улучшить текущий ответ. Для этого мы используем следующий критерий: наше состояние выигрышное тогда и только тогда, когда существует ход в проигрышное состояние. Из всех ходов, гарантирующих наш выигрыш, вы выберем такое, чтобы наши очки были максимальны, а при равенстве - очки соперника минимальны. Если наше состояние - проигрышное, то выбирать по этому критерию надо вообще из всех переходов.

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

Хранить все состояния было проще всего в структуре данных map (или HashMap, TreeMap и подобные), но вполне адекватным решением было хранить результаты в массиве d[][][], где первое измерение - номер строки из алфавита, второе и третье измерение - начало и конец вхождения текущей строки в эту строку из алфавита.

Read more »

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