Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-03-25 19:57:39.
Revizia anterioară   Revizia următoare  

Solutii Runda 4

Next

(problema usoara, clasa a 9-a)

Folosind operatii pe numere mari se calculeaza restul lui N la numarul D. Fie R acest rest, se va aduna la numarul N valoarea (D-R) mod D (a mod b reprezinta restul numarului a la impartirea cu b). Numarul astfel obtinut va reprezenta primul numar mai mare sau egal decat N divizibil cu D. O prezentare detaliata a modului in care se pot implementa operatiile cu numere mari necesare se gaseste aici. Complexitatea rezolvarii este O(lg N).

Shop

(problema medie, clasa a 9-a)

La prima vedere, problema este asemanatoare cu problema rucsacului, deci se poate aborda folosind metoda programarii dinamice. Avand in vedere limita mare pentru numarul L o astfel de abordare nu ar fi obtinut punctaj maxim.  Avand in vedere ca toate monezile sunt puteri ale numarului C, exista o rezolvare greedy: se determina cel mai mare tip de moneda CAi disponibil si se foloseste un numar maxim posibil de astfel de monede (minimul dintre L/CAi si Bi). Complexitatea unei astfel de solutii este O(logC L). O solutie care ar fi efectuat scaderi repetate ale cele mai mari monezi ar fi obtinut de asemenea punctaj maxim.

Dezastru

(problema grea, clasa a 9-a)

Bowling

(problema usoara, clasa a 10-a)

In primul rand, pentru a intelege solutia acestei probleme si altor probleme asemanatoare se recomanda citirea urmatoarelor documente despre teoria jocurilor:

Aceasta probleme se regaseste in literatura de specialitate si cu titlul de Kayles. Rezultatul pentru un joc se poate calcula in functie de XOR-ul numerelor Grundy pentru fiecare secventa de popice din sir. Cum N ≤ 50.000, trebuie calculate valorile Grundy pentru fiecare secventa de i popice cu i ≤ 50.000. Acestea se pot calcula in complexitate patratica si se pot pune in sursa ca un sir de constante. O alta solutie se foloseste de observatia ca incepand cu i = 72 sirul de valori se repeta cu perioada 12. Pentru fiecare test din fisier, complexitatea rezolvarii este O(N).

Regiuni

(problema medie, clasa a 10-a, problema usoara, clasele 11-12)

Elimin 2

(problema grea, clasa a 10-a)

Pentru a afla numarul maxim palindrom care este subsir al numarului N vom utiliza metoda programarii dinamice. Fie Li,j lungimea maxima a unui numar palindrom care se gaseste intre pozitiile i si j din numarul N. In momentul in care construim tabloul L consideram ca un numar poate incepe si cu cifra 0. Initial, Li,i = 1, pentru orice i de la 1 la numarul de cifre ale lui N. Vom calcula elementele tabloului L crescator in functie de marimea intervalelor (i,j). Daca consideram ca LEFTc,i este cea mai mica pozitie ≥ i in care apare cifra c in numarul N si RIGHTc,i cea mai mare pozitie ≤ i in care apare c in numarul N, avem urmatoarea relatie de recurenta:
Li,j = maxim(Li+1,j, Li,j-1, Li+1, RIGHT[N[i]][j]-1 + 2, LLEFT[N[j]][i]+1, j-1 + 2), unde prin Ni s-a notat a i-a cifra a numarului N. Relatia de recurenta trateaza urmatoarele cazuri:

  • nu folosim cifra a i-a in solutia optima
  • nu folosim cifra a j-a in solutia optima
  • folosim cifra a i-a ( notata c ) in solutia optima. Pentru ca numarul intre i si j sa fie palindrom, este suficient sa aflam ultima pozitie p inainte de j a cifrei c, solutia optima intre i si j obtinandu-se din solutia optima intre i+1 si p-1 la care adaugam 2 cifre ( cele din capete ).
  • folosim cifra a j-a ( notata c ) in solutia optima. Se trateaza similar.

