Pentru a gasi cea de a {$K$}-a descompunere a lui $N$ ne vom folosi de aceasta matrice. Incercam pe rand sa punem fiecare divizor pe prima pozitie. Cand punem divizorul $i$ pe prima pozitie vom avea $A{~X,i~}$ posibilitati unde $X$ reprezinta indicele divizorului {$N/dvz{~i~}$}. Daca numarul acestor posibilitati este mai mic strict decat $K$ se va scadea acest numar din $K$ deoarece toate descompunerile care incep cu $dvz{~i~}$ sunt mai mici lexicografic decat varianta cautata de noi. Daca numarul acestor posibilitati este mai mare sau egal cu $K$ atunci descompunerea cautata de noi incepe cu {$dvz{~i~}$} si vom cauta in continuare a {$K$}-a descompunere pentru $N/dvz{~i~}$ folosind insa divizori mai mari decat {$dvz{~i~}$}.

h2.Struti

h2. Struti

h3. (clasele 11-12 problema medie)

Vom incerca sa rezolvam fiecare oferta in O(M*N), complexitatea finala a algoritmului fiind astfel O(P*M*N). Matricea de altitudini o vom nota cu mat. Intai vom determina maximul pe portiuni dreptunghiulare de forma [i,j]-[i+DX-1,j+DY-1], iar apoi, prin aceeasi metoda vom afla si minimul. Pentru a afla maximul pe astfel de portiuni, vom nota cu
MAX[i][j] = max{mat[i][j], mat[i+1][j].... mat[i+DX-1][y]}. Pentru fiecare coloana, vom utiliza o stiva sortata crescator dupa linii si descrescator dupa valoare altitudinilor. Stiva va retine elemente situate pe pozitii intre i si i+DX-1, cu altitudinile sortate descrescator.
Daca avem stiva construita la linia i, atunci pentru linia urmatoare vom scoate primul element din stiva doar daca pozitia pe care se afla este mai mica sau egala cu i, iar elementul curent il vom introduce pentru a mentine stiva ordonata. Complexitatea acestui pas este O(M*N), pe fiecare coloana efectuandu-se O(M) operatii, pentru ca fiecare element este introdus si scos din stiva exact o data. Pentru a afla maximul intregii portiuni dreptunghiulare, aplicam acelasi procedeu, notand:
MAX2[i][j] = max{MAX[i][j], MAX[i][j+1].... MAX[i][j+DY-1]}.
Pentru a afla si minimul pe portiuni se procedeaza similar.
In plus, pentru o oferta vom procesa atat perechea (DX, DY), cat si (DY, DX), daca si numai
daca DX diferit de DY. Altfel, vom proceda doar (DX, DY).
 

Vom incerca sa rezolvam fiecare oferta in {$O(M*N)$}, complexitatea finala a algoritmului fiind astfel {$O(P*M*N)$}. Matricea de altitudini o vom nota cu mat. Intai vom determina maximul pe portiuni dreptunghiulare de forma [{$i,j$}]-[{$i+DX-1,j+DY-1$}], iar apoi, prin aceeasi metoda vom afla si minimul. Pentru a afla maximul pe astfel de portiuni, vom nota cu {$MAX{~i,j~} = max{mat{~i,j~}, mat{~i+1,j~} ... mat{~i+DX-1,j~}}$}. Pentru fiecare coloana, vom utiliza o stiva sortata crescator dupa linii si descrescator dupa valoare altitudinilor. Stiva va retine elemente situate pe pozitii intre $i$ si {$i+DX-1$}, cu altitudinile sortate descrescator.
Daca avem stiva construita la linia {$i$}, atunci pentru linia urmatoare vom scoate primul element din stiva doar daca pozitia pe care se afla este mai mica sau egala cu {$i$}, iar elementul curent il vom introduce pentru a mentine stiva ordonata. Complexitatea acestui pas este {$O(M*N)$}, pe fiecare coloana efectuandu-se $O(M)$ operatii, pentru ca fiecare element este introdus si scos din stiva exact o data. Pentru a afla maximul intregii portiuni dreptunghiulare, aplicam acelasi procedeu, notand: {$MAX2{~i,j~} = max{MAX{~i,j~}, MAX{~i,j+1~} ... MAX{~i,j+DY-1~}}$}.

Camera
 
(clasele 11-12 problema grea)

Pentru a afla si minimul pe portiuni se procedeaza similar.

Problema pare la prima vedere destul de complicata. O solutie posibila ar fi sa pornim cu poligonul initial si sa il intersectam cu cate o dreapta determinata de fiecare din laturile lui. Aceasta rezolvare ar putea parea destul de complicata pentru ca implica intersectii de drepte cu poligoane concave. Zona din care toate laturile poligonului sunt vizibile este cunoscuta sub numele de nucleu sau kernel in engleza. Pentru ca dintr-un punct sa fie vizibila o latura a poligonului, acest punct trebuie sa fie in semiplanul determinat de aceasta latura. De aici deducem ca nucleul poligonului este de fapt intersectia celor N semiplane determinate de laturile poligonului. Pornim la inceput cu o zona patrata care contine toate punctele poligonului, astfel ea va contine si nucleul poligonului. Vom taia pe rand cu semiplane acest patrat. Poligonul intermediar va fi tot timpul convex, ceea ce ne usureaza cu mult rezolvarea. Vedem in urmatoarea imagine un exemplu al pasilor algoritmului:

In plus, pentru o oferta vom procesa atat perechea ({$DX, DY$}), cat si ({$DY, DX$}), daca si numai
daca {$DX$} diferit de {$DY$}. Altfel, vom proceda doar ({$DX, DY$}).

Parcurgem laturile poligonului intr-o ordine oarecare. Vom avea doi pointeri cur si next care vor reprezenta doua varfuri consecutive de pe poligonul care e solutia curenta. Daca ambele puncte sunt in interiorul semiplanului, atunci solutiei urmatoare ii adaugam punctul urmator. Daca punctul curent e in interior si punctul urmator este in exterior atunci solutiei ii adaugam punctul de intersectie p. Daca ambele puncte sunt in exterior procesam urmatoarea pereche. Daca punctul curent e in exterior si urmatorul punct este in interior atunci solutiei ii adaugam punctul de intersectie p si punctul urmator. Astfel obtinem un algoritm de complexitate O(n^2). Mentionam ca acest algoritm poate fi folosit si la determinarea intersectiei a doua poligoane convexe.
>

h2. Camera
h3. (clasele 11-12 problema grea)
Problema pare la prima vedere destul de complicata. O solutie posibila ar fi sa pornim cu poligonul initial si sa il intersectam cu cate o dreapta determinata de fiecare din laturile lui. Aceasta rezolvare ar putea parea destul de complicata pentru ca implica intersectii de drepte cu poligoane concave. Zona din care toate laturile poligonului sunt vizibile este cunoscuta sub numele de nucleu sau kernel in engleza. Pentru ca dintr-un punct sa fie vizibila o latura a poligonului, acest punct trebuie sa fie in semiplanul determinat de aceasta latura. De aici deducem ca nucleul poligonului este de fapt intersectia celor $N$ semiplane determinate de laturile poligonului. Pornim la inceput cu o zona patrata care contine toate punctele poligonului, astfel ea va contine si nucleul poligonului. Vom taia pe rand cu semiplane acest patrat. Poligonul intermediar va fi tot timpul convex, ceea ce ne usureaza cu mult rezolvarea. Vedem in urmatoarea imagine un exemplu al pasilor algoritmului:
!http://infoarena.ro/Solutii_preONI_2006_Runda_a_2_a?action=download&file=nucleu1.jpg!

References

Parcurgem laturile poligonului intr-o ordine oarecare. Vom avea doi pointeri $cur$ si $next$ care vor reprezenta doua varfuri consecutive de pe poligonul care e solutia curenta. Daca ambele puncte sunt in interiorul semiplanului, atunci solutiei urmatoare ii adaugam punctul urmator. Daca punctul curent e in interior si punctul urmator este in exterior atunci solutiei ii adaugam punctul de intersectie {$p$}. Daca ambele puncte sunt in exterior procesam urmatoarea pereche. Daca punctul curent e in exterior si urmatorul punct este in interior atunci solutiei ii adaugam punctul de intersectie $p$ si punctul urmator. Astfel obtinem un algoritm de complexitate {$O(n^2^)$}. Mentionam ca acest algoritm poate fi folosit si la determinarea intersectiei a doua poligoane convexe.

Visible links
1. http://infoarena.devnet.ro/index.php?page=preoni_2006
2. http://infoarena.devnet.ro/index.php?page=stats&conid=preoni62a&smod=top
3. http://infoarena.devnet.ro/index.php?page=stats&conid=preoni62b&smod=top
4. http://infoarena.devnet.ro/index.php?page=stats&conid=preoni62c&smod=top
5. http://infoarena.devnet.ro/clasament/preoni2006.php
6. http://info.devnet.ro/forum/viewforum.php?f=20
7. http://infoarena.devnet.ro/
8. http://www.cit.gu.edu.au/%7esosic/nqueens.html
9. http://en.wikipedia.org/wiki/eight_queens_puzzle

!http://infoarena.ro/Solutii_preONI_2006_Runda_a_2_a?action=download&file=nucleu2.jpg!