Закончился последний квалификационный тур Russian Code Cup. В полуфинал, в отборочный тур, перешли лучшие 600 участников. 16-го июня мы будем наблюдать за сражением умов, пятьдесят победителей перейдут в финал, где будут разыграны 18 тысяч долларов.
В данной статье я подробно разберу задачи, которые предлагались на третьей квалификации. Этот материал должен быть полезен как для тех, кто делает первые шаги в спортивном программировании, так и для участников, которым не удалось решить все пять задач. Также добро пожаловать в предыдущие два разбора: с первой и второй квалификаций.
Прекрасная проблема с подсчетом минимального количества негатива, приходящегося на чиновника от посетителей из очереди, про часы, залитые краской, про недоеденную кем-то шоколадку — постараюсь разделить с вами удовольствие от разбора этих замечательных задач.
Задачи отборочного раунда будут заметно сложнее и еще более интересные. Приходите «поболеть» 16-го июня в 11:00 на сайт RussianCodeCup.Ru.
«Шоколадка»
В задаче Шоколадка нужно было определить, можно ли из двух «половинок» квадратной шоколадки собрать целую. На вход подается построчная «развертка» — ширина в дольках поочередно левой половинки и правой половинки каждой «строки». Необходимо дать ответ, нет ли недостающей дольки: «yes» означает, что такое обнаружилось, и «no», если все в порядке. Подробную постановку задачи см. на официальном сайте RussianCodeCup.ru
Очевидно, что если любая пара «ширина левой половинки» — «ширина правой половинки» в сумме не дают n — ширину шоколадки, пишем «yes».
Как и в первых двух квалификациях первая задача была самой простой и ее нужно было сделать максимально быстро и с первой попытки. Лучший результат у Короткевича Геннадия — 1 минута 40 секунд с момента начала тура. Этого времени хватило на то, чтобы вчитаться в задачу, написать и протестировать программу и отправить ее на сервер.
«Игра»
По условию задачи необходимо найти победителя в несложной игре, в которой игроки поочередно двигают одну фигуру по бесконечному полю. Необходимо по известным координатам исходной позиции и цели, куда нужно привести фигуру, а также числового параметра, имеющего отношение к дальности хода фигуры, сообщить исход партии и номер хода, на которой оканчивается игра и чей ход в ней был последним, или вывести Infinity, если игроки могут играть бесконечно долго…
Очевиден самый простой вариант, когда игра заканчивается за один ход первого игрока — когда цель и исходная позиция находятся на расстоянии, меньшем или равному указанной дальности хода.
Ключевым решением данной задачи является доказательство, что во всех остальных случаях игроки могут играть бесконечно долго, если никто из них не делает неправильных ходов. Иначе, чем первым ходом первый выиграть не может, потому что на каждый ход первого второй может возвращать фигуру обратно, чтобы не проиграть. Второй выиграть тоже не может, потому что на каждый ход второго первый может возвращать второго на место, чтобы не проиграть.
В итоге, решение задачи оказывается крайне простым — выводить победу первого игрока в один ход, если расстояние между точками меньше или равно указанной дальности хода, и выводить «Infinity» в остальных случаях.
«Часы»
В задаче необходимо найти количество разных положений стрелок в момент остановки часов. По условию циферблат может быть открыт только частично и, если одна из стрелок или обе стрелки в момент остановки попали в открытый сектор, то их положение становится известно, но тем самым сужается число возможных вариантов. Также известно, что положения часовой и минутной стрелок, как и в реальных часах, находятся в прямой зависимости друг от друга. Требуется найти количество вариантов стрелок. Полная постановка задачи со всеми деталями доступна на сайте RussianCodeCup.ru
Для начала подготавливаем множество значений положений минутной стрелки.
if (m == -1) { // если положение минутной стрелки неизвестно,
// то множество включает все возможные значения
mins = new int[60];
for (int i = 0; i < 60; i++)
mins[i] = i;
} else {
// если же указано, то множество состоит из одного положения (указанного)
mins = new int[]{m};
}
Аналогично поступаем с часовой стрелкой:
if (h == -1) {// если положение часовой стрелки неизвестно,
// то множество включает все возможные значения
hours = new int[12];
for (int i = 0; i < 12; i++)
hours[i] = i;
} else {
// если же указано, то множество состоит из одного положения (указанного)
hours = new int[]{h};
}
Далее проходимся по всему произведению этих множеств и проверяем корректность положения стрелок друг относительно друга.
| Минутная стрелка | 0-11 | 12-23 | 24-35 | 36-47 | 48-59 |
| Часовая стрелка (в мин. делениях) |
5*h+1 | 5*h+2 | 5*h+3 | 5*h+4 | 5*h+5 |
| 5*h+int(m/12) | |||||
Формула для проверки корректности положения проста – 5*h+mm/12.
for (int hh : hours) { // по всем возможным положениям часовой стрелки в часовых отсечках
for (int mm : mins) {// по всем возможным положениям минутной стрелки
int hhh = hh; // hhh – положение часовой стрелки в минутных отсечках
if (hours.length != 1)
hhh = hhh * 5 + mm / 12;
// проверяем существование взаимного положения стрелок и даем ответ
// реализацию check см. Ниже
// a = левая граница открытой части циферблата
// b = правая граница открытой части циферблата
ans += check(a, b, hhh, mm, h == -1, m == -1) ? 1 : 0;
}
}
Вспомогательная функция check проверяет, может ли существовать взаимное положение минутной и часовой стрелок и соответветствуют ли положения стрелок их видимости.
boolean check(int a, int b, int hh, int mm, boolean hInside, boolean mInside) {
// a = левая граница открытой части циферблата
// b = правая граница открытой части циферблата
// hh = положение часовой стрелки в минутных отсечках
// mm = положение минутной стрелки
// hInside = положение часовой стрелки неизвестно
// mInside = положение минутной стрелки неизвестно
boolean hOk = inside(a, b, hh) ^ hInside;
boolean mOk = inside(a, b, mm) ^ mInside;
return hOk && mOk && (hh % 5 == mm / 12);
}
// определение, лежит ли положение m внутри диапазона a,b
boolean inside(int a, int b, int m) {
if (a <= b)
return a <= m && m <= b;
return inside(a, 59, m) || inside(0, b, m);
}
ГАС «Очередь»
Условие этой задачи стоит того, чтобы привести его здесь полностью:
«За последние несколько лет электронные очереди прочно вошли в повседневную жизнь. Во многих государственных учреждениях можно встретить терминал, печатающий бумажку с номером, и, не задавая привычный вопрос «Кто последний?», посетители с помощью электронного табло узнают, сколько еще им ждать и когда наступит их очередь.
Однако, пока такие системы далеки от совершенства. Например, вызывает вопросы стандартный принцип любой очереди: «Первым обслуживается тот, кто первым пришел». При разработке инновационной ГАС «Очередь» решено было сделать ее такой, что выполнение этого принципа не требуется. Вместо этого, новая система призвана минимизировать количество негатива, приходящегося на чиновника, на прием к которому стоят люди в очереди.
Известно, что у каждого человека есть такой критерий, как раздражительность. Если этот параметр равен w, то через t часов ожидания в очереди этот человек обрушит на голову чиновника ровно wt единиц злобы и ругани. Так, если посетителя начнут обслуживать сразу же после его прихода, то чиновник не пострадает, а если посетитель пришел в начале третьего часа, а его обслуживание началось только в начале пятого — количество гнева будет равно 2w.
Также известно, что на обслуживание каждого посетителя уходит ровно час, а каждый посетитель приходит в начале какого-либо часа. Ваша задача заключается в том, чтобы по данным вам показателям раздражительности и временам прихода посетителей определить, сколько негатива достанется чиновнику при оптимальном порядке обслуживания клиентов.
В первой строке задано одно целое число t — количество случаев, которые вам предстоит обработать. Далее следуют t описаний самих случаев.
Описание каждого случая состоит из: числа n в первой строке — количества посетителей, и n описаний самих посетителей. Для каждого посетителя в отдельной строке указаны два целых числа ri и wi (1 ≤ ri, wi ≤ 106) — номер часа, в начале которого посетитель пришел, и его коэффициент раздражительности, соответственно.
Суммарное количество посетителей во всех случаях одного теста не превосходит 1000000.
Для каждого случая в отдельной строке следовало вывести ответ — минимальное суммарное количество негатива, которое получит чиновник.«
Один из примеров к задаче демонстрирует описанный принцип. В примере пришло к чиновнику три посетителя. Из них двое — в начале первого часа с раздражительностями «3» и «4» соответственно. И еще один — в начале второго часа с раздражительностью «5». На обслуживание каждого уходит час, следовательно в начале первого часа есть два варианта — пропустить вперед посетителя с раздражительностью «4» или посетителя с раздражительностью «3». Тот, кого не пропустили, переходит на следующий час, где добавляется еще посетитель «5», и там появляется еще два варианта — пропустить новичка, или того, кто стоит в очереди.
| Раздраж-сть пришедших |
Вариант 1 | Вариант 2 | Вариант 3 | Вариант 4 | |
| Начало 1-го часа | 3, 4 | П(3), РЧ=0 | П(3), РЧ=0 | П(4), РЧ=0 | П(4), РЧ=0 |
| Начало 2-го часа | 5 | П(4), РЧ=4×1=4 | П(5), РЧ=4×1=4 | П(3), РЧ=3×1=3 | П(5), РЧ=3×1=3 |
| Начало 3-го часа | — | П(5), РЧ=4+5=9 | П(4), РЧ=4×2+5×1=13 | П(5), РЧ=3+5=8 | П(3), РЧ=3×2=6 |
| МИНИМУМ |
За два часа чиновник получает минимально раздражительность 6.
Алгоритм, решающий эту задачу достаточно прост, если догадаться до того факта, что в каждый момент времени выгоднее всего обслуживать человека, который к этому моменту уже пришел, еще не обслужен ранее, и раздражительность которого не меньше, чем у остальных таких же людей.
Докажем это утверждение. Пусть у нас есть некоторое расписание, построенное по этому правилу и некоторое оптимальное расписание. Рассмотрим первый момент времени t1, в котором они различаются. Пусть человек, который в этот момент обслуживается в оптимальном расписании, обладает раздражительностью w1, а человек, который обслуживается в этот момент во втором — раздражительностью w2. В оптимальном расписании этот человек обслуживается в некоторый момент времени t2, причем t2 > t1 (ведь до момента t1 расписания были одинаковы). Значит, если в оптимальном расписании поменять местами этих двух людей, что, очевидно, можно сделать, так как и в момент времени t1, и в момент времени t2 они оба доступны (раз оба расписания валидны), то суммарный гнев в оптимальном расписании изменится на (t2− t1) × w1 + (t1 − t2) × w2, что равно (t2 − t1) × (w1 − w2).
Поскольку t2 > t1 (по сказанному выше), и w1 > w1 (по построению исследуемого расписания), указанная величина изменения гнева будет отрицательной, а значит, оптимальное расписание улучшилось. Очевидно, что подобные рассуждения для всех прочих расхождений приведут к тому, что описанный выше алгоритм очереди верный.
Теперь можно задуматься о реализации описанного решения. Нам необходима структура данных, в которой будут храниться все уже пришедшие, но еще не обслуженные люди, и из которой можно было бы за небольшое количество времени извлекать максимальный элемент (человека, раздражительность которого не меньше, чем у остальных). Этой структурой является приоритетная очередь. При реализации ее, например, с помощью двоичной кучи, операции будут выполняться за O(log n), а суммарное асимптотическое время работы решения составит O(n log n).
В Java и C++, например, приоритетная очередь реализована в виде классов PriorityQueue и priority_queue, соответственно. Но для полноты картины следует рассказать что это такое для тех, кто не в курсе.
Приоритетная очередь позволяет хранить пары (ключ, значение) и поддерживает операции добавления пары, быстрого поиска пары с минимальным или максимальным ключом, извлечения такой пары. Эффективным и наиболее оптимальным способом реализации этой структуры является двоичная куча.
Двоичная куча с накоплением максимума реализуется через бинарное дерево, в котором любой узел-потомок не может быть больше своего узла-предка, то есть корнем всегда является максимум, поэтому получать его очень быстро. Добавление новой пары производится в любой свободный концевой узел (лист), после чего она перемещается по направлению к корню, пока значение предка меньше, чем значение только что добавленного ключа.
Детально ознакомиться с этим алгоритмом можно здесь: http://www.rsdn.ru/article/submit/heap/heaps.xml#EKLAC
«Помехи»
В данной задаче необходимо было написать алгоритм восстановления поврежденных данных (набор сообщений по 34 бита) по известным полиномиальным хэшам. Необходимо восстановить сообщение, отличающееся от оригинального наименьшим числом бит, имеющим тот же хеш.
Подробную постановку задачи см. на сайте RussianCodeCup.ru
Перебирать все 34-битные числа — а это 17 миллиардов значений — займет слишком большое время. Для оптимизации перебора применяют метод, называемый встречей в середине (meet-in-the-middle).
Концепция meet-in-the-middle предполагает разбиение задачи пополам и решение «большой задачи» через частичный расчет для половинок. Классической задачей, решаемой таким подходом, является задача о наиболее эффективной упаковке рюкзака. Каждый предмет характеризуется весом и ценностью, нужно в рюкзак с ограничением по весу набрать вещей с максимальной суммарной ценностью. Для ее решения большое множество вещей N разбивается на два равных (или примерно равных) подмножества, для которых можно перебрать все варианты за приемлемое время, и посчитать для каждого суммарный вес и ценность, а затем для каждой группы из первого подмножества найти группу из второго с максимальной ценностью, при которых общий вес будет укладываться в ограничения.
В нашем случае нужно посчитать хеши для первых n/2 бит и отдельно для всевозможных вариантов n-n/2 бит. В каждой половине получается максимум 217=131072 вариантов.
int m = (len + 1) / 2; // находим бóльшую половину
Pair[] h1 = new Pair[1 << m]; // массив под хеши
for (int i = 0; i < h1.length; i++) {
h1[i] = new Pair(i, countHash(i)); // рассчитываем хеш каждого значения
}
Pair[] h2 = new Pair[1 << (len – m)];
for (int i = 0; i < h2.length; i++) {
h2[i] = new Pair(i, countHash(((0L + i) << m))); // с учетом
}
Поскольку нам необходимо получить сообщение с фиксированным известным хешом h, то каждому варианту значения хеша для первой половины бит h1 в пару сопоставляется не более одного значения хеша для второй половины бит h2 такое, что h = (h1 +h2) mod M.
Осталось научиться для каждого варианта h1 быстро находить соответствующее значение h2. Для этого можно воспользоваться такими структурами данных, как set в C++ или TreeSet и HashSet в Java.
Также можно отсортировать всевозможные значения хешей для первой и второй половины по возрастанию и воспользоваться идеей «двух указателей».
Будем двигать первый указатель i по хешам для первой половины в порядке возрастания значений. Соответствующий хеш во второй половине при этом будем искать, начиная от предыдущего подходящего значения, двигая второй указатель j по хешам для второй половины в порядке убывания значений. В тот момент, когда указатель j дойдет до минимального значения, его необходимо будет переместить на максимальное значение. Но, такое произойдет не более одного раза, поэтому суммарно указатель j пройдет не более двух раз по всем значениям.
И, наконец, необходимо из всех найденных пар подходящих значений h1 и h2 выбрать ту, в которой изменилось минимальное число бит по сравнению с принятым сообщением m.
Алиев Рауф,
директор департамента исследований и образования
Mail.Ru Group
Автор: raliev
