Блог пользователя Nickolas

Автор Nickolas, 13 лет назад, По-русски

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 внутри (иначе можно разбить эту последовательность на две в том месте, где находятся эти нули, и записывать их по отдельности, при этом не увеличив, а то и уменьшив количество слагаемых).

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

Разбор задач Codeforces Beta Round 96 (Div. 1)
Разбор задач Codeforces Beta Round 96 (Div. 2)
  • Проголосовать: нравится
  • +58
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
В E вроде бы можно не искать крайнее левое состояние, если разрешили стоять вначале, смотря в люую сторону
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    В принципе да, но я так и не смогла убедить себя в правильности этого варианта и писала авторское решение так, с перестраховкой :-)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Симметрично же все, поэтому можно идти только вправо.

      P. S. А будет ли авторский разбор задачи E div 1?

13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

А разве в "Черепашке Лого" должно не работать ДП по "двум с половиной" ;) параметрам
1) до какой по номеру команды программы добрались (параметр целочисленный)
2) сколько сделали изменений (параметр целочисленный)
3) влево или вправо смотрит черепашка (параметр булев, и лично я реализовывал не третьим измерением массива, а тем, что двумерный массив хранит структуры).
???

UPD: наверно, таки не работает -- ошибка не только на 11 тесте (тупо не учтено n > command.size()), но ещё и на 14-м. Почему -- мне пока не ясно.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не, не факт что максимизируя текущее состояние мы максимизируем результат. 
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В том виде, как я написал сначала -- пожалуй, действительно не факт.

      А если то, что я написал в http://codeforces.me/blog/entry/3292#comment-66089 тоже не факт -- ОЧЕНЬ хотелось бы узнать почему.
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        С важным уточнением о том, что хранится и минимум, и максимум, получается все правильно.

  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Я делал такую динамику, всё работает.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Мне лень стало в Е динамику писать. Написал вот такую хрень http://codeforces.me/contest/132/submission/925825
Она почему-то прошла.
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Хотя задача D у меня сдалась, но я малость недопонял - могли ли два одноцветных прямоугольника касаться (хотя бы частично) стороной (не углом)... %)