Daca tablourile LEFT si RIGHT sunt construite inainte de a incepe programarea dinamica ( preprocesare ), putem construi tabloul L in complexitate O(NR_CIF2), unde NR_CIF este numarul de cifre ale lui N. Dupa ce am construit acest tablou, putem reconstitui solutia optima. Sa presupunem ca dorim sa cautam aceasta solutie intre pozitiile i si j si Li,j = X. Vom pune la capetele solutiei cea mai mare cifra c care indeplineste:
LLEFT[c,i]+1,RIGHT[c,j]-1 = X-2.

In final, eliminam 0-urile terminale ( de la ambele capete ale numarului palindrom ) si afisam acest numar. De precizat ca un algoritm de complexitate O(NR_CIF2) si constanta 10 ar fi obtinut in jur de 50 de puncte.

Distincte

(problema medie, clasele 11-12)

Vom calcula in timp liniar urmatorul vector:
urmi = min { j / i < j AND Aj = Ai}
Astfel, urmi va fi prima pozitie din dreapta egala ca valoare cu elementul de pe pozitia i (daca nu exista urmi consideram ca urmi este egal cu N+1). Considerand N puncte in plan cu coordonatele (i, urmi) la care se ataseaza valoarea Ai o intrebare st ≤ dr se rezolva facand un query in dreptunghiul [st..dr] x [dr+1..N], adica suma acelor elemente care se afla in interval, iar urmatoarea aparitie la dreapta este in afara intervalului. Acest query ne garanteaza ca se va face doar suma elementelor distincte din intervalul st..dr. O rezolvare care imparte vectorul in bucati de √N si rezolva intrebarile in O(√N) ar fi obtinut cel putin 50 de puncte, desi este probabil sa obtina si punctaj maxim optimizand codul. O rezolvare mai buna din punct de vedere al complexitatii este folosirea arborilor de intervale, tehnica descrisa aici si care poate fi folosita si la rezolvarea problemei Zoo. Din pacate, aceasta solutie este greu de implementat, iar solutia in O(lg2 N) probabil ar fi fost prea inceata pentru a obtine punctaj maxim.
Rezolvarea problemei se simplifica mult daca se sorteaza intervalele care se dau ca intrebari dupa capatul dreapta, si se proceseaza in aceasta ordine, apoi se afiseaza in ordinea initiala. Parcurgand intervalele descrescator dupa capatul dreapta se poate mentine suma punctelor care au coordonata y in afara capatului dreapta curent, si se pot calcula raspunsurile pentru intervale in timp O(log N) folosind fie un arbore de intervale, fie, si mai simplu, cu un arbore indexat binar.

Laser

(problema grea, clasele 11-12)

Vom considera semidreptele ce pleaca din origine si trec printr-un capat al unui segment. Vor exista 2*N astfel de semidrepte. Pentru fiecare din cele 2*N unghiuri formate consideram bisectoarea sa. Orice alta semidreapta ce pleaca din origine va intersecta aceleasi segmente cu una din cele 2*N bisectoare. Deci Gigel nu trebuie sa traga decat in unele din aceste bisectoare. In loc de bisectoare se putea considera orice alta semidreapta strict in interiorul unghiului, dar bisectoarea este mai usor de calculat.

Vom forma un sistem cu N ecuatii si 2*N necunoscute astfel: pentru un segment i se formeaza o ecuatie de forma

  • Bi = X1 * Ai,1 + X2 * Ai,2 + ... + X2*N * Ai,2*N
    • Bi este starea initiala a neonului i
    • X1, X2, ..., X2*N sunt cele 2*N necunoscute care semnifica faptul ca se trage pe directia respectivei bisectoare
    • Ai,j = 1 in caz ca bisectoarea j intersecteaza segmentul i, 0 in caz contrar.
      Sistemul se va rezolva modulo 2 folosind metoda lui Gauss.

Pentru calcularea valorilor Ai,j se calculeaza unghiul format de semidreptele ce trec prin capetele segmentului j si se testeaza daca semidreapta i se afla in interiorul sau. Trebuie avut grija la eventualele cazuri care apar, in special cand unghiul are o semidreapta in cadranul 4 si alta in cadranul 1.

Complexitate O(n3)

Sponsori

Organizarea finalei preONI este posibila datorita generosilor nostri sponsori: