3. Lietajúce Taniere (vzorové riešenie) - Korešpondenčný seminár z programovania

Zadanie

Pozemšťanské Národné Múzeum v Sekulách vystavuje skutočný skvost: Najvzácnejšiu hlásku galaxie¹. Táto hláska je lokálny endemit – nevyskytuje sa vo fonológií jazyka žiadnej inej planéty, a preto má obrovskú hodnotu. A práve preto bola v piatok cez obedovú prestávku ukradnutá rafinovaným páchateľom. Nie je ním nik iný, ako interstelárny kriminálnik Okáň Hruškový, prezývaný “Bzučiak”. Samotná krádež bola pre neho hračkou, skutočná skúška jeho schopností nastáva až teraz: s ukradnutou hláskou sa musí dostať na najbližšiu matriku, kde si zmení meno na Okäň, čím zmätie agentov zákona, zahladí všetky stopy po svojej kriminálnej histórií a šťastný odíde do dôchodku. Samozrejme, poletí lietajúcim tanierom².

Má to však háčik: Medzi Pozemšťanským Národným Múzeom v Sekulách a Sekulským Matričným Úradom nejde žiaden priamy let, preto musí Bzučiak prestúpiť na Hlavnej Tanierovej Stanici Sagittarius A.

Okrem toho je problémom, že galaktická polícia má agentov zákona všade. Normálne síce pre Bzučiaka žiaden problém nepredstavujú³, pokiaľ ale poletí rovnakým letom ako jeden z nich, môže sa s novým menom rozlúčiť.

Ako nový zamestnanec IT oddelenia galaktickej polície ste dostali časy odletov všetkých liniek, spolu s pridelenými financiami, za ktoré môžete nakúpiť niekoľkým policajtom letenky, aby ste Bzučiakovi znemožnili využitie týchto letov. Vašou úlohou je Bzučiakovi cestu čo najviac znepríjemniť, pokiaľ možno úplne znemožniť.

Úloha

Máte dané časy odchodov všetkých \(n\) letov z Národného Múzea do Tanierovej Stanice, ako aj ich dĺžku \(d_a\), ktorá je, samozrejme, pre všetky rovnaká. Rovnako máte dané aj odchody všetkých \(n\) letov z Tanierovej Stanice na Matričný Úrad, a ich dĺžku \(d_b\). Máte peniaze na zablokovanie \(k\) letov – určte, v akom najneskoršom čase môžeme Bzučiaka prinútiť dostať sa na Matričný Úrad, respektíve či vieme Bzučiakovi v jeho dosiahnutí úplne zabrániť.

Bzučiak môže prestúpiť medzi dvoma letmi, pokiaľ čas príchodu prvého nie je vyšší ako čas odchodu druhého, pričom dĺžka letu je definovaná ako rozdiel v časoch jeho príchodu a odchodu.

Formát vstupu

Na prvom riadku vstupu sa nachádzajú 4 celé čísla \(n, d_a, d_b, k\) - počet letov na každej linke, dĺžky letov prvej a druhej linky, a počet lístkov, ktorý si môžeme dovoliť kúpiť, pričom vždy platí \(1 \leq d_a,d_b\) a \(1 \leq k \leq 2n\).

Nasledujú dva riadky. Na prvom z nich je \(n\) rôznych celých čísel \(a_0\) až \(a_{n-1}\), ktoré označujú časy odchodov letov prvej linky. Na druhom z nich je \(n\) rôznych celých čísel \(b_0\) až \(b_{n-1}\), ktoré označujú časy odchodov letov druhej linky. Platí, že oba riadky sú zoradené vo vzostupnom poradí, a okrem toho všetky časy odletov \(x\) spadajú do nasledovného rozmedzia: \(1 \leq x \leq 10^{9}\).

Formát výstupu

Na jediný riadok výstupu vypíšte jediné číslo – najneskorší čas, v akom môžeme Bzučiaka donútiť doraziť do cieľovej zastávky. Pokiaľ je možné Bzučiakovi zabrániť v dosiahnutí cieľa úplne, vypíšte číslo \(-1\). Nezabudnite na konci vypísať symbol konca riadku.

Hodnotenie

Sú 4 sady vstupov:

V prvej sade platí, že \(1 \leq n \leq 100\), \(d_a = d_b = 1\) a obe linky majú rovnaké časy odletov, teda \(a_i = b_i\) pre všetky \(0 \leq i \leq n-1\).
V druhej sade platí, že \(1 \leq n \leq 10\,000\).
V tretej sade platí, že \(1 \leq n \leq 100\,000\).
V štvrtej sade platí, že \(1 \leq n \leq 1\,000\,000\).

Príklad

Input:

4 3 5 3
1 2 3 6
6 7 8 9

Output:

Zablokujeme napríklad prvé tri lety z Národného Múzea. Bzučiak nebude mať inú možnosť, ako využiť ten posledný, s odchodom v čase 6. V Tanierovej Stanici bude v čase 9, stihne rýchlo nastúpiť na posledný let na Matričný Úrad, ktorý k nemu dorazí v čase 14. Alternatívne sme mohli zablokovať prvé tri lety druhej linky a dosiahnuť rovnaký výsledok.

Input:

6 2 1 4
1 3 5 7 9 11
3 4 5 6 10 13

Output:

-1

V tomto prípade vieme Bzučiaka od Matričného Úradu úplne odrezať, napríklad zablokovaním prvých dvoch letov z Národného Múzea a posledných dvoch letov z Tanierovej Stanice. Bzučiak odletí najskorším letom s odchodom v čase 5, v Tanierovej Stanici bude v čase 7, a nestíha už žiaden nezablokovaný let ďalej.

Lokálne sa zaznačuje písenkom ä.↩︎
Nemýliť si s morským tanierom.↩︎
Dôvod, prečo Bzučiaka polícia nemôže chytiť mimo lietajúceho taniera, je úplne očividný a netreba ho vysvetľovať.↩︎

Zamyslime sa, ktorými letmi sa Bzučiakovi oplatí letieť. Z Národného Múzea do Hlavnej Stanice sa mu určite oplatí letieť prvým neblokovaným letom. Teda pre nás nemá zmysel blokovať tieto lety, pokiaľ je nejaký skorší aj tak nezablokovaný. Takže jednoducho budeme blokovať niekoľko prvých letov prvej linky.

V prípade druhej linky to je podobne: Bzučiak určite nepoletí z Hlavnej Stanice na Matričný Úrad žiadnym letom po prvom neblokovanom. Zároveň ale, na rozdiel od prvej situácie, platí, že určite nepoletí takým letom, ktorý odlieta pred tým, ako priletí Bzučiakov prvý let (nie preto, že by sa to neoplatilo, ale preto, že je to jednoducho nemožné).

Teda všetky možné blokovania letov, aké sa nám teoreticky môžu oplatiť (majú potenciál viesť ku hľadanému optimálnemu výsledku), vyzerajú nasledovne: Zablokujeme \(x\) prvých letov prvej linky, pričom \(0 \leq x \leq k\) . Bzučiak poletí prvým neblokovaným letom, teda do Hlavnej Stanice doletí v čase \(a_x + d_a\), respektíve ak \(n \leq x\), tak nepoletí vôbec, keďže sme zablokovali všetky lety na prvej linke. Ostáva nám \(k-x\) letov, ktoré môžeme blokovať. Nemá zmysel blokovať lety druhej linky, ktoré odlietajú pred Bzučiakovym časom príchodu do hlavnej stanice. Zablokujeme teda prvých \(k-x\) letov, ktoré z Hlavnej Stanice odlietajú v Bzučiakovom čase príchodu alebo neskôr. Opäť môže nastať možnosť, že \(k-x\) je dosť na zablokovanie všetkých letov až po posledný. Ak nenastane, Bzučiak poletí letom číslo \(y\), a do cieľa sa dostane v čase \(b_y + d_b\).

Pre všetky možné hodnoty \(x\) musíme nájsť najvyššie dosiahnuteľné \(b_y + d_b\), prípadne či pre nejaké \(x\) vieme dosiahnuť kompletné zablokovanie.

Pomalé riešenie

Najzjavnejšie riešenie, ktoré nám môže napadnúť je postupne vyskúšať všetky možné počty zablokovaných letov prvej linky \(x\), a pre každý nájsť riešenie. Jednoducho pre každý čas príchodu \(a_x + d_a\) nájdeme v časoch odchodu druhej linky prvý let, ktorý neodlieta pred ním, posunieme sa o \(k-x\) letov neskôr na nejaký let \(b_y\), a pamätáme si výsledok \(b_y + d_b\). Na konci vypíšeme z týchto výsledkov ten najvyšší, respektíve ak niekedy dosiahneme kompletné zablokovanie, tak môžeme hľadanie ihneď prerušiť a vypísať \(-1\).

Časová zložitosť tohto riešenia môže byť \(O(n^2)\), pokiaľ prvý let druhej linky, ktorý Bzučiak stíha, hľadáme lineárne, teda postupne od začiatku. Môžeme si trošku prilepšiť použitím binárneho vyhľadávania, čím zlepšíme zložitosť na \(O(n \cdot log(n))\). V oboch prípadoch pre každú možnú hodnotu \(x\), ktorých určite nie je viac ako \(2n\), hľadáme bod v usporiadanom poli, teda zložitosť je lineárna, vynásobená zložitosťou našeho hľadania. Posunúť sa po nájdení tohto letu o \(k-x\) ďalej nám zaberie konštantný čas, keďže výstupom z hľadania je index nájdeného prvku, a k nemu jednoducho pripočítame \(k-x\). Pamäťová zložitosť programu bude každopádne \(O(n)\), keďže nám stačí pamätať si vstup a konštantné množstvo celočíselných premenných.

Vzorové riešenie

Hľadanie, ktoré sme v pomalších riešeniach vylepšovali, môžeme zlepšiť ešte viac. Uvedomme si, že keď \(x\) sa zvýši o \(1\), tak čas príletu do Hlavnej Stanice sa určite nezníži. Teda nemusíme zakaždým prehľadávať celé pole odletov, ale stačí nám pokračovať tam, kde sme prestali (pretože vieme, že letíme neskorším letom, ako predtým, teda lety, ktoré sme nestihli predtým, určite nestihneme ani teraz). Postačí nám teda hľadať lineárne, no pamätať si vždy bod, kde sme naposledy prestali, a nabudúce pokračovať v hľadaní odtiaľ.

Toto nové hľadanie prejde najviac všetkými \(n\) prvkami počas celého behu programu. Programu teda hľadanie celkovo zaberie najviac \(n\) času, teda časová zložitosť bude \(O(n+n) = O(n)\). Pamäťová zložitosť je rovnaká, ako v pomalších riešeniach - \(O(n)\).

#include <iostream>
using namespace std;

int main() 
{
	int n, da, db, k;
	std::cin >> n >> da >> db >> k;
	
	int atob [n] = {};
	for(int i=0; i<n; i++)
	{
	    std::cin >> atob[i];
	}
	
	int btoc [n] = {};
	for(int i=0; i<n; i++)
	{
	    std::cin >> btoc[i];
	}
	
	
	//najneskorsi let do ciela, ktorym sa nám Bzuciaka podarilo prinutit ist
	int best = 0;
	//prvy let do ciela, ktoreho odlet Bzuciak teoreticky stiha
	int b_dep_index = 0;
	
	//vyskusame zablokovat vsetky mozne pocty letov prvej linky
	for(int offset=0; offset<=k; offset++)
	{
		//pokial sa nam podari zablokovat vsetky, Bzuciak sa do ciela nevie dostat a hladat dalej nie je potrebne
	    if(offset >= n)
	    {
	        std::cout << -1 << std::endl;
	        return 0;
	    }
	    
		//cas, v ktorom Bzuciak dorazi do prestupnej stanice
	    int b_arrival = atob[offset] + da;
	    
		//najdeme prvy let dalej, ktory Bzuciak teoreticky stiha
	    while(btoc[b_dep_index] < b_arrival)
	    {
	        b_dep_index ++;
	    }
		//Bzuciak neodide tymto letom, ale az o tolko letov neskor, kolko ich este mozeme zablokovat
	    int b_departure = b_dep_index + k - offset;
	    
		//pokial zablokujeme vsetky zvysne lety, do ciela sa nedostane
	    if(b_departure >= n)
	    {
	        std::cout << -1 << std::endl;
	        return 0;
	    }
	    
		//pokial sme dosiahli zatial najlepsi vysledok, zapamatame si ho
	    if((btoc[b_departure] + db) > best)
	    {
	        best = (btoc[b_departure] + db); 
	    }
	    
	}
	//vypiseme najneskorsi prichod, aky sme dosiahli
	std::cout << best << std::endl;
	return 0;
}

n,da,db,k = [int(i) for i in input().split()]
a = input().split()
b = input().split()
for i in range(n):
    a[i] = int(a[i])
    b[i] = int(b[i])

#index letu prvej linky, ktorym Bzuciak poleti (rovny poctu zablokovanych letov prvej linky)
prvy = 0
#index letu druhej linky, ktory Bzuciak teoreticky stiha (neratame s blokovanim letov druhej linky)
druhy = 0
#odpoved - index letu druhej linky, ktorym Bzuciak pri vhodnom zablokovani poleti najneskor (rovne -1, pokial sa da Bzuciaka zablokovat uplne)
o = -1

#vyskusame vsetky mozne pocty zablokovanych letov prvej linky
while prvy <= k:
    #pokial na niektorej linke zablokujeme dost letov, aby Bzuciak musel ist indexom letu, ktory uz neexistuje, tak sme ho od ciela odrezali a dalej hladat nemusime
    if prvy >= n:
        o = -1
        break
    if druhy >= n:
        o = -1
        break
    
    #pokial Bzuciak nestiha let ulozeny v premennej druhy, tak ho posunieme, kym ho nebude stihat
    if b[druhy] < a[prvy]+da:
        druhy += 1
        continue
    
    #pocet letov, ktore este mozeme zablokovat na druhej linke
    ostava = k-prvy
    #index letu druhej linky, ktorym Bzuciak naozaj poleti
    x = druhy+ostava
    #pokial uz nestiha ziaden let, je od ciela odrezany
    if x >= n:
        o = -1
        break
    #pokial sme dosiahli zatial najlepsi vysledok, zapamatame si ho
    if x > o:
        o = x
    #pokial sme sa dostali az sem, ideme vyskusat dalsi pocet zablokovani na prvej linke
    prvy += 1
    
#vypiseme vysledok
if o == -1:
    print(-1)
else:
    print(b[o]+db)

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.

3. Lietajúce Taniere vzorové riešenie