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

[Maksay]

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

[klem4]

Может быть вариант что нам для получения придется преревернуть несколько подпоследовательностей ? Ну на рпимер с 4 по 7, с 12 по 20 и с 23 по 25 ? Или нам надо перевернуть какую-то одну (из всех имеющихся) последовательность с нечетным кол-вом едениц ?

Хотя сори, слово подпоследовательностей говорит само за себя _

[volvo]

В дополнение к предыдущему вопросу: может ли понадобиться "разворот" перекрывающихся подпоследовательностей? Допустим, сначала 4-7, а затем 6-10? Или это не разрешено?

Кстати, если можно - еще хотя бы несколько тестов приведи...

[klem4]

Volvo, и на твой вопрос ответ судя по всему тоже да, ибо в примере сначала была перевернута вся последовательность, а потом кусок из середины

[volvo]

Тогда есть высокая (очень высокая) вероятность того, что ВСЕГДА можно исходную последовательность привести к результату. За исключением случаев, когда в исходной последовательности всего одна единица.

Кстати, приведенный пример решается так:
исходная:
011010010

010101010 = результат...

Так что... Перекрывающихся подпоследовательностей не было. Вопрос в силе.

[Maksay]

Извиняюсь, пример действительно неудачный.Переворачивать можно сколько угодно раз и как угодно.
Другие тесты:
1)Вход:
9
100011100
001011001
Выход:
Да
6 9
3 8
1 5
2)Вход:
7
1001001
Изменить невозможно
3)Вход:
7
11001101
10101101
Выход:
Нет

[Malice]

У меня вот такой алгоритм получился:

uses crt;
var c,i,j,n:integer;
s1,s2:string;
function pr(s:string):string;
begin
if s='' then pr:=s else
pr:=s[length(s)]+pr(copy(s,1,length(s)-1));
end;

begin
clrscr;
s1:='100011100';s2:='001011001'; {s1:='011010010';s2:='010101010';}
n:=byte(s1[0]);
writeln (s1); writeln (s2);
i:=1;
for i:=1 to n-1 do begin
if s1[i]=s2[i] then continue;
c:=byte(s2[i]='1'); j:=i;
repeat
inc(j);
c:=c+byte(s2[j]='1');
until (j>n) or (not(odd(c )) and (s2[j]=s1[i]));
if (j>n) then writeln ('NO') else begin
s2:=copy(s2,1,i-1)+pr(copy(s2,i,j-i+1))+copy(s2,j+1,255);
writeln ( i,' ',j,' -',s2,' ');
end;
end;
readln;
end.

Не знаю, будет ли он работать во всех случаях (по идее должен), но по нему вариант "Нет" очень даже возможен. Другого способа чего-то в голову не приходит.

Сообщение отредактировано: volvo - 2.11.2006 13:56

[Michael_Rybak]

В условии сказано: подпоследовательностей с четным кол-вом единиц.

Это значит, что любой нолик можно перевернуть, правильно? Это ведь подпоследовательность длины 1, с четным количеством (0) единиц.

Тогда идея такая:

1. Заменяем все нолики единичками

2. Если n четное, переворачиваем всю строку, получаем все нули. Если нечетное, то переворачиваем со второго по последний, потом второй превращаем обратно в единицу, потом переворачиваем первые два. Например:

11111
10000 - перевернули 2-5
11000 - перевернули 2-2
00000 - перевернули 1-2

Таким образом, любую строку мы превратили в строку нулей.
А теперь заменяем нужные нули на единицы.

Единственный случай, когда это не работает - это когда первая строка - "1", а вторая - "0". Тогда нельзя сделать "потом *второй* превращаем обратно в единицу", потому что второго нету.

На приведенном примере:

9
100011100
001011001


100011100

Заменяем нули единицами.

2-2: 110011100
3-3: 111011100
4-4: 111111100
8-8: 111111110
9-9: 111111111

Превращаем всё в нули:

2-9: 100000000
2-2: 110000000
1-2: 000000000

Строим то, что нужно:

3-3: 001000000
5-5: 001010000
6-6: 001011000
9-9: 001011001

Ответ:

да
2 2
3 3
4 4
8 8
9 9
2 9
2 2
1 2
3 3
5 5
6 6
9 9


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

[Coder_perm]

В условии сказано: подпоследовательностей с четным кол-вом единиц.

Это значит, что любой нолик можно перевернуть, правильно? Это ведь подпоследовательность длины 1, с четным количеством (0) единиц.

ИМХО ты немного не правильно понял условие задачи:

1. Переворачивать, не значит менять 0 на 1 и обратно.
Это значит, что последовательность 110000 перевернется в 000011, а не в 001111.

2. Каждое переворачиваение должно происходить только с четным количеством элементов последовательности, а не общее число перевернутых элементов должно быть четным.

[Michael_Rybak]

>1. Переворачивать, не значит менять 0 на 1 и обратно.
мдя. что есть то есть

>с четным количеством элементов последовательности
Ну там сказано не элементов, а именно единиц. Т.е. в переворачиваемой последовательности количество элементов, равных единице, должно быть четным.

Сорри за неправильную интерпретацию.

[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

[Michael_Rybak]

А эту задачу можно сдать на каком-нибудь онлайн архиве?

[Lapp]

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

Транзитивность означает существование преобразования, которое (в твоем случае) сразу переводит А в С. А это не только неочевидно, но и неверно.
А: 1100 0011
В: 0011 0011
С: 0011 1100
Найдешь преобразование, переводящее из А в С?
Впрочем, транзитивность ты и не используешь . Обратимость же действительно важна.

Мне кажется, такое понимание переворачивания (имени Coder_perm) тоже спорно и не особо лучше первоначального варианта. Нет возможности узнать достоверно, что имеется в виду?

[volvo]

Нет возможности узнать достоверно, что имеется в виду?

Ну, если автор пишет:

Пример:
011010010 010101010
{011010010
все символы
010010110
с 4 по 7
010101010}

, то очевидно, что имеется в виду именно вариант переворачивания "имени Coder_perm" ©...

[Michael_Rybak]

>Найдешь преобразование, переводящее из А в С?

А чего придираться?

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

>транзитивность ты и не используешь
В том то и дело, что использую. Использую для того, чтобы канонический вид имел право выступать в качестве промежуточного звена. Если бы транзитивности у преобразований не было (преобразований, очевидно, в смысле цепочек переворотов), то от канонического вида толку б не было.

[Lapp]

> > Найдешь преобразование, переводящее из А в С?
> А чего придираться?
???

> Понятно, что я имел ввиду, что преобразование - это цепочка переворотов,
> а не один переворот. Т.е. "если из строки А путем нескольких переворотов ..." и т. д.
Вообще, транзитивность обычно не применяется к бинарным операциям. Обычно это свойство операций сравнения (a<b, b<c => a<c). Я просто попытался распространить это на бинарные операции (что, впрочем, не имеет особого смысла, так как в группах выражается свойством принадлежности результата операции к группе). То, что ты имел в виду на самом деле означает, что если операцию удалось произвести два раза, то это можно повторить - что настолько очевидно, что непонятно, у кого может возникнуть вопрос. Попробуй перенести свое понятие на обычные числа (скажем, на группу целых чисел по сложению), и ты поймешь, что это "свойство" абсолютно ничего не добавляет

> >транзитивность ты и не используешь
> В том то и дело, что использую. Использую для того, чтобы канонический вид
> имел право выступать в качестве промежуточного звена. Если бы транзитивности
> у преобразований не было (преобразований, очевидно, в смысле цепочек
> переворотов), то от канонического вида толку б не было.
Повторяю, речь идет только о возможности выполнять законные преобразования, которая, конечно, есть всегда. Существования обратной операции вполне достаточно. Подумай над этим.

В целом решение интересное, но некоторые моменты мне не ясны..
Ты пишешь:
> плавающая единица образует две группы, одна из которых
> обязательно будет четной, а другая нечетной,
А почему это? Известно, что количество нулей сохраняется, и если оно изначально было четным, то будет четным и в конце. Соответственно, оно будет разбито на чет-чет или нечет-нечет..
Что я упустил?

[Michael_Rybak]

> > > Найдешь преобразование, переводящее из А в С?
> > А чего придираться?
> ???

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

>и ты поймешь, что это "свойство" абсолютно ничего не добавляет
ок, я согласен с некоторой аксиоматичностью этого свойства. Мне все же кажется, что так оно, все таки, нагляднее - можем из А получить канон., из В получить канон (=> по обратимости можем из канон. получить В), потому, по транзитивности, из А можем В.

Согласен, что транзитивность можно было при этом не упоминать.

> плавающая единица образует две группы, одна из которых
> обязательно будет четной, а другая нечетной,
А почему это? Известно, что количество нулей сохраняется, и если оно изначально было четным, то будет четным и в конце. Соответственно, оно будет разбито на чет-чет или нечет-нечет..
Что я упустил?

Мы смотрим не на четность количества нулей, а на само количество нулей.

Для примера, рассмотрим все канонические битовые строки длины 10, в которых встречается ровно 4 единички. По ходу считаем для них наш инвариант I.

1111000000 - <>1<>1<>1<>1<000000> - I = 6
1110100000 - <>1<>1<>1<0>1<00000> - I = 5
1110010000 - <>1<>1<>1<00>1<0000> - I = 4
1110001000 - <>1<>1<>1<000>1<000> - I = 3
1110000100 - <>1<>1<>1<0000>1<00> - I = 2
1110000010 - <>1<>1<>1<00000>1<0> - I = 1
1110000001 - <>1<>1<>1<000000>1<> - I = 0

Получается, что значение инварианта различно для всех возможных канонических строк.

Когда я говорил, что "плавающая единица образует две группы, одна из которых обязательно будет четной, а другая нечетной", я имел ввиду не количество нулей в группах, а порядковый номер групп.

Вообще, во всем решении, говоря о "нечетных" группах, я говорил о порядковом номере. Т.е. мы просто идем по строке слева направо, сладывая кол-во нулей в группах, и каждую вторую группу при этом игнорируем.

Тогда получается, что плавающая единица образует две группы - слева от нее, и справа от нее. И одну из них (например, левую) мы все время учитываем в сумме, а другую - нет. Левую, или правую - зависит от кол-ва единиц.

[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]

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

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