Revizia anterioară Revizia următoare
Re:Adunare
Destul de straightforward problema, 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.
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 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.
Snowball
Dlboss
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.
