Најдужа серија победа - Решење

Груба сила

Постоји неколико начина да се наивно приступи решавању овог проблема и сви претпостављају да су у програму резултати утакмица смештени у низ. Врло је вероватно да би сваки програмер са имало искуства избегао оваква решења, али приказаћемо их, да бисмо систематично илустровали неке технике поступне оптимизације кода.

Једно веома наивно решење је да анализирамо све могуће сегменте низа одређене свим могућим вредностима променљивих \(0 \leq i \leq j < n\). Њих можемо набројати угнежђеним петљама. За сваки сегмент можемо применом линеарне претраге проверити да ли садржи само победе и ако садржи, ажурирати максимум у складу са тим.

#include <iostream>
#include <vector>

using namespace std;

// izracunava duzinu najduze serije pobeda za dati niz rezultata utakmica
int najduzaSerijaPobeda(const vector<int>& a) {
  // broj utakmica
  int N = a.size();

  // duzina najduze serije pobeda
  int maxDuzina = 0;
  // analiziramo sve segmente a[i, j]
  for (int i = 0; i < N; i++) {
    for (int j = i; j < N; j++) {
      // proveravamo da li su u segmentu a[i, j] samo pobede
      bool samo_pobede = true;
      for (int k = i; k <= j; k++)
        if (a[k] != 1) {
          samo_pobede = false;
          break;
        }
      // ako jesu, azuriramo maksimum u odnosu na duzinu segmenta [i, j]
      if (samo_pobede)
        maxDuzina = max(maxDuzina, j - i + 1);
    }
  }

  return maxDuzina;
}

int main() {
  ios_base::sync_with_stdio(false);
  // ucitavamo rezultate svih utakmica u niz
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++)
    cin >> a[i];
  // ispisujemo duzinu najduze seriju pobeda
  cout << najduzaSerijaPobeda(a) << endl;
}

Најдужа серија за сваки леви крај

Мало бољи приступ је да за сваку партију \(i\) одредимо најдужи сегмент победа који почиње на тој позицији. То се може урадити тако што се сегмент који почиње на позицији \(i\) проширује од позиције \(i\) надесно, све док се у њему налазе само победе. Ако знамо да су све победе у неком интервалу \([i, j]\) и да је победа и у утакмици \(j+1\), аутоматски знамо да су све победе и у интервалу \([i, j+1]\), чиме вршимо важну уштеду јер не морамо да анализирамо поново све елементе тог интервала (кажемо да проверу вршимо инкрементално).

Када се наиђе на први пораз (или на крај), нађен је најдужи сегмент победа који почиње на позицији \(i\), јер ће сва продужавања сегмента надесно, ако их има, садржати и тај пораз и неће више представљати серије победа. Дакле, на овом месту вршимо одсецање претраге прескачући многе сегменте за које се унапред зна да не могу задовољити наметнути услов. Поређење са максималном дужином вршимо тек када максимално проширимо текући сегмент, јер унапред знамо да су сви подсегменти тог максимално проширеног сегмента краћи од њега (и овде заправо вршимо одређено одсецање).

#include <iostream>
#include <vector>

using namespace std;

// izracunava duzinu najduze serije pobeda za dati niz rezultata utakmica
int najduzaSerijaPobeda(const vector<int>& a) {
  // broj utakmica
  int N = a.size();

  // duzina najduze serije pobeda
  int maxDuzina = 0;
  // za svaku poziciju i odredjujemo duzinu najduze serije pobeda koja
  // pocinje na poziciji i
  for (int i = 0; i < N; i++) {
    int duzina = 0;
    for (int j = i; j < N && a[j] == 1; j++)
      duzina++;
    // ako je duzina serije koja se zavrsava na poziciji i veca od
    // maksimalne do tada vidjene duzine, azuriramo maksimalnu duzinu
    if (duzina > maxDuzina)
      maxDuzina = duzina;
  }

  return maxDuzina;
}


int main() {
  ios_base::sync_with_stdio(false);
  // ucitavamo rezultate svih utakmica u niz
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++)
    cin >> a[i];
  // ispisujemo duzinu najduze seriju pobeda
  cout << najduzaSerijaPobeda(a) << endl;
}

Овај приступ се може додатно значајно убрзати даљим одсецањем.

Подела на максималне серије узастопних победа

За сваку позицију \(i\) одређујемо дужину најдужег сегмента победа који почиње на позицији \(i\). Једном када одредимо да је то сегмент \([i, j]\), време значајно можемо уштедети тако што приметимо да ни један сегмент победа који почиње на позицијама након \(i\), а закључно са \(j\) не може бити дужи од сегмента који почиње на позицији \(i\) (јер ако позиција \(j\) није последња у низу, на позицији иза ње се налази пораз). Зато је након ширења сегмента који почиње на позицији \(i\) надесно и одређивања серије победа који почињу на позицији \(i\) могуће директно прећи на израчунавање најдужег сегмента победа који почиње на позицији \(j+1\) (ако таква постоји) и прескачемо анализу сегмената који почињу на позицијама између \(i+1\) и \(j\) (вршимо одсецање).

Овај алгоритам је заправо и врло интуитиван и вероватно је први алгоритам који би програмер са мало искуства имплементирао: крећемо од почетка, проналазимо серију победа који почиње на почетку, након тога тражимо наредну серију победа која наступа након те прве серијe, затим серију победа која наступа након те друге серије итд. Дакле, цео низ делимо на мање сегменте, такве да је сваки од њих оптималан у смислу да га није могуће продужити (ни на лево, ни на десно) и анализирамо само њих.

Током имплементације није неопходно да памтимо резултате свих утакмица истовремено у низу. У једној петљи ћемо читати резултате мечева и у сваком тренутку одржавати дужину текуће и дужину најдуже до тада пронађене серије (сегмента) победа. Пошто на почетку нисмо видели још ни један резултат, обе променљиве иницијализујемо на нулу. Затим, у петљи, учитавамо и обрађујемо резултате утакмица. Ако је тим победио, тада текућа утакмица продужава текућу серију победа и њену дужину увећавамо за један. Ако је тим изгубио, тада се прекида евентуална серија победа и текућа серија победа има дужину 0 (јер је утакмица којом та серија почиње изгубљена).

Након завршетка читања сваке серије победа потребно је ажурирати дужину најдуже серије (ако је дужина текуће серије дужа од до тада најдуже, потребно је дужину најдуже поставити на дужину текуће). То се дешава или када се наиђе на утакмицу у којој је тим поражен или након петље, када је последња евентуална серија победа завршена. Треба бити веома обазрив да се не заборави на последњу серију победу, тј. да се не заборави поређење текуће и најдуже серије након завршетка петље.

#include <iostream>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);

  // broj utakmica
  int N;
  cin >> N;
  // duzina tekuce serije pobeda
  int duzinaTekuce = 0;
  // duzina najduze do sada vidjene serije pobeda
  int duzinaNajduze = 0;
  // ucitavamo podatke o svim utakmicama
  for (int i = 0; i < N; i++) {
    // rezultat utakmice
    int rezultat;
    cin >> rezultat;
    if (rezultat == 1) {
      // ako je tim pobedio, to produzava tekucu seriju pobeda
      duzinaTekuce++;
    } else {
      // ako je upravo prekinuta serija pobeda duza od najduze,
      // azuriramo duzinu najduze
      if (duzinaTekuce > duzinaNajduze)
        duzinaNajduze = duzinaTekuce;
      // procitali smo poraz, pa u tekucoj seriji nema pobeda
      duzinaTekuce = 0;
    }
  }
  // vrsimo proveru i za poslednju seriju
  if (duzinaTekuce > duzinaNajduze)
    duzinaNajduze = duzinaTekuce;

  // ispisujemo konacan rezultat
  cout << duzinaNajduze << endl;
  return 0;
}

Најдужа серија за сваки десни крај грубом силом

Могуће је грубом силом одредити и оптимум за сваки фиксирани десни крај.