A. HQ9+
В задаче давалось описание HQ9+ и спрашивалось, выведет ли заданная программа что-то на печать. Ввиду исключительной простоты языка для этого было достаточно проверить, содержит ли программа хотя бы один из символов H, Q и 9 (с учетом регистра).
B. Unary
У замечательного языка Brainfuck есть диалекты на все случаи жизни; подозреваю, что при желании по ним можно было бы придумать целый раунд (не Unknown Language Round, конечно, слишком уж он известен), но на этот раз я ограничилась только одной задачей.
В решении нет ничего сложного: нужно всего лишь в точности следовать описанию преобразования кода на Brainfuck в код на Unary. В языках со встроенной длинной арифметикой можно действовать напролом: заменить символы каждого типа на соответствующие бинарные коды, преобразовать полученную строку в длинное число и взять его по модулю.
Если длинной арифметики нет, тоже не страшно. Программу можно формировать постепенно, добавляя к ней по одному символу слева направо; на каждом шаге длина имеющейся программы умножается на 16 (что соответствует дописыванию справа бинарного кода длины 4), к ней добавляется код текущего символа и результат берется по модулю.
C. Лента Тьюринга
Еще одна задача на реализацию, навеянная не менее замечательным языком INTERCAL. Технически чуть сложнее предыдущей за счет выполнения операции "отобразить зеркально байт" и выполнения не описанной процедуры, а обратной. Для i-ого символа входных данных зеркально отображаем его и сохраняем в rev[i], а i-ое число вывода получаем как (rev[i - 1] - rev[i] + 256)%256 (для i = 0 rev[i - 1] = 0).
D. Piet
Замечательный язык Piet отличается от прочих графически-эзотерических языков особо зверским подходом к реализации указателя инструкций — в задаче предлагалась очень упрощенная версия.
Первым шагом решения должно было быть выделение одноцветных блоков. Из-за того, что они строго прямоугольны, это можно было сделать и без поиска в ширину: при нахождении цветного пикселя, который еще не отмечен как часть одного из блоков, можно найти самую длинную последовательность пикселей того же цвета в этой строке, начинающуюся с него, и считать ее шириной блока; аналогично определяется высота блока.
............ ..X----->... ..|XXXXXX... ..vXXXXXX... ............
При этом лично мне удобно было пронумеровать блоки, запомнить их цвета и координаты границ — чтобы два раза не перебирать. Затем я вычислила "функцию переходов" между блоками: для каждого состояния счетчика инструкций выяснить, в какое он перейдет из него за один шаг. Для этого можно проиндексировать состояния счетчика следующим образом. Указатель на текущий блок задается индексом блока, значения указателя направления соответствуют числам от 0 (влево) до 3 (вверх), указателя выбора блоков — 0 (влево) и 1 (вправо). Тогда состояние счетчика однозначно задается числом 8*(указатель на текущий блок) + 2*(указатель направления) + (указатель выбора блоков). Это число находится в диапазоне от 0 до 8*N-1 (N — количество цветных блоков) и изменяется по сравнительно несложным правилам: в начале выполнения программы оно равно 0 (если нумеровать блоки естественным образом, в порядке их нахождения), и если на каком-то шаге переход между блоками возможен, изменяется слагаемое 8*(указатель на текущий блок), а если невозможен, то слагаемое 2*(указатель направления) + (указатель выбора блоков) просто увеличивается на единицу (по модулю 8).
При такой системе индексации состояния счетчика "функцию переходов" можно описать одномерным массивом целых чисел, где индекс — это исходное состояние, а значение — состояние, в которое счетчик перейдет за один шаг. Для заполнения массива нужно для каждого блока и каждого состояния счетчика выяснить, из какого угла блока будет происходить переход и в каком направлении, и проверить, что находится в следующем пикселе. Размер массива не превысит 502, а симуляция каждого шага выполнения программы сведется к переходу текущего состояния от a к f(a), что гораздо проще, чем полная симуляция описанной в условии процедуры.
E. Черепашка Logo
Задача на динамическое программирование (и единственная на не-эзотерический язык :-)). Подходов может быть несколько. Я хранила два трехмерных массива: самое левое и самое правое положение черепашки, если использовано I команд из списка, сделано ровно J изменений в этих командах и черепашка смотрит в направлении K. Начальное условие — при I = J = 0 и черепашке, смотрящей вправо (начальное направление можно выбрать произвольно) left = right = 0. Правила перехода между позициями: если сейчас выполнится команда T (либо она текущая и изменение не происходит, либо эта команда — результат изменения), координата черепашки сохраняется, а направление меняется на противоположное. Иначе направление сохраняется, а координата меняется в соответствии с этим направлением.
На каждой команде удобно делать не больше одного изменения; тогда после вычисления всех элементов массива динамики, в которых использованы все команды из списка, нужно взять максимальное значение по всем направлениям черепашки и по всем количествам изменений, имеющих ту же четность, что и заданное (любую команду можно изменить четное количество раз, и это не повлияет на результат).
Div1 D. Константы на языке Шекспира
Две последние задачи раунда были вдохновлены не менее замечательным языком Shakespeare и по изначальной задумке были одной задачей, которая звучала как "Как вывести заданную последовательность символов с использованием минимального количества прилагательных?". Но потом мы одумались :-) и сделали из этого монстра две задачи.
Напрашивающееся жадное решение (разбить бинарную запись числа на группы единиц, идущих подряд, записать группу размера 1 как одну степень, группу размера 2 и больше — как разность двух степеней) неверно; это можно показать на тесте 4 "10110111": жадное решение вернет 5 ( + 27 + 26 - 24 + 23 - 20), в то время как существует решение размера 4 ( + 28 - 26 - 24 - 21).
Правильное решение основано на следующей идее. Пусть у нас есть фрагмент бинарной записи, содержащий биты, соответствующие степеням двойки от N до M (N < M), в котором K нулей и L единиц. Его можно записать непосредственно через сумму степеней, соответствующих позициям единиц, использовав для этого L слагаемых. А можно записать его как 2M + 1 - 2N - ..., где ... — степени, соответствующие позициям нулей, использовав 2 + K слагаемых. Очевидно, что применять второй способ записи есть смысл только к фрагментам, начинающимся и заканчивающимся на единицы (иначе можно применить его к более короткому фрагменту, не содержащему начальные/конечные нули, сэкономив на этом слагаемое) и не содержащих последовательности 00 внутри (иначе можно разбить эту последовательность на две в том месте, где находятся эти нули, и записывать их по отдельности, при этом не увеличив, а то и уменьшив количество слагаемых).
После этого наблюдения задача решается динамическим программированием: для каждой позиции в бинарной записи храним признак "записываем ее как сумму степеней или как разность", и во втором случае храним длину фрагмента, который записываем как разность (длину фрагмента, который записываем как сумму, хранить не нужно, потому что как сумму можно записывать и отдельные биты, на фрагмент этот способ не завязан).
Симметрично же все, поэтому можно идти только вправо.
P. S. А будет ли авторский разбор задачи E div 1?
А разве в "Черепашке Лого" должно не работать ДП по "двум с половиной" ;) параметрам
1) до какой по номеру команды программы добрались (параметр целочисленный)
2) сколько сделали изменений (параметр целочисленный)
3) влево или вправо смотрит черепашка (параметр булев, и лично я реализовывал не третьим измерением массива, а тем, что двумерный массив хранит структуры).
???
UPD: наверно, таки не работает -- ошибка не только на 11 тесте (тупо не учтено n > command.size()), но ещё и на 14-м. Почему -- мне пока не ясно.
А если то, что я написал в http://codeforces.me/blog/entry/3292#comment-66089 тоже не факт -- ОЧЕНЬ хотелось бы узнать почему.
С важным уточнением о том, что хранится и минимум, и максимум, получается все правильно.
Буду благодарен за пояснение. (за контест отдельное спасибо - давно у меня такого скачка в рейтинге не было... или вообще не было)
Блок пикселей определяется как прямоугольник, состоящий из пикселей одного цвета (не черного). Гарантируется, что все связные множества цветных пикселей будут образовывать прямоугольные блоки.
самое интересное, что решение "в лоб" проходит)) я пытался свалить макс тестом такое решение, но оно работало 1700 мс.
Ну есть же оригиналы (вроде меня) которые на Java пишут... Уверен что не пройдёт по времени.
Хотя в этом контесте первые три задачи на пыхтоне сдались и может стоило попробовать и четвёртую... (не в лоб, в смысле) %)
В дорешке сдалось решение на яве решение в лоб с предварительным подсчётом перехода и изменения направлений для каждой точки. Итого 900мс.
с прекальком должно обязательно заходить, так как у вас выполнится только сonst*N операций. ( где const около 5-8 операций ( переход ) ). в итоге получится около 250-400млн операций.
Мое решение с прекальком зашло за 410мс.
Под "в лоб" я подразумевал совсем "в лоб" :D
То есть на каждом шаге мы находим край по направлению DP, потом крайний пиксель по направлению CP.
Просто при n = 10^18 любое решение в лоб не проходило бы и задача была бы поинтереснее)
Не в лоб я имел ввиду поиск цикла, но писать это мне было лень - итак начудачил(
I have problem understanding what problem C asks us to do.Plz help me by telling where I misunderstood the question...
prev,res=0;
for(i=0;i<s.length();i++)
{
rev="";
res=(prev-(int)s.charAt(i))%256; //ith element is subtracted from prev%256(step2)
a=Integer.toBinaryString(res);//converting to binary
while(a.length()<8) //making its size 8
a='0'+a;
for(j=7;j>=0;j--) //rev the binary number(step 3)
rev=rev+a.charAt(j);
res=Integer.parseInt(rev,2);
out.println(res); //printing the answer
a=Integer.toBinaryString(res); //preparing the prev for the 1st step
while(a.length()<8)
a='0'+a;
rev="";
for(j=7;j>=0;j--)
rev=rev+a.charAt(j);
prev=Integer.parseInt(rev,2);
}
I considered states (row, column, direction, left/right) and then found for each position which position would be the next one, so then after some preprocessing I could advance in 2^k steps (k <= 25).Sorry wrong problem.
[0: BP=9 (color), DP=Right0]
1: BP=9, DP=Right1
2: BP=3, DP=Right1
3: BP=4, DP=Right1
4: BP=4, DP=Down0
5: BP=4, DP=Down1
6: BP=4, DP=Left0
7: BP=3, DP=Left0
that was very clear
i really appreciate that
thanks again....:)
Ну смотри, вот пусть есть модуль p и 2 числа x = ap + b и y = cp + d (b < x, d < y).
Перемножим их, будет xy = acp2 + (ad + bc)p + bd = acp2 + (ad + bc)p + (bd)/p*p + (bd) % p. И по модулю p останется (bd) % p.
А что будет, если сначала взять модуль, а потом перемножить? Тогда вместо x останется b, а вместо y останется d - то же самое - после перемножения будет bd = (bd)/p*p + (bd) % p, а по модулю - (bd) % p.
Т.е. выходит, что можно сформулировать общее правило так: любая линейная комбинация по модулю p может быть вычислена, когда каждый из промежуточных результатов берётся по модулю. Верно?
Да, конечно.
when it more than 2 '1',('111','11'...) it is better to use '-2^'.
use the greedy to solve the problem D..
how to solve the problem E。div1
We can reduce it to a minimum-cost flow (or matching) problem. Consider the following formulation: