Број растућих сегмената - Решење

Груба сила

Задатак можемо решити анализирајући све сегменте датог низа \(a\) и за сваки сегмент \(a_i, a_{i+1}, ..., a_j\) где је \(0 \leq i < j < n\) проверити да ли је растући и у складу са тим увећати бројач растућих сегмената.

Број растућих сегмената за сваки леви крај

Ефикасније решење се може добити ако се провера монотоности врши инкрементално (да би се проверило да је сегмент \([i, j]\) растући довољно је да је \(a_j > a_{j-1}\) и да је сегмент \([i, j-1]\) растући или једночлан).

Време извршавања можемо унапредити и одсецањем. Приметимо да ако сегмент који чине елементи на позицијама \([i, j]\) није растући, онда нису растући ни сегменти \([i, j']\) за \(j \leq j' < n\), па за те сегменте не треба вршити проверу, што значи да је бројање растућих сегмената који почињу на позицији \(i\) могуће прекинути чим се пронађе неки сегмент који почиње на тој позицији и није растући.

Дакле, за сваку позицију \(i\) у низу (за свако \(0 \leq i < n-1\)) анализирамо један по један сегмент \([i, j]\) који на тој позицији почиње све док су ти сегменти растући и за сваки растући сегмент увећавамо бројач растућих сегмената за 1. Чим наиђемо на сегмент који није растући (тј. на елемент који је мањи од претходног), прелазимо на наредну позицију \(i\).

#include <iostream>
#include <vector>

using namespace std;

long long brojRastucihSegmenata(const vector<int>& a) {
  // velicina niza
  int n = a.size();
  // ukupan broj rastucih serija
  long long brojRastucih = 0;
  // za svaku poziciju u nizu
  for (int i = 0; i < n - 1; i++) {
    // pronalazimo sve rastuce serije koje pocinju na toj poziciji
    // proveru da li je serija odredjena pozicijama [i, j] rastuca
    // odredjujemo inkrementalno
    // postupak prekidamo cim se naidje na seriju koja nije rastuca
    for (int j = i + 1; j < n; j++)
      if (a[j] > a[j-1])
        brojRastucih++;
      else
        break;
  }
  return brojRastucih;
}


int main() {
  ios_base::sync_with_stdio(false);
  // ucitavamo niz
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++)
    cin >> a[i];
  // ispisujemo ukupan broj rastucih serija
  cout << brojRastucihSegmenata(a) << endl;

  return 0;
}

Максимални растући сегменти

Приметимо да у претходном примеру анализирајући растући сегмент који почиње од елемента \(a_0\) пролазимо и по растућим сегментима низа који почињу са \(a_1\) и \(a_2\). Ако је сегмент \([a_i, a_{i+1}, ..., a_{j}]\) растући, онда унапред знамо да су растући и сегменти \([a_i, a_{i+1}]\), \([a_i, a_{i+1}, a_{i+2}]\), \(\ldots\), \([a_i, a_{i+1}, \ldots, a_{j}]\), затим \([a_{i+1}, a_{i+2}]\), \(\ldots\), \([a_{i+1}, a_{i+2}, \ldots, a_{j}]\), па све до \([a_{j-1}, a_j]\), а да сегменти \([a_i, a_{i+1}, \ldots, a_{j+1}]\), \(\ldots\), \([a_i, a_{i+1}, \ldots, a_{n-1}]\), затим \([a_{i+1}, a_{i+2}, \ldots, a_{j+1}]\), \(\ldots\), \([a_{i+1}, a_{i+2}, \ldots, a_{n-1}]\) итд., закључно са \([a_{j}, \ldots, a_{n-1}]\) нису растући. Дакле, за сваку позицију из интервала \([i, j]\) тачно знамо све растуће сегменте који на њој почињу.

Растући сегмент \([a_i, a_{i+1}, \ldots, a_{i+k-1}]\) дужине \(k\) у себи садржи:

• \(k-1\) растућих сегмената који почињу са \(a_i\)

• \(k-2\) растућих сегмената који почињу са \(a_{i-1}\)

• …

• \(1\) растући сегменат који почињe са \(a_{i+k-2}\)

укупно \((k-1) + (k-2) + ... + 1\) растућих сегмената што износи \(\frac {k \cdot (k - 1)}{2}\).

До истог закључка можемо доћи и на следећи начин: сваки подсегмент \(a_p, a_{p+1}, \ldots, a_q\) где је \(i \leq p < q \leq i+k-1\) растућег сегмента \(a_i, a_{i+1}, ..., a_{i+k-1}\) је растући, почетак \(p\) и крај \(q\) подсегмента можемо изабрати на \(\frac {k \cdot (k - 1)}{2}\) начина.

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

Према томе, у петљи анализирамо низ члан по члан почев од првог члана (\(i = 0\)) и одређујемо дужину \(t\) текућег растућег сегмента (ако је \(a_i < a_{i+1}\) увећавамо \(t\) за 1). Када дођемо до краја текућег растућег сегмента увећамо укупан број растућих сегмената \(br\) за \(\frac{t \cdot (t - 1)}{2}\) и почињемо анализу следећег растућег сегмента (\(t = 1\)). До краја максималног растућег сегмента се може стићи на два начина: или када је \(a_i \geq a_{i+1}\) или када се дође до краја низа. Напоменимо да за тај последњи растући сегмент увећавамо укупан број растућих сегмената изван петље (честа грешка је да се то заборави).

У сваком тренутку је довољно поредити само два суседна члана низа, тако да није неопходно цео низ памтити у меморији, већ само два суседна члана низа (претходни и текући).

#include <iostream>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  int prethodni;
  cin >> prethodni;
  // ukupan broj rastucih serija
  long long brojRastucih = 0;
  // duzina tekuce rastuce serije
  long long duzinaTekuceRastuce = 1;
  for(int i = 1; i < n; i++) {
    int tekuci;
    cin >> tekuci;
    if (tekuci > prethodni)
      // tekuci element produzava tekucu rastucu seriju
      duzinaTekuceRastuce++;
    else {
      // tekuci element zapocinje novu rastucu seriju
      // dodajemo sve rastuce serije koje su podserije rastuce serije
      // koja se zavrsila sa prethodnim elementom
      brojRastucih += (duzinaTekuceRastuce - 1) * duzinaTekuceRastuce / 2;
      duzinaTekuceRastuce = 1;
    }
    prethodni = tekuci;
  }
  // dodajemo sve rastuce serije koje su podserije poslednje rastuce
  // serije
  brojRastucih += (duzinaTekuceRastuce - 1)*duzinaTekuceRastuce/2;
  cout << brojRastucih << endl;
  return 0;
}