Буду благодарен за пояснение. (за контест отдельное спасибо - давно у меня такого скачка в рейтинге не было... или вообще не было)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    не могли)). В условии написано:

    Блок пикселей определяется как прямоугольник, состоящий из пикселей одного цвета (не черного). Гарантируется, что все связные множества цветных пикселей будут образовывать прямоугольные блоки.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Да, эту фразу я несколько раз перечитал - размышлял означает ли "цветных" в данном случае "одноцветных" или "нечёрных"... %)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если бы они касались стороной - они были бы связанным множеством и не являлись бы прямоугольником.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В D состояний 50х50х8 , период не может быть больше, можно было n поставить до 10^18 
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А я как раз думаю что имело смысл ставить n поменьше. Большое число (при маленьком размере поля) как бы намекает что путь зациклится (хотя до этого трудно не догадаться)... 10-50 млн в этом смысле очень хорошее число - может побудить кого-нибудь пытаться "в лоб" решить...
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      самое интересное, что решение "в лоб" проходит)) я пытался свалить макс тестом такое решение, но оно работало 1700 мс.

      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Ну есть же оригиналы (вроде меня) которые на Java пишут... Уверен что не пройдёт по времени.

        Хотя в этом контесте первые три задачи на пыхтоне сдались и может стоило попробовать и четвёртую... (не в лоб, в смысле) %)

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Моё решение "в лоб" тоже проходит в дорешке. Я на контесте о периоде вот даже как-то не задумался, прикинул, посчитал, вроде должно заходить, а оказалось ТЛ 58. А самое обидное, что сейчас я отправляю тот же код, только указывая компилятор GNU C++, а не MS C++ как на контесте, и получаю "Полное решение" с максимальным временем работы 1550 мс. Действительно ли GNU C++ настолько быстрее MS C++? Не знал.
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        В дорешке сдалось решение на яве решение в лоб с предварительным подсчётом перехода и изменения направлений для каждой точки. Итого 900мс.

        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          с прекальком должно обязательно заходить, так как у вас выполнится только сonst*N операций. ( где const около 5-8 операций ( переход ) ). в итоге получится около 250-400млн операций. 

          Мое решение с прекальком зашло за 410мс.

          Под "в лоб" я подразумевал совсем "в лоб" :D

          То есть на каждом шаге мы находим край по направлению DP, потом крайний пиксель по направлению CP. 

          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Просто при n = 10^18 любое решение в лоб не проходило бы и задача была бы поинтереснее)

            Не в лоб я имел ввиду поиск цикла, но писать это мне было лень - итак начудачил(

13 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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);
            }
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Problem E stand up some difficulties for me in finding a solution. Can someone please reply me what's the main idea of the problem ? Thanks in advance.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    it's a dynamic programming.The idea is foreach character, try to change it (if possible) or not.My state is (position, changeLeft, direction, value)

     I missed "abs" of the value during the contest. Lost about 1200 point :(
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Could anyone explain the following case for Problem Piet.
Input:
3 7
901
922
934
Output:
3
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    [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

13 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится
can anyone explain the following test case of Piet for me?
3 9
888
456
226
Ans: 4
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Log from my accepted solution on this input:
    After step 1: color=8, DP=right, CP=right
    After step 2: color=8, DP=down, CP=left
    After step 3: color=6, DP=down, CP=left
    After step 4: color=6, DP=down, CP=right
    After step 5: color=6, DP=left, CP=left
    After step 6: color=2, DP=left, CP=left
    After step 7: color=2, DP=left, CP=right
    After step 8: color=2, DP=up, CP=left
    After step 9: color=4, DP=up, CP=left
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Sorry, my mistake.
13 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится
А может вы мне объясните, почему в задаче В взятие промежуточного результата по модулю эквивалентно взятию по модулю целого длинного числа?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    Это азы модульной арифметики. Почитайте на эту тему в википедии, Кормене, еще в чем-нибудь хорошем.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Давай представим наше исходное число как an * 16n + ..a1 * 16 + a0. Это будет так, потому что склеивание таких бинарных строк длины 4 равносильно умножению левой части на 16 ( 24), и крайние 4 бита справа будут нулями.
    Теперь давай посчитаем  (an * 16n + ..a1 * 16 + a0)%mod. Для начала немного преобразуем наше выражение : a0 + 16 * (a1 + 16 * (a2 + ... + 16 * (an - 1 + 16 * an))). Тогда, если мы будем поступать по принципу result = 0 и при добавлении любого ai делать шаги result = (result * 16)%mod, result = (result + ai)%mod, то это равносильно выражению выше, но взятому по модулю.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Ну смотри, вот пусть есть модуль 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.

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо, очень хорошее объяснение. Значит выходит xy%p == (x%p) * (y%p), а как быть если b == x и d == y? Тогда так: xy%p == ((x%p) * (y%p)) % p ? (2*6)%10 == 2, но (2%10) * (6%10) = 12

      Т.е. выходит, что можно сформулировать общее правило так: любая линейная комбинация по модулю p может быть вычислена, когда каждый из промежуточных результатов берётся по модулю. Верно?
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Да, конечно.

        Только надо не забыть, что (a + b)mod p в общем случае не равно (a mod  p + b mod  p), а равно (a  mod p  + b  mod  p)  mod  p
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Спасибо, теперь всё ясно.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ну и b == x не бывает, т.к. b в моем примере это остаток от деления на x, и он лежит в диапазоне от 0 до x-1
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Where is the editorial of Div1 prob.D and E?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Будет ли разбор задач первого дивизиона?
13 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

how to solve the problem E。div1

  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

    We can reduce it to a minimum-cost flow (or matching) problem. Consider the following formulation:

    • for each number ai in the sequence (n total) create two nodes ui and vi; and
    • for each variable bi you have (m total), create a node wi.
    We will create a weighted bipartite graph with nodes ui and wi on one side, and nodes vj on the other. We connect ui to vj for all j > i. This represents the case "aj is the next number to use the same variable as ai." Thus it has cost f(aj) if ai ≠ aj and cost zero if ai = aj, where f(aj) is the number of bits set in aj. Also, connect wi to vj for all j with cost f(aj). This represents the case "aj is the first number to be stored in variable bi."

    The result is obtained by a minimum-cost matching in this graph. To recover the sequence, for each vj we see what node ui or wi it is matched with. If vj is matched with a ui, we put aj in the same variable as ai (recall that i < j in this case), doing nothing if they are equal. If vj is matched with wi, we put aj in variable bi.

    Hope this helps!