Битовые последовательности, Помогите решить задачу Опции

[Maksay]

Люди, кто любит решать олимпиадные задачи на Pascal'е-помогите решить:
Есть 2 битовых последовательности длины N.
Требуется узнать, можно ли получить из одной
другую посредством переворачивания подпоследовательностей
с четным кол-вом единиц, и если да-то как!
Пример:
011010010 010101010
{011010010
все символы
010010110
с 4 по 7
010101010}
P.S. Неделю бъюсь-ничего.Кстати N-до 100.

[Michael_Rybak]

Надеюсь, теперь я правильно понял условие

Понятно, что преобразования у нас транзитивные и обратимые.

1) транзитивность – если из строки А можно получить В, а из В – С, то из А можно получить С (очевидно)
2) обратимость – если из А можно получить В, то из В можно получить А (очевидно, нужно просто выполнить операции в обратном порядке)

Теперь попытаемся свести обе входные строки к некоторому каноническому виду.

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

Например:

11000100110010011011

11000100110010011011
11100100010010011011

11100100010010011011
11110001000010011011

11110001000010011011
11111000010000011011

11111000010000011011
11111100000100001011

11111100000100001011
11111110000100000011

11111110000100000011
11111111000000100001

11111111000000100001
11111111100001000000

В данном случае плавающая единица оказалась на расстоянии 4х нулей от остальных:

11111111100001000000

Даже если бы она оказалась на расстоянии 0 (11111111110000000000), мы все равно ее назвали бы "плавающей".


Из транзитивности и обратимости следует, что, если обе входные строки свелись к одному и тому же каноническому виду, то решение существует.

Рассмотрим пример, для которого ответ - "да":

1) Вход
9
100011100
001011001

Приводим 100011100:

100011100

100011100 - (2,6)
111000100

Приводим 001011001:

001011001

001011001 – (1,5)
101001001

101001001 – (2,6)
110010001

110010001 – (3,9)
111000100

Чтобы получить ответ, выписываем операции для первой строки, а потом, в обратном порядке, операции для второй:

(2,6)
(3,9)
(2,6)
(1,5)


Но теперь, конечно, возникает вопрос, почему нельзя, скажем, из строки 111110010 получить строку 111110001. Докажем, что разные канонические строки неприводимы друг к другу.

В строке рассмотрим группы нулей (в т.ч. пустые), ограниченные по краям единицами, или краями строки. Групп будет на 1 больше, чем единиц. Например, в строке

1100010110

Будет шесть групп, длины 0,0,3,1,0,1 соответственно:

<>1<>1<000>1<0>1<>1<0>

Будем рассматривать общее количество нулей в *нечетных* группах:

<>1<>1<000>1<0>1<>1<0>


Легко проверить, что для нашей задачи эта характеристика является инвариантом, т.е. что переворот произвольной подпоследовательности с *четным* количеством единиц не меняет общего количества нулей в *нечетных* группах. Это объясняется тем, что из-за четности количества единиц все нули, которые были в нечетных группах, попадают опять в нечетные группы, а те, которые были в четных – попадают в четные.

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

Поэтому мы доказали, что, если сведя обе входные строки к каноническому виду, мы получили разные результаты, то ответ – "нет".

Кстати, случай, когда количество единиц в строках отличается (или отличается длина строк), учитывать отдельно не нужно – канонические виды тоже получатся разными


Сообщение отредактировано: Michael_Rybak - 6.09.2006 13:59

[Malice]

Ну вы и монстры, блин

Michael_Rybak
Алгоритм интересный, но в реализации будет наверное громоздким. Но у него есть преимущество перед моим - "да" или "нет" он скажет до вывода результата, у меня вычисляется в процессе. Хотя мой тоже можно переделать (просто прогнать 2 раза: 1 раз для "да"-"нет", второй раз результат )

Мне непонятен только вот этот пример:
2)Вход:
7
1001001
Изменить невозможно
Почему невозможно, если можно так: 1001001, 1001001 и т.д. ?