FMI No Stress 7 - Soluţii

Re:Adunare

Trebuia implementată adunarea pentru numele naturale date în formatul din teoria mulţimilor. Condiţiile iniţiale garantau că rezultatul se încadrează în limitele de memorie. Cum ordinea relativă a elementelor într-o mulţime determină o multitudine de variante de a o reprezenta, trebuia aleasă soluţia care genera şirul minim lexicografică (prioritizam afişarea elementelor mai mari înaintea celor mai mici).

Dicsi

Observăm că numerele de forma [1, 2, 4, 8, ..., 2k] necesită folosirea a k + 1 culori distincte. Putem obţine o astfel de colorare colorând numărul i cu suma exponenţilor din descompunerea în factori primi a acestuia. Echivalent, putem folosi următoarea "euristică": col[i] = 1 + max{col[d] | d divide pe i} (care dă, în final, acelaşi răspuns). Calcularea se poate face în complexitate O(n sqrt(n)) cu divizori sau O(n log(n)) cu ciur.

Blaturi

Problema se rezolvă utilizând metoda greedy:

Fie SumSt[K] = suma timpilor pentru a prepara blaturile de la 1 la K si SumDr[K] = suma timpilor pentru a prepara blaturile de la K la N.
Este evident că dacă studentul 1 face K blaturi din cele N, se va plăti SumSt[K] * Timp1 şi SumDr[K+1] * Timp2. La valoarea pe care o obţinem se mai adaugă şi eventualele costuri suplimentare, costuri obţinute în funcţie de numărul de blaturi făcute de fiecare student. Deoarece dorim să minimizăm acest cost suplimentar total, deducem că trebuie să-i alternăm cât mai mult posibil pe cei doi.

De exemplu, dacă avem 11 blaturi şi studentul 1 face 7 blaturi (deci studentul 2 face 4 blaturi), trebuie să avem următoarea distribuţie: 121212121 11. Astfel vom plăti de două ori costul suplimentar cerut de studentul 1.

Pang

Problema cerea permutarea unui şir de noduri A1...Ak astfel încât să existe un drum A1 - A2 ... Ak în graful orientat aciclic dat în input. O primă observaţie este că, dacă există, soluţia este unică:

Să presupunem că există o soluţie A1...Ak (în această ordine). Să interschimbăm acum ordinea relativă Ai, Aj,cu i < j, aleşi arbitrar. Din condiţia de DAG, rezultă că nu există drum de la Aj la Ai, deci nu poate exista o altă soluţie cu ordinea interschimbată. În concluzie, orice soluţie va trebui să păstreze aceeaşi ordine relativă a nodurilor, de unde rezultă unicitatea. Existenţa se poate verifica cu următoarea dinamică: dp[v] = vip[v] + max{dp[w] | (v, w) e muchie în graf}, unde vip[v] = 1 ddacă există o relicvă în v. Acum, există soluţie ddacă există un nod v* cu dp[v*] = k. Ordinea (unică) este dictată de sortarea topologică a nodurilor grafului.

Snowball

Problema cere aflarea lungimii celei mai lungi subsecvenţe continue din A care nu îl conţine pe B ca subşir şi numărarea tuturor subsecvenţelor cu această proprietate. Să presupunem că fixăm capătul stânga i. Pentru a afla cea mai lungă subsecvenţă, vom căuta iterativ primul număr din B, apoi, în continuare, al doilea, ş.a.m.d. Când am găsit ultimul număr din B sau am ajuns la sfârşitul şirului A, ne oprim. Soluţia aceasta are complexitate O(n2).

Pentru a o optimiza, putem parcurge şirul de la dreapta la stânga şi menţine direct legăturile la fiecare număr din şir (putem face asta, deoarece şirul B conţine numere distincte). Astfel putem găsi poziţia primului număr c din dreapta lui i. Vom ţine, mai apoi, end[x] = "poziţia de terminare pentru sufixul din dreapta lui i care începe cu numărul x şi este cel mai din stânga. Vom menţine o variabilă dr globală, care va reţine cea mai din stânga poziţie din dreapta lui i care îl conţine pe B ca subşir (iniţial este egală cu lungimea şirului A). Avem 3 cazuri:

  • numărul de pe poziţia i este ultimul din B : end[A[i]] = i
  • numărul de pe poziţia i apare în B la poziţia poz, dar nu este ultimul : end[A[i]] = end[B[poz + 1]]
  • numărul de pe poziţia i este primul în B : dr = end[A[i]]

Bineînţeles, iniţial end va fi umplut cu valoarea egală cu lungimea şirului A.
Complexitatea acestei soluţii este liniară.

Dlboss

O primă observaţie este că, pentru ca Dl. Boss să poată vizita fetele în ordinea strict crescătoare a frumuseţii, este suficient şi necesar ca frumuseţile acestora să fie diferite două câte două.

Vom sorta fetele descrescător după frumuseţe şi de vom procesa în această ordine. La fiecare pas, vom ţine mulţimea de fete aleasă, la care îi vom adăuga o noua fată. Singura problemă care poate apărea este atunci când noua mulţime de fete depăşeşte timpul maxim alocat. În acest caz, vom renunţa intuitiv la fata cea mai depărtată, după care vom continua procesul. Simularea se poate face cu un max heap (a.k.a. std::priority_queue), în timp O(n log n), bineînţeles, cu atenţie la detaliile de implementare.

Hapsan

Problema cere găsirea unui subşir crescător de sumă maximă, cu respectarea a M constrângeri de forma putem alege un singur element din intervalul [Ai...Bi].
Fie dinamica intuitivă dp[i] = "cel mai bun câştig, considerând că ultimul sushi a fost cel cu indicele de ordine i".
Pentru a rezolva problema, o spargem în două subprobleme:

  • rezolvarea restricţiilor pe interval : Se poate rezolva preprocesând left[i] = "cel mai din dreapta sushi pe care îl pot lua ca penultim, dacă ultimul sushi luat a fost i". Se demonstrează că left[i] = min{Aj | Aj <= i <= Bj} - 1. Acest lucru se poate calcula în mai multe moduri : cu deque / baleiere / arbore de intervale. Există totuşi o soluţie care rezolvă problema în timp liniar, folosindu-se doar de un array ca structură auxiliară, pe care o lăsăm ca temă de gândire.
  • rezolvarea restricţiilor de monotonie : Se poate rezolva în două moduri, folosind un AIB / arbore de intervale. Unul este sortând în prealabil sushi-urile crescător şi rezolvându-le în ordinea sortată, rezolvarea fiind modelată ca şi query de maxim pe prefix de poziţii. Cea de a doua soluţie consideră rezolvarea problemei într-o nouă parcurgere stânga - dreapta a sushi-urilor şi populând dp[i] cu răspunsul unui query de maxim pe prefix de valori la momentul left[i]. Acest concept mai poartă numele argotic de "dinamică inainte", fiind util şi uşurând implementările în multe cazuri de probleme de programare dinamică.

Notă: Pentru a rezolva problema de 50 de puncte, este suficientă strategia greedy de a porni de la dreapta la stânga şi de a lua mereu sushi-ul curent, dacă acesta nu contrazice restricţiile din enunţ.

Shield

Soluţia se bazează pe determinarea la fiecare pas a intervalului în care se poate afla scutul. Să-l definim ca fiind left[i]...right[i]. Algoritmul va fi compus din doi paşi:

  • Pasul 1 (forward pass) : Pornim cu left[1] = right[1] = 1. Pentru următorii paşi, vom avea că left[i], right[i] = left[i - 1] - 1, right[i - 1] + 1, pe care îl vom intersecta cu intervalele X - L + 1, X, pentru fiecare monstru aflat la înălţimea i şi coordonata orizontală X. Există soluţie ddacă nu am obţinut intervale vide pe parcurs.
  • Pasul 2 (back pass) : Pornim de la înălţimea maximă spre 1 şi, intersectăm în ordine intervalul left[i], right[i] obţinut la pasul 1 cu intervalul left[i + 1] - 1, right[i + 1] + 1 obţinut la pasul 2.

Pentru a construi o soluţie validă, este suficient acum să pornim de jos în sus şi să afişăm orice direcţie, atâta timp cât aceasta ne va trimite pe o coordonată validă la pasul următor (verificând cu valorile procesate mai sus).

Bonus: Cum numărăm soluţiile distincte?

Cutit

O primă observaţie este că un lanţ de K + 1 noduri este o soluţie validă. Această soluţie ar trebui să obţină 15 puncte.

O bună intuiţie în rezolvarea a astfel de probleme este alegerea unei structuri de bază şi combinarea acesteia iterativ până la soluţia cea bună. În acest caz, putem observa că un graf complet de x noduri va genera 2x-1-1 tăieturi valide (demonstraţia este lăsată ca exerciţiu). Perfect, avem modelul de bază. Dar cum putem combina două modele? Pentru aceasta, este suficient să ne uităm la observaţia de mai sus, cu alte cuvinte să formăm un lanţ de clici. Această soluţie ar trebui să obţină, în funcţie de implementare, circa 80 de puncte.

Dar cum putem îmbunătăţi soluţia? La o mică analiză, putem constata că diferenţa între numărul de noduri al grafului la soluţia precedentă depăşeşte cu puţin limita de 80 de noduri. Soluţia de 100 de puncte foloseşte tot ideea de conectare a clicilor, însă se foloseşte mereu nodul 1 ca şi nod comun pentru toate clicile (în esenţă, dacă avem o construcţie cu a tăieturi şi una cu b tăieturi, putem forma una cu a + b tăieturi prin simpla punere în comun a unuia dintre noduri). De ce?

Bonus: Cum aţi implementa un checker pentru o asemenea problemă?