preONI 2005 runda #3 - solutii

(Creat de Mircea Pasoi •domino la data de 2005-03-20 categoria Competitii, autor(i) Echipa devNet)

Articolul contine ideile de rezolvare ale problemelor propuse la ultima runda a concursului preONI ce s-a desfasurat pe data de 20 martie 2005, cat si comentarii legate de concurs. Si de aceasta data numarul de participanti a fost impresionat, cu siguranta datorita faptului ca in numai 5 zile incepe ONI!

Setul de probleme a fost mai greu de data aceasta, special pentru a testa concurentii cu probleme cat mai asemanatoare cu stilul ONI. Speram ca fiecare participant a invatat cate ceva in urma acestui concurs si asteptam pareri si sugestii pentru viitor pe forum.

Clasele 9-10

Clasament

Pozitie	Nume	Scor
1	Mugurel-Ionut Andreica •mugurelionut	190
2	Bogdan-Cristian Tataroiu •bogdan2412	170
2	Ionita Andrei Lucian •TheCreeep	170
4	Ionescu Bogdan-Gabriel •ionescu_bogdan	160
5	Simion Alexandru •sims	150
5	Filip Cristian Buruiana •filipb	150
7	Mihai Moraru •Ignition	140

Barman

(solutie corecta oferita de Dan-Constantin Spatarel •spatarel, 20 noiembrie 2005)

Metoda folosita este una brute-force si se bazeaza pe cateva observatii. Pentru a determina solutia optima sortam sirul valorilor bauturilor si ii generam toate permutarile circulare in vectorul obt. De aici, problema noastra ramane transformarea de cost minim a vectorului initial a in vectorul obt folosind operatiile permise. Dintre toate permutarile circulare, evident o vom alege pe cea care cere un cost minim al operatiilor. In primul rand se observa ca nu are nici un rost sa deranjam camerele care au bautura ceruta (a_i = obt_i), deci pe Paftenie nu il vor preocupa acestea. In al doilea rand este de remarcat ca ar fi inutil ca Paftenie sa deplaseze mai mult de un pahar intre doua camere deoarece am considera un caz redundant. De ce? Ar fi libere numai camerele c₁ si c₂, din care provin cele doua pahare de pe tava. Cu doua pahare pe tava ar putea sa mearga intr-o camera c₃ diferita de c₁ si c₂, dar ar fi inutil, caci nici pe tava nici in camera nu mai poate depozita vreun pahar.

Astfel, problema se reduce la a gasi, pentru fiecare bautura care nu se afla pe locul ei, o pozitie optima, pe care daca o asezam, vom obtine un cost global minim. Pentru simplitate, in continuare voi numi "cuplaj" mutarea unei bauturi pe o alta masa. Se poate oberva ca problema se poate imparti in mai multe sub-probleme independente: fiecare sub-problema va calcula cuplajul optim pentru toate bauturile de aceeasi valoare. Problemele sunt independente, deoarece pentru a pastra solutia optima globala, trebuie sa cuplam o bautura cu o masa pe care trebuie plasata acelasi tip de bautura.

O metoda ar fi greedy: pentru fiecare bautura care nu e la locul ei, cautam cea mai apropiata masa pe care se poate pune - insa aceasta metoda este gresita.

O alta metoda este cuplajul intr-un graf bipatit. Desi aceasta rezolvare este corecta, nu se incadreaza in timpul de executie. Deoarece trebuie efectuate N cuplaje cu cate 2*N noduri fiecare, vom obtine o complexitate de O(N⁵), supraestimata. Este posibil, totusi, ca in urma unor optimizari puternice, si aceasta metoda sa obtina punctaj mare.

Totusi, mai exista si o alta metoda mult mai simpla si mai rapida, care se bazeaza pe cateva observatii suplimentare: datorita sortarii pe care am efecutat-o la inceputul algoritmului si a permutarilor circulare, mesele pe care trebuie plasata aceeasi bautura, sunt plasate fie secvential, fie in doua secvente, de la 1 la k si de la l la N. De asemenea, deoarece am eliminat cazurile in care a_i = obt_i, cele doua cazuri, fara a pirde dingeneralitate, se reduc la unul singur: in intervalul 1 - k exista numai bauturi care trebuie cuplate; in intervalul k+1 - l exista numai mese care trebuie cuplate; in intervalul l+1 - N exista numai bauturi care trebuie cuplate. (Al doilea caz este simetric, si deoarece mesele pot fi privite ca bauturi, si invers, putem reduce al doilea caz la primmul.)

Problema se rezolva partitionand mulmimea meselor in doua secvente: mesele din prima secventa se vor cupla cu bauturile din intervalul 1 - k, iar mesele din a doua secventa cu bauturile din intervalul l+1 - N. Se poate observa ca oricum s-ar realiza cele doua cuplaje, costul golbal va fi acelasi. In plus, orice alt cuplaj global care nu tine cont de aceasta impartire va obtine un const global mai mare. Astfel, se garanteaza ca aceasta metoda va calcula corect costul minim global.

Algoritmul care impleneteaza acest cuplaj este foarte simplu: pentru fiecare bautura care nu se alfa la locul ei (a_i = obt_i), se cauta prima masa necuplata pe care se poate plasa bautura.

Cifre

Pentru a afla probabilitatea ceruta trebuie sa aflat cate numere exista in intervalul [A..B] cu cel putin K cifre de C. Pentru asta vom construi o functia f(x) care va returna cate numere sunt in intervalul [0..x-1] care au cel putin K cifre de C. Astfel rezultatul va fi f(B+1)-f(A). Functia f(x) va rula in complexitate O(lg x) parcurgand numarul x cifra cu cifra. Ca sa realizam acest lucru avem nevoie de urmatoarele informatii:
cnt(i, j) = cate numere intre 0 si 10ⁱ-1 contin j cifre de C (vom considera ca numerele pot avea 0-uri in fata, de exemplu: 0003 are 3 cifre de 0)
Acest numar se poate calcula fie printr-o formula matematica folosind combinari sau cu o relatia de recurenta (independenta de variabila C):

• cnt(i, j) = 9 * cnt(i-1, j) + cnt(i-1, j-1)

De asemenea mai avem nevoie de urmatoarele informatii:
cnt0(i, j) = cate numere care nu au 0-uri in fata intre 0 si 10ⁱ-1 contin j cifre de C. Relatia de recurenta va fi in functie de C:

• daca C=0 atunci cnt0(i, j) = cnt0(i-1, j) + 9 * cnt(i-1, j)
• altfel cnt0(i, j) = cnt0(i-1, j) + 8 * cnt(i-1, j) + cnt(i-1, j-1)

Cele doua matrici au marimi lgB*K deci construirea lor va avea complexitate O(lg B*K). Odata disponibile aceste informatii se poate realiza destul de usor functia f(x). Nu voi prezenta aici toate detaliile deoarecere apar mai multe cazuri (in special cand C = 0), lasand ca exercitiu pentru cititor.

O alta rezolvare posibila ar fi calcularea functiei f(x) in O(2^lg10(x)*lg10(x)) astfel: pe fiecare pozitie intre 0 si lg10(x) avem doua variante, fie punem cifra C, fie alta cifra. Pentru fiecare astfel de configuratie cu cel putin K cifre de C se poate determina dintr-o parcurgere cate numere exista < x care au cifre de C in pozitiile respective.

Farfurii

Problema cere construirea unei permutari de lungime N cu K inversiuni, minim lexicografica. O prima rezolvare de complexitate O(N²) ar fi construirea permutarii element cu element. Cu cat un element este mai mare pe o anumita pozitie cu atat formeaza mai multe inversiuni, astfel ca incercam sa punem pe fiecare pozitie un element cat mai mic astfel: pe pozitia i, daca K ≤ (N-i)*(N-i-1)/2 putem pune cel mai mic element disponibil (pentru ca in bucata de N-i ramasa putem construi cel putin /2 inversiuni), altfel punem al K-(N-i)(N-i-1)/2 element disponibil. Aceasta modalitate de constructie garanteaza ca permutarea este minim lexicografic. O implementare directa, cum am zis, are complexitate O(N^2) si ia 40-60p. Pentru 100p se poate folosi un arbore de intervale (ca la problema concurs de la .campion 2004, runda 9) reducand complexitate la O(N*lg N). O asemenea solutie, desi lua 100p, necesita cunostiinte de structuri de date avansate care depasesc nivelul de cunostiinte general al unui concurent pentru clasele 9-10. O rezolvare O(N) mult mai simpla se bazeaza pe urmatoarea observatie:
O permutare de lungime i are cel mult i*(i-1)/2 inversiuni cand numerele sunt in ordine descrescatoare.
Astfel, daca K e de forma M*(M-1)/2 permutarea minim lexicografica cu K inversiuni va fi:

1, 2, 3, ... N-M, N, N-1, N-2, ... N-M+1

Cele K inversiuni apar in ultimele M elemente. Daca in aceasta permutare mutam un element N-x imediat inaintea lui N numarul de inversiuni scade cu x. Astfel, daca K>M*(M-1)/2 construim permutarea

1, 2, 3, ... N-M-1, N, N-1, N-2, ... N-M

(care are (M+1)*M/2 inversiuni) si mutam elementul N-((M+1)*M/2-K) imediat inaintea lui N, astfel scadem numarul de inversiuni la K. Este evident ca permutarea astfel construita este minim lexicografica. Algoritmul descris are complexitate O(N).

Clasele 11-12

Clasament

Pozitie	Nume	Scor
1	Mugurel-Ionut Andreica •mugurelionut	210
2	Teodorescu Andrei-Marius •andreitheo87	200
3	Adrian Diaconu •DITzoneC	170
4	Sorin Stancu-Mara •MaxDamage	150
5	Tiberiu-Lucian Florea •greco	120
6	Dima Alex •cavendish	110

Setul de probleme, mai greu de data aceasta, se pare ca a pus in dificultate majoritatea concurentilor. Desi problemele Critice si Poligon nu erau foarte dificile in faza de concepere a algoritmului se pare ca implementarea a fost cea care i-a speriat pe multi dintre participanti.

Critice

Problema este o aplicatie a algoritmului de aflare a fluxului maxim dintr-o retea. Se construieste o retea, nodurile fiind adaposturile iar capacitatile muchiilor fiind egale cu rezistentele tunelurilor. Prima solutie, care trece ~ 50% din teste, este urmatoarea:

1. Se calculeaza fluxul maxim in reteau construita
2. Pentru fiecare muchie (separat) se creste capacitatea ei cu o unitate si se mai ruleaza inca o data algoritmul de flux maximi. Daca fluxul maxim a crescut atunci muchia este critica.

Se observa ca acest algoritm are o complexitate considerabila si trebuie sa ne gandim la ceva mai bun. Primul lucru inteligent pe care il putem observa este ca muchiile critice sunt muchiile care, dupa ce am rulat odata algoritmul de flux maxim, sunt saturate (am folosit toata capacitatea ei intr-o directie sau cealalta). Totusi nu toate muchiile saturate sunt si critice. Pentru a fi mai exacti, muchiile critice sunt acele muchii saturate care au propietatea ca de la sursa retelei (nodul 1) este drum in graful rezidual (adica graful care ne ramane daca eliminam muchiile saturate) la unul din capetele ei si respectiv de la destinatie (nodul N) la celalalt capat. Asadar se contureaza algoritmul:

1. Se ruleaza odata algoritmul de flux maxim
2. Cu ajutorul a doua parcurgeri a grafului rezidual stabilim pentru fiecare muchie critica daca propietatea este adevarata

Complexitatea (teoretica) va fi O(M^2*N + M) dar este supraestimata algoritmul de flux ruland mult mai rapid.

Ferma

La prima vedere, problema pare abordabila cu programare dinamica. O simpla rezolvare care nu tine cont de faptul ca sirul este circular este urmatoarea: A(i, j) = productivitatea maxima pentru a face i strangeri din primele j sectoare; evident raspunsul va fi A(K, N). Relatia de recurenta:

A(i, j) = max (A(i, j-1), A(i-1, k) + suma P(k),P(k+1)..P(j)) pentru fiecare k<j, iar P reprezinta vectorul de productivitati.

O astfel de implementare are complexitate O(N^2*K) si nu se va incadra in timp. Fie S(i) = P(1)+P(2)+...P(i), atunci putem rescrie relatia de recurenta astfel:

A(i, j) = max(A(i, j-1), A(i-1, k) + S(j) - S(k)), pentru fiecare k<j

Al doilea termen este de forma A(i-1, k) - S(k) (termen independent de j) + S(j). Astfel din linia i-1 a matricii de dinamica pentru fiecare j ne trebuie valoarea maxima A(i-1, k)-S(k) cu k<j. O prima idee ar fi ca pe masura ce construim linia i sa inseram elementele din linia i-1 intr-un max-heap astfel reducand complexitatea la O(N*lgN*K).

Cei care au rezolvat probleme precum "secventa" de pe info-arena, "trans" de la barajul de la ONI 2004 sau "divide" de la USACO Ianuarie 2005 vor realiza imediat ca putem reduce complexitatea la O(N*K) folosind structura necesara in rezolvarea acelor probleme si anume o coada (in literatura de specialitate se intalneste ca "deque with heap order"). Aceasta structura a mai fost tratata si in solutiilor problemelor prezentate mai sus, deci nu voi intra in detalii. Este evident ca un algoritm de complexitate O(N*K) se incadreaza in timp, dar mai apare in calcul faptul ca sirul este circular. Un algoritm O(N*K) care nu trateaza acest lucru ia 40 de puncte. O prima idee ar fi sa aplicam acelasi algoritm pe fiecare permutare circulara dar se ridica complexitatea iar la O(N^2*K). Aceasta abordare ar trebui sa obtina intre 50 si 60 de puncte. Putem trata circularitatea sirului tot in O(N*K) incercand sa obtinem o secventa care contine elemente N si 1. Putem realiza acest lucru astfel:

• dupa ce realizam prima data dinamica, reinitializam linia 1 astfel A(1, i) = S(i)
• aplicam din nou dinamica -> de data aceasta algoritmul va fi obligat sa intoarca rezultate care contin neaparat elementul 1 intr-o secventa din cauza initializarii
• pentru fiecare pozitie i<=N comparam rezultatul A(i, K)+S(N)-S(i) (adaugam la secventa care il contine pe 1 o bucata care il contine pe N) cu cel mai bun obtinut

Astfel, problema este rezolvabila in complexitate O(N*K).

Poligon

Problema cere sa determinam cate puncte din cele M sunt in interiorul poligonului. O abordare imediata a acestei probleme ar fi sa determinam pentru fiecare punct in O(N) daca este sau nu in interiorul poligonului. Exista mai multe moduri de a rezolva acest lucru. Un mod ar fi sa ducem o semidreapta pornind din punctul nostru si sa vedem de cate ori intersecteaza laturile poligonului: daca intersecteaza poligonul de un numar par de ori atunci inseamna ca punctul este in exterior, iar daca ea intersecteaza de un numar impar de ori laturile poligonului inseamna ca punctul este in interior. O alta modalitate: calculam suma unghiurilor pe care le fac extremele laturilor cu punctul nostr (unghiurile sunt luate pozitive sau negative dupa cum cele 3 puncte ce formeaza unghiul sunt in sens trigonometric sau orar), daca suma unghiurilor pentru toate laturile e 0 atunci punctul e in exteriorul poligonului, iar daca suma unghiurilor e 2*Pi atunci punctul e in interiorul poligonului, pentru mai multe detalii puteti
sa va uitati pe urmatoarele pagini:

http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Dimensiunile datelor de intrare ne sugereaza ca trebuie sa acceleram determinarea pozitiei punctelor fata de poligon. Daca poligonul ar fi convex, este usor sa facem acest test in O(log N): consideram un varf al poligonului si semidrepte ce pleaca din el spre celelalte varfuri, cu cautare binara gasim in ce sector determinat de doua semidrepte intra punctul pentru care vrem sa determinam incluziunea in poligon, dupa ce gasim sectorul testul de incluziune se reduce la determinarea incluziunii intr-un triunghi. Aceasta metoda eleganta si simpla merge pentru poligon convex, dar pentru unul oarecare trebuie sa gasim o alta abordare.

Pentru poligoane concave, mergand pe aceeasi idee, impartirea in zone pentru care este mai usor sa determinam incluziunea se va face un pic diferit. Sortam coordonatele x ale punctelor poligonului si ducem prin fiecare coordonata x distincta cate o dreapta verticala. Se formeaza astfel niste benzi verticale intersectate de laturile poligonului. Pentru fiecare banda tinem minte ce laturi ale poligonului intersecteaza aceasta banda si sortam aceste laturi pe verticala dupa mijlocul segmentului de intersectie al laturii cu banda. Acum pentru a determina daca un punct e in interiorul poligonului, determinam cu cautare binara mai intai banda din care face parte si apoi pentru banda respectiva deasupra cator segmente se afla, daca punctul e deasupra unui numar par de segmente atunci punctul e in exterior si daca e deasupra unui numar impar e interior. Astfel rezolvarea noastra are complexitatea O(N^2 log N) in faza de preprocesare si O(log N) pentru a determina pentru fiecare punct daca este interior sau
exterior poligonului. Complexitatea totala va fi O(N^2 log N + M log N).