{
ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН'02 - 16 ноември 2002
ТЕМА ЗА 9 – 10 КЛАС (ГРУПА B)

Задача 3.  ЧИСЛОРЕД

Напишете програма GRADE.EXE, която по зададена редица от цели положителни
числа намира такива, колкото може по-малко на брой измежду тях, които, ако
бъдат отстранени от редицата, тя ще се окаже не намаляваща (всяко число в нея
ще се предхожда само от по-малки или равни на него).

Входните данни съдържат единствен ред, в който са записани числата от
редицата, разделени с интервали.  Те са не повече от 1 000 000 на брой, като
всяко от тях е не по-голямо от 30 000.

Резултатът съдържа един ред с поредните номера на намерените числа, разделени
с интервали (броенето започва от 1). Входните данни са такива, че в изхода
винаги ще има поне едно число.

Входните данни се четат от стандартния вход, а изходните данни се записват на
стандартния изход.

Пример.

Вход
3 1 2 0 5 4

Изход
1 4 5

(Възможен отговор е и 1 4 6)


РЕШЕНИЕ:

Едно възможно решение на задачата е да се генерират всички възможни не
намаляващи подредици на входната и от тях да се избере най-дългата (така ще
отстраним възможно най-малко числа от редицата). Това, обаче, ще отнеме ужасно
много време дори при сравнително малка редица, а максималният брой числа в
редицата може да е до 1 000 000.

Затова трябва да помислим за някакво по-добре решение. Една добра е идея да
намерим най-дългата възможна подредица, завършващата с определено число на
редицата. Прилагайки директно техниката на динамично оптимиране за тази идея,
ще получим:
 Seq[i] = max(1, Seq[j]+1 | за всяко j: 1<=j<i и num[j]<=num[i])
където num[i] е i-тото число от редицата, а Seq[i] е дължината на най-дългата
подредица завършваща с i-тото число, а j-тото число са евентуалните
предпоследни числа в търсената подредица. За по-кратко записване ще използваме
<i,s> за подредица завършваща с i-тото число, имаща дължина равна на s
(някаква стойност).
За да намерим отговора на за задачата ще трябва да намерим <1,Seq[1]>,
<2,Seq[2]>, . . ., <N,Seq[N]> и от тях да изберем тази <R,Seq[R]>, за която
Seq[R] е най-голямо. Това може да стане по следния начин:
Seq[1] := 1;
R := 1;
for i := 2 to N do begin
  Seq[i] := 1;
  for j := 1 to i-1 do
    if (Seq[j] >= Seq[i]) and (num[j] <= num[i])
      then Seq[i] := Seq[j]+1;
  if Seq[i] > Seq[R] then R := i;
end;
Така реализирахме горната идея, но това решение има сложност О(N*N), което е
незадоволително при ограниченията в задачата. Да се опитаме да оптимизираме
това решение.

Нека разгледаме възможните стойности на <j,Seq[j]>, когато намираме
<i,Seq[i]>. Да допуснем че съществуват две различни стойности на j – j1 и j2
(т.е. 1<=j1<i, 1<=j2<i, j1<>j2), за които е изпълнено Seq[j1]=Seq[j2]=L. Без
ограничения можем да изберем j1-то число от редицата да бъде не по-голямо от
j2-to (т.е. num[j1]<=num[j2]). Тогава, когато търсим стойността на Seq[i],
можем да НЕ разглеждаме j=j2, защото:
  А) тя би ни дала <i,L+1>, ако е изпълнено num[j2]<=num[i]. Обаче
num[j1]<=num[j2]; следователно тогава num[j1]<=num[i] т.е. за j=j1 също ще
получим <i,L+1>.
  Б) Ако пък не е изпълнено num[j2]<=num[i], то j2-то число не може да бъде
предпоследно в подредица завършваща с i-тото число.
Това би ни дало някаква оптимизация стига да можем да го използваме добре. Да
правим някаква проверка за стойностите, които приема j в цикъла “for j := 1 to
i-1 . . .” би било трудно.
Да разгледаме по-внимателно j1 и j2 от горния пример. За тях е вярно
Seq[j1]=Seq[j2]=L и num[j1]<=num[j2]. Следователно за всяко j в интервала
[1,i-1], за което е вярно Seq[j]=L ни интересува само това j, за което num[j]
е минимално. Ето защо, е логично да поддържаме масив Last, който за всяко
възможна до момента дължина X, помни индекса j на най-малкото число от
редицата, за което е вярно Seq[j]=X, т.е. Last[X] е индекса на най-малкото
число от всички последни числа на подредици с дължина X. Да видим как този
масив може да ни помогне за намирането на Seq[i].

Нека първо изкажем твърдението, че Num[Last[p]]<=Num[Last[q]], при p<q, т.е.
ако от всички възможни най-дълги подредици, имащи дължина p, изберем тази
завършваща с най-малкото число (числото ще е Num[Last[p]]), нека тя е PSeq, и
ако от всички възможни най-дълги подредици, имащи дължина q, където q е
по-голямо от p, изберем тази завършваща с най-малко число(числото ще е
Num[Last[q]]), нека тя е QSeq, то последното число на PSeq ще е не по-голямо
от последното число на QSeq. Допускането на противното води до противоречие с
дефиницията на Last[p], защото след като “изтрием” последните q-p числа от
QSeq, ще получим подредица с дължина p, имаща последно число не по-голямо от
Num[Last[q]] (QSeq е не намаляваща), но Num[Last[p]]>Num[Last[q]];
следователно Last[p] не отговаря на дефиницията си и допускането е не вярно.

А сега да видим как ще намерим Seq[i]. Нека Longest=max(Seq[j]) за 1<=j<i,
т.е. Longest е дължината на на-дългата подредица до момента.
1сл.) Num[i]<Num[Last[1]] т.е. i-тото число е по-малко от всички числа до
момента (всички подредици с дължина 1). Според дефиницията на Last следва, че
Last[1]:=i;. Тъй като, i-тото число е най-малкото до момента, то не може да
бъде последен на елемент на подредици с дължина 2 или по-дълги, т.е.
Seq[i]:=1;.
2сл.) Num[i]>=Num[Last[Longest]] т.е. i-тото число е по-голямо или равно на
последното число на най-дългата подредица до момента. Следователно
Seq[i]=Longest+1. А оттук, Longest:=Longest+1; Last[Longest]:=i;
3сл.) Когато не са изпълнение условията от сл.1 и 2, търсим това j, за което е
изпълнено:
   *) Num[i] < Num[Last[j]] и
   *) Num[i] >= Num[Last[j-1]]
Токова j съществува поради два факта:
   I) Num[i] е в интервала [ Num[Last[1]], Num[Last[Longest]] ) – интервалът е
затворен отляво и отворен вдясно - вярно от това че сме стигнали до сл.3, а не
сл.1 или сл.2.
  II) Num[Last[p]]<=Num[Last[q]], при p<q.
Намирането на j става с двоично търсене, което става с log двоичен от Longest
на брой стъпки (сложност O(log Longest)). Оттук, Seq[i]:=j; Last[j]:=i;,
защото няма начин Seq[i]>j, понеже това означава, че има подредица до момента,
с дължина поне j, която завършва с число не е по-голямо от i-тото; но от
стойностите на масива Last се вижда, че няма такава; а пък има подредица с
дължина j-1, завършваща с число което не е по-голямо от i-тото и затова
Seq[i]=j.

Строейки масива по гореописания начин лесно може да се докаже по индукция, че
всеки негов елемент с индекс в интервала [1,Longest] има стойност при i>2.

И така se стига до програмата по-долу, за която ще отбележим че не ни е нужен
масива Seq! Нужни са ни само масива Num (съдържащ числата на началата редица),
масива Last (описан по-горе) и един масив Prev, който съдържа числото преди
i-тото в <i,Seq[i]> (предпоследното число в най-дългата подредица, завършваща
с i-тото число). Също така използвам един помощен масив Remove, за да маркирам
кои елементи трябва да бъдат махнати от началата редица, за да се получи
максимално дълга, не намаляваща подредица, но използването на този масив може
да се избегне.

Сложността на това решение е O(N*logR), където R е големината на най-дългата
не намаляваща редица; но R може да е равно на N, т.е. решението има сложност
O(N*logN) в най-лошия случай.

Kristiyan Haralambiev
}

program Chislored;
const
        InFile                  = ''; // when the name of a file is ''
        OutFile                 = ''; // the standard i/o is used
        Max                     = 1000*1000;
var
        N, Longest              : LongInt;
        Num                     : array[1..Max] of LongInt;
        Last, Prev              : array[1..Max] of LongInt;
        Remove                  : array[1..Max] of Boolean;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure InPut;
var
        F                       : Text;
begin
  Assign(F, InFile); ReSet(F);

  N := 0;
  repeat
    Inc(N);
    Read(F, Num[N]);
  until Eoln(F) or Eof(F);

  Close(F);
end;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure Solve;
var
        I, J, K, Mid            : LongInt;
begin
  FillChar(Prev, SizeOf(Prev), 0);

  Longest := 1;
  Last[1] := 1;

  for K := 2 to N do begin
    if Num[K] < Num[ Last[1] ] then Last[1] := K // case 1
    else if Num[K] >= Num[ Last[Longest] ] then begin // case 2
      Inc(Longest);
      Last[Longest] := K;
      Prev[K] := Last[Longest-1];
    end
    else begin // case 3
     //binary search
      I := 1;
      J := Longest;
      while J - I > 1 do begin
        Mid := (I + J) div 2;
        if Num[ Last[Mid] ] > Num[K] then J := Mid else I := Mid;
      end;
     //update - it is true that I = J-1
      Last[J] := K;
      Prev[K] := Last[I];
    end;
  end; //end of for K := ...
end;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure OutPut;
var
        K                       : LongInt;
        F                       : Text;
begin
  Assign(F, OutFile); ReWrite(F);
  FillChar(Remove, SizeOf(Remove), True);

  K := Last[Longest];
  repeat
    Remove[K] := False;
    K := Prev[K];
  until K = 0;

  for K := 1 to N do
    if Remove[K] then Write(F, K, ' ');
  WriteLn(F);

  Close(F);
end;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
begin
  InPut;
  Solve;
  OutPut;
end.