5. O Vlejdovom bicykli vzorové riešenie

Zadanie

Vlejd chce bicykel, a ako správny hipster sa rozhodol, že si ho postaví sám. Základom bicykla je, samozrejme, trojuholníkový¹ rám (na obrázku ružovou). Naň si Vlejd zohnal niekoľko starých kovových rúriek, z ktorých plánuje tri vybrať a pozvárať ich do tvaru trojuholníka. Následne chce rám natrieť hipsterskou ružovou farbou, ktorej má toľko, že ňou vie natrieť rúrky, ktoré sú spolu dlhé \(d\) centimetrov.

Keďže by bola škoda po otvorení nepoužiť všetku ružovú farbu (zvyšok by zaschol a musel by sa vyhodiť), chce zistiť, či sa medzi jeho rúrkami nachádzajú tri také, ktoré tvoria trojuholník s obvodom presne \(d\) centimetrov. (Ak také rúrky nemá, farbu si ušetrí na neskôr, vyberie iné rúrky a rámu uháčkuje slušivý obal z tyrkysovej priadze.) Pomôžete mu?

Úloha

Na vstupe dostanete obvod \(d\), počet rúrok \(n\) a dĺžky jednotlivých rúrok \(r_1, \dots, r_n\).

Zistite, či sa z niektorých troch rúrok (môže sa stať, že viacero rúrok je rovnako dlhých, ale každú môžete použiť len raz) dá poskladať trojuholník s obvodom \(d\).

Formát vstupu

Na prvom riadku vstupu je počet testovacích sád \(t\).

Nasledujú dva riadky pre každú sadu (dokopy \(2t\) riadkov). Na prvom riadku sú vždy dve celé čísla \(n\) a \(d\) (\(1 \leq d \leq 10^9\)) – počet rúrok a obvod trojuholníka. Na druhom riadku je \(n\) celých čísel \(r_1, \dots, r_n\) – dĺžky rúrok.

Pre jednotlivé vstupy platia nasledovné obmedzenia:

Číslo vstupu	1	2	3	4	5	6
\(t\)	\(1\,000\)	\(1\,000\)	\(500\)	\(200\)	\(100\)	\(50\)
Maximálne \(n\)	\(10\)	\(50\)	\(200\)	\(1\,000\)	\(2\,000\)	\(5\,000\)
Maximálne \(r_i\)	\(1\,000\)	\(1\,000\)	\(10^8\)	\(10^6\)	\(10^9\)	\(10^9\)

Formát výstupu

Pre každú testovaciu sadu vypíšte jeden riadok obsahujúci slová DA SA ak sa z rúrok na vstupe dá poskladať trojuholník s daným obvodom a NEDA SA inak.

Príklad

Input:

3
2 10
6 4
5 12
1 2 3 4 5
4 12
11 1 10 1

Output:

NEDA SA
DA SA
NEDA SA

V prvom prípade nemáme dosť rúrok na trojuholník; v druhom prípade môžeme postaviť trojuholník 3-4-5; v treťom prípade síce platí, že \(1+1+10 = 12\), ale trojuholník z toho ani Vlejd nespraví.

---

1. Vlejd má rád trojuholníky. Viď príklad 6 z ostatnej série.↩

Na získanie 7-8 bodov za tento príklad stačilo bruteforce riešenie “vyskúšame všetky trojice” s časovou zložitosťou \(O(n^3)\). (Samozrejme, aj tu si treba dať pozor na to, že ak tri rúrky majú tvoriť trojuholník, musí pre ne platiť, že súčet dĺžok ľubovoľných dvoch rúrok je väčší než dĺžka tretej rúrky).

Riešenie vieme zlepšiť využitím informácie o obvode trojuholníka. Namiesto zmýšľania v štýle “vyskúšame všetky trojice, či náhodou nebudú mať súčet \(d\),”, použijeme štýl “vyskúšame dvojice, dopočítame si dĺžku tretej strany trojuholníka a overíme či máme tyčku správnej dĺžky.” Overenie sa dá spraviť napríklad binárnym vyhľadávaním, čím by sme dosiahli časovú zložitosť \(O(n^2 \log n)\). Aby sme vedeli binárne vyhľadávať, musíme na začiatku algoritmu pole utriediť, ale to nie je žiaden problém, pretože zložitosť triedenia je \(O(n \log n)\).

Ešte lepšie riešenie vieme dosiahnuť prístupom: “Vyskúšame všetky možnosti pre najdlhšiu rúrku, jej dĺžku označíme \(r_i\), a pokúsime sa zistiť, či sa medzi paličkami nachádzajú dve so súčtom dĺžok \(d - r_i\), pričom obe sú nanajvýš také dlhé ako \(r_i\).”

Prečo nám toto pomôže? Pretože v utriedenom poli čísel vieme nájsť dve také, ktoré majú súčet \(x\), v lineárnom čase. Stačí použiť dvoch bežcov: dva pointre ukazujúce do poľa, na začiatku inicializované na začiatok a koniec poľa. Pokiaľ je súčet prvkov, na ktoré ukazujú, menší ako \(x\), posunieme ľavý pointer doprava. Pokiaľ je súčet prvkov, na ktoré ukazujú, väčší ako \(x\), posunieme pravý pointer doľava. Ak je súčet rovný \(x\), našli sme prvky, ktoré sme hľadali. Nuž a pokiaľ sa stane, že ľavý pointer je napravo od pravého pointra, v poli sa nenachádzajú také dva prvky, ktorých súčet by bol \(x\).

Prehoďme pár slov o tom, prečo to funguje a prečo to má lineárnu časovú zložitosť. Pokúšame sa zistiť, či vo vzostupne utriedenom poli \(a_0\) až \(a_k\), sú dve čísla \(a_i\), \(a_j\) také že \(a_i + a_j = x\).

Pokiaľ \(a_0 + a_k > x\), tak pre všetky \(i\geq 0\) platí, že \(a_i + a_k > x\) a teda \(a_k\) nemôže byť \(a_j\). Preto môžeme \(a_k\) zahodiť. Analogicky, keď \(a_0 + a_k < x\), môžeme zahodiť \(a_0\). Po zahodení dostaneme o jedna kratšie pole, na ktorom riešime rovnakú úlohu.

Keďže zahadzujeme len tie prvky, ktoré nemôžu byť hľadanými \(a_i\), \(a_j\), tak buď tieto prvky časom nájdeme, alebo zistíme, že sme všetko zahodili a prvky sa v poli nenachádzajú. V každom kroku, v ktorom sme nenašli odpoveď, sme postupnosť skrátili, takže časová zložitosť je \(O(k)\), kde \(k\) je počiatočná dĺžka postupnosti.

Takže celý algoritmus bude fungovať takto: pole dĺžok rúrok si utriedime, postupne si každú rúrku (jej dĺžku označíme \(r_i\)) zvolíme za “najdlhšiu rúrku trojuholníka”. Pokiaľ \(2r_i \geq d\), rovno vieme, že to, čo by sme poskladali, nebude trojuholník. V opačnom prípade sa pokúsime ku nej nájsť (v časti poľa, v ktorej sú len kratšie rúrky) dve také rúrky, ktoré majú súčet dĺžok rovný \(d - r_i\). Ak sa podarilo, vypíšeme DA SA, ak sa to nepodarí pre žiadnu “najdlhšiu rúrku trojuholníka”, vypíšeme NEDA SA. Časová zložitosť algoritmu pre jednu testovaciu sadu je \(O(n^2)\). Jeho pamäťová zložitosť je \(O(n)\).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int t, d, n, najdlhsia, a, b;
    long long sucet;
    bool bicykel;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        cin >> n >> d;
        vector<int> r(n);
        for (int j = 0; j < n; ++j) cin >> r[j];
        bicykel = false;
        sort(r.begin(), r.end());
        najdlhsia = 2;
        // Skusame vsetky rurky, ci by mohli byt najdlhsou rurkou trojuholnika
        while (najdlhsia < n && r[najdlhsia]*2 < d && !bicykel) {
            a = 0;
            b = najdlhsia - 1;
            // Hladame dve zvysne rurky pasujuce k vybranej najdlhsej
            while (a < b && !bicykel) {
                sucet = (long long)r[a] + (long long)r[b] + r[najdlhsia];
                if (sucet > d) b--;
                else if (sucet < d) a++;
                else bicykel = true;
            }
            najdlhsia++;
        }
        if (bicykel) cout << "DA SA" << endl;
        else cout << "NEDA SA" << endl;
    }
}