6. Oválna pracovňa vzorové riešenie

Zadanie

Nie je to tak dávno, čo sa do našej oválnej pracovne nasťahoval nový Týpek. Ako to už býva zvykom, nový týpek – nové nápady. A tak hneď ako ho napadol ten najlepší, zvolal svojich poradcov do oválnej pracovne. Za okrúhlym stolom im predostrel ideu postavenia veľkého múru pred nepriateľmi. Ako ale istá americká štúdia ukázala: čím bývajú nepriatelia viac na východ, tým sú nebezpečnejší. Preto musí byť múr na východe vyšší, alebo aspoň rovnako vysoký ako na západe.

Po nekonečných rokovaniach sa všetci v oválnej pracovni zhodli, že naša krajina je v ohrození a treba začať so stavbou ihneď. Ešteže zostalo v oválnej pracovni pod stolom zopár betónových stĺpov jednotkovej šírky. Stavbu teda môžeme zahájiť, no tak ako to pri veľkých projektoch býva potrebujeme plán, ten najlepší plán.

Hoci postavenie múru nie je vôbec populistické, zlé jazyky nás môžu začať ohovárať, preto musí mať náš múr aj nejaký hlboký zmysel, napríklad umelecký. Aby sme teda pred svetom nevyzerali ako barbari, musí sa postaviť múr esteticky, teda tak, aby rozdiel výšok medzi ľubovoľnými susednými betónovými stĺpmi bol rovnaký. Okrem toho je tu už spomínaný fakt, že nepriatelia na východe sú nebezpečnejší. Preto musia výšky jednotlivých stĺpov v múre tvoriť od západu na východ neklesajúcu postupnosť.

Na obrázku môžete vidieť päť rôznych múrov.

Prvé dva z nich sú dobré. Tretí je zlý, pretože výšky stĺpov netvoria neklesajúcu postupnosť. Štvrtý tak isto (tam stĺpy tvoria klesajúcu postupnosť). Piaty múr je zlý, lebo rozdiely medzi výškami susedných stĺpov nie sú všade rovnaké.

Pomôžte zachrániť krajinu pred čo najviac nepriateľmi a navrhnite čo najdlhší múr z materiálov, ktoré sú k dispozícií.

Úloha

Máme \(n\) betónových stĺpov s danými výškami. Zistite najväčšiu možnú dĺžku (počet použitých stĺpov) neklesajúceho múru ktorý vieme postaviť tak, aby v postavenom múre mali každé dva susedné betónové stĺpy rovnaký rozdiel výšok. Nemusíte použiť všetky stĺpy zo vstupu.

Formát vstupu

Na prvom riadku vstupu dostanete kladné celé číslo \(n\). V druhom riadku bude \(n\) medzerou oddelených nezáporných celých čísel \(a_1, a_2, ..., a_n\) reprezentujúcich výšky jednotlivých stĺpov.

Je päť testovacích sád. Pre jednotlivé sady platia nasledovné obmedzenia:

číslo sady	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)
\(n \leq\)	\(20\)	\(100\)	\(500\)	\(1\,000\)	\(3\,000\)
\(a_i \leq\)	\(10^3\)	\(10^3\)	\(10^3\)	\(10^9\)	\(10^9\)

Formát výstupu

Na výstup vypíšte jediné číslo – počet použitých stĺpov v najdlhšom možnom múre spĺňajúcom podmienky zo zadania.

Príklad

Input:

4
2 3 4 1

Output:

4

Zjavne dokážeme postaviť múr zo všetkých našich stĺpov a tiež splniť estetickú podmienku, stačí postaviť stĺpy v poradí 1, 2, 3, 4

Input:

5
2 1 5 2 4

Output:

2

Najdlhší múr vieme postaviť napríklad zo stĺpov výšok 2 a 4

Zadanie od nás vyžaduje postaviť taký múr, že rozdiely susedných stĺpov budú všade rovnaké. To ale znamená, že výšky našich stĺpov majú tvoriť aritmetickú postupnosť. A síce výšky stĺpov vyberáme z množiny danej množiny, ak si stĺpy usporiadame podľa výšky, zmení sa náš problém na hľadanie najdlhšej aritmetickej podpostupnosti. Dokonca v zadaní je napísané, že hľadáme neklesajúcu postupnosť a preto usporiadaním stĺpov nestratíme žiadne riešenie.

Aké aritmetické podpostupnosti sa tu nachádzajú?

Aritmetická postupnosť je definovaná 2 číslami – prvým prvkom a diferenciou. Na to, ktorý prvok vybrať ako prvý máme \(n\) možností. A pri určovaní diferencie si uvedomme, že diferencia musí byť naozaj rozdiel niektorých dvoch prvkov z našej postupnosti. V opačnom prípade totiž nevytvoríme ani podpostupnosť dĺžky 2. Máme teda najviac \(n^2\) možných diferencií. Pre každý začiatočný prvok a diferenciu vieme zistiť, aká dlhá aritmetická postupnosť má takúto charakteristiku a vybrať to najdlhšie riešenie. Zložitosť takéhoto riešenia bude \(O(n^4)\).

Rýchlejšie riešenie

Treba si ale uvedomiť, že prvý prvok nás až tak nezaujíma. Stačí si určiť hodnotu diferencie \(d\). Následne si vieme klásť otázku, aká by bola dĺžka najdlhšej aritmetickej podpostupnosti s diferenciou \(d\), ktorej posledný prvok leží v usporiadanom poli výšok na pozícii \(x\). Túto najväčšiu dĺžku si označme \(P[d][x]\).

Pre dané \(d\) budeme túto hodnotu počítať postupne pre čoraz väčšie hodnoty \(x\) – teda naše pole budeme predcházdať zľava doprava. Nech \(x\)-tá výška má hodnotu \(A[x]\). Potom vieme, že predposledný prvok tejto aritmetickej postupnosti musel mať hodnotu \(A[x]-d\). Musíme, preto zistiť, na ktorom mieste v našom poli sa nachádza táto hodnota.

Jedna možnosť je, že hodnota \(A[x]-d\) sa medzi našimi výškami nenachádza. V takom prípade je \(P[d][x]=1\), lebo pre danú hodnotu diferencie nemohol existovať skorší prvok. V druhej možnosti, nech je hodnota \(A[x]-d\) na indexe \(y\). Potom zase vieme, že dĺžka najdlhšej podpostupnosti končiacej na indexe \(x\) bude \(P[d][x] = 1 + P[d][y]\). A keďže \(y < x\), tak hodnotu \(P[d][y]\) už máme vypočítanú.

Pre každú kladnú diferenciu \(d\) (0 ošetríme zvlášť) teda prejdeme poľom A[] a vyplníme pole P[d][]. Jediné, čo potrebujeme vedieť robiť rýchlo je povedať, na ktorom indexe, ak vôbec, leží nejaké číslo. Toto môžeme robiť pomocou setu v čase \(O(\log n)\), alebo pomocou hash tabuľky v čase \(O(1)\). Dokopy dostaneme časovú zložitosť \(O(n^3)\).

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  vector<int> stlpy(n);
  for (int i = 0; i < n; i++)
    scanf("%d", &stlpy[i]);
  sort(stlpy.begin(), stlpy.end());
  int odpoved = 1;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      int d = stlpy[j] - stlpy[i];
      // v tejto hash mape si na indexe x pamatame dlzku
      // najdlhsej aritmetickej postupnosti konciacej prvkom s hodnotou x
      unordered_map<int, int> najdlhsia;
      for (int k = 0; k < n; k++) {
        int moznaodpoved = 1, hodnotapredosleho = stlpy[k] - d;
        if (najdlhsia.find(hodnotapredosleho) != najdlhsia.end()) {
          moznaodpoved += najdlhsia[hodnotapredosleho];
        }
        odpoved = max(odpoved, moznaodpoved);
        najdlhsia[stlpy[k]] = moznaodpoved;
      }
    }
  }
  printf("%d\n", odpoved);

  return 0;
}

Vzorové riešenie

To už ale nie sme ďaleko od vzorového riešenia. Stačí si uvedomiť, že diferenciu si nepotrebujeme určovať dopredu. Aritmetickú postupnosť predsa jednoznačne určujú aj jej posledné dva prvky.

Takže našu otázku upravíme: aká by bola dĺžka najdlhšej aritmetickej postupnosti, ak by posledné dva prvky boli na indexoch \(x\) (posledný prvok) a \(y\) (predposledný prvok)? Označme si túto hodnotu \(D[x][y]\).

Je jasné, že diferencia takejto postupnosti je \(d=A[x]-A[y]\). Opäť nás teda bude zaujímať, na ktorom indexe, ak vôbec, leží číslo \(A[y]-d\). V prípade, že táto hodnota sa v poli nenachádza, tak \(D[x][y]=2\), pretože tieto dva prvky tvoria našu postupnosť a nič iné pred nimi nemôže byť. Ak sa však hľadaná hodnota nachádza na indexe \(z\), tak platí, že \(D[x][y] = 1 + D[y][z]\).

Tak ako v predchádzajúcom riešení budeme pole D[][] vypĺňať postupne od najmenších hodnôt \(x\) a \(y\), aby sme na riešenie s veľkými hodnotami mohli použiť tie s malými. Na určenie indexu, na ktorom sa nachádza nejaká hodnota použijeme hash tabuľku. Každú hodnotu v našej tabuľke preto vieme vypočítať v konštantnom čase, čo vedie k zložitosti \(O(n^2)\).

#include <bits/stdc++.h>

using namespace std;
int n, vysledok = 1;
vector<int> vysky;
int main() {
  cin >> n;
  vector<vector<int>> D(n, vector<int>(n, 1));
  vysky.resize(n);
  for (int i = 0; i < n; i++)
    cin >> vysky[i];
  sort(vysky.begin(), vysky.end());
  for (int i = 0; i < n; i++) {
    unordered_map<int, int>
        videne; // pre kazdu hodnotu si pamatame kde v poli sa nachadza
    for (int j = 0; j < i; j++) {
      int diferencia = vysky[i] - vysky[j];
      auto it = videne.find(vysky[j] - diferencia);
      if (it == videne.end())
        D[i][j] = 2;
      else
        D[i][j] = 1 + D[j][it->second];
      videne[vysky[j]] = j;
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++)
      vysledok = max(vysledok, D[i][j]);
  }
  cout << vysledok << endl;
  return 0;
}