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

[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 и т.д. ?

[Michael_Rybak]

Алгоритм интересный, но в реализации будет наверное громоздким

Совсем нет:

{$AppType CONSOLE}

const MAX_N = 128;

type TAr = array [1 .. MAX_N] of longint;

var n0, n1: integer;
    a0, b0, a1, b1: TAr;
    s0, s1: string;
    i, len: integer;

procedure ToCanonic(var s: string; var n: longint; var a, b: TAr);
  var i, j, k, ones: longint;
      t: char;
begin
  n := 0;
  for i := 1 to Length(s) do
    if s[i] = '0' then begin
      ones := 0;
      for j := i + 1 to Length(s) do
        if s[j] = '1' then begin
          Inc(ones);
          if ones = 2 then begin
            Inc(n);
            a[n] := i;
            b[n] := j;
            for k := i to (i + j) Div 2 do begin
              t := s[k];
              s[k] := s[i + j - k];
              s[i + j - k] := t;
            end;
            break;
          end;
        end;
      if ones < 2 then
        break; //достигли плавающей единицы
    end;
end;

begin
  Readln(len);
  Readln(s0);
  Readln(s1);
  ToCanonic(s0, n0, a0, b0);
  ToCanonic(s1, n1, a1, b1);
  if s0 <> s1 then
    Writeln('No')
  else begin
    Writeln('Yes');
    for i := 1 to n0 do
      Writeln(a0[i], ' ', b0[i]);
    for i := n1 downto 1 do
      Writeln(a1[i], ' ', b1[i]);
  end;
end.

Хотя мой тоже можно переделать (просто прогнать 2 раза: 1 раз для "да"-"нет", второй раз результат )

А ты можешь доказать правильность своего?

Почему невозможно, если можно так: 1001001, 1001001 и т.д.

Согласен.

[Malice]

А ты можешь доказать правильность своего?

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

[Гость]

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

"Так что" ЧТО?

Если я перечислю в программе 5 тестовых примеров с ответами - это что, тоже будет правильным решением? Ведь тестовые варианты проходят... И вторая часть вопроса: кто Вам сказал, что это так же чисто отработает на последовательности из 95 цифр, где могут понадобиться десятки перестановок? Здесь, уважаемый, не олимпиада...

[mlc]

Если я перечислю в программе 5 тестовых примеров с ответами - это что, тоже будет правильным решением?
Ведь тестовые варианты проходят...

Нет, это значит - хочешь проверить, гоняй на своих тестовых примерах, доказывай, что неправильно. Приводить ход своих размышлений, алгоритм работы, объяснить как оно работает я не обязан. Форум программистов, а не философов-разговорников, да и тема в "Задачах", а не в теор. вопросах.

И вторая часть вопроса: кто Вам сказал, что это так же чисто отработает на последовательности из 95 цифр, где могут понадобиться десятки перестановок?

А что ей помешает ? Запутается ? А если миллион, а у вас 4 массива, и что ?

Здесь, уважаемый, не олимпиада...

Условия одни-главное, чтоб работало..