Soluţii ONIS 2014, Runda 3

Bitonic

Solutia cea mai simpla este sa calculam prin programare dinamica, pentru fiecare pozitie 1 <= i <= n, urmatoarele valori:

  • fi[i] = cel mai lung subsir crescator care se termina pe pozitia i
  • fd[i] = cel mai lung subsir descrescator care se termina pe pozitia i
  • bi[i] = cel mai lung subsir crescator care incepe pe pozitia i
  • bd[i] = cel mai lung subsir descrescator care incepe pe pozitia i

Solutia va fi

  • max ( max_i { fi[i] + bd[i] - 1 }, max_i { fd[i] + bi[i] + 1 } ).

Valorile de mai sus se pot calcula in timp O(n2) folosind algoritmul standard pentru cel mai lung subsir crescator, rezultand un timp total de rulare de O(n2) / test.

Puncte3

Sortăm punctele după coordonate. Căutăm binar lungimea minim posibilă pentru segmentul de lungime maximă. Pentru o valoare a lungimii minime, parcurgem punctele în ordinea crescătoare a coordonatelor. La început creăm un segment pornind din primul punct. Când segmentul curent nu mai poate ajunge la punctul curent, creăm un nou segment pornind din acest punct. Complexitatea timp a acestui algoritm este O(N * (log(N) + log(Xmax))).

Matrice8

Vom calcula Sum[l]© ca fiind suma elementelor din submatricea Mat[1 … l][1 … c] (unde Mat este matricea binara data ca input). Această matrice poate fi calculată în timp O(N * M), folosind principiul includerii şi excluderii pe submatrice de dimensiuni cu 1 mai mici, şi ne permite sa verificam dacă o submatrice este uniformă în O(1). Folosim metoda programarii dinamice. Fie Min[l1][c1][l2][c2] numărul minim de tăieturi pentru a partiţiona submatricea Mat[l1 … l2][c1 … c2] în submatrice uniforme. Acest număr se poate calcula luand in considerare toate taieturile posibile, pe linii sau coloane, şi folosind rezultatele calculate anterior pentru submatricele obtinute după tăietură. Complexitatea algoritmului este O(N2 * M2 * (N + M)).

Friend of Friend

Vom considera reţeaua de prietenie un graf neorientat: fiecare om este un nod, iar o relaţie de prietenie dintre doi oameni este o muchie. Având două noduri x şi y, putem spune că x este prietenul prietenului lui y şi viceversa dacă lanţul de lungime minimă dintre nodurile x şi y are lungimea egală cu 2. Astfel, vom porni o parcurgere în lăţime din fiecare nod i, marcând nodurile care se află la distanţă 2 de nodul i.

Echilibru

Se pot genera toate submultimile multimii de 2 * N puncte. Apoi se numara numarul de elemente din submultime (cardinanul) si se calculeaza suma elementelor ei. Daca numarul de elemente este N si suma elementelor este exact jumatate din suma tuturor celor 2 * N elemente, atunci exista solutie pentru partitionare. Pentru a salva acest bit in numarul rezultat care se afiseaza, putem folosi formula:

  • rez |= (echilibru << (i));
    unde rez este initial 0, echilibru are valoarea 0 sau 1 dupa cum e raspunsul fiecarui test iar i este numarul testului (iterand de la T-1 la 0 pentru a respecta conditiile datelor de iesire)

Generarea tuturor submultimilor unei multimi se poate face in acest caz tot folosind operatii pe biti, printr-un bitset: for de la 0 la (1 << (2*N))-1, adica 2 la puterea (2*N)-1. Bitii cu valoarea 1 din acest numar vor selecta elementele care sunt in submultime (sunt 2 * N biti).

Zigsort

Vom sorta pe rand fiecare secventa de lungime (K+1) care este 'monotona', folosind algoritmul insertsort. Presupunand ca am sortat pana la o anumita pozitie din aceasta secventa (crescator sau descrescator dupa paritatea secventei), urmatorul element trebuie introdus prin interschimbari valide pe pozitia pe care respecta ordinea curenta. De exemplu daca avem sortat valid 8 > 6 > 4 > 3 si noua urmatoarea valoare trebuie sa fie > 3 (K = 4) dar ea are valoarea 7, vom interschimba pe rand 3 cu 7, apoi 4 cu 7 si in final 6 cu 7. La fiecare interschimbare vom aduce valoarea 7 cu o pozitie mai aproape de 8, lasand ordinea intre celelalte elemente neschimbata.

  • 8 > 6 > 4 > 3 > 7 swap(3, 7)
  • 8 > 6 > 4 > 7 > 3 swap(4, 7)
  • 8 > 6 > 7 > 4 > 3 swap(6, 7)
  • 8 > 7 > 6 > 4 > 3 swap(6, 7)

Atunci cand trecem de la o secventa la alta aplicand acest algoritm nu vom strica ordinea anterioara.

  • a1 > a2 > a3 < a4 < a5.

In momentul in care ordonam a3 < a4 < a5 vom aduce eventual numere cu valori tot mai mici pe pozitia a3. Astfel ele vor respecta ordinea fata de a2 (a2 > a3), deoarece a3 devine tot mai mic si prima valoare a3 respecta oricum aceasta ordine.

Numarul maxim de interschimbari care sunt necesare pentru o secventa de lunime (K + 1) numere este 0 + 1 + 2 + ... + k = (k) * (k + 1) / 2. In total sunt (N - 1) / K astfel de secvente - atentie elementele din capete se afla in cate doua secvente - deci avem maxim (N / k) * k * (k + 1) / 2 interschimbari, adica maxim 250000 interschimbari.

Dreptunghi2

Putem determina punctul pentru care X + Y are valoarea maxima. Acest punct se afla sigur pe o latura a dreptunghiului, mai exact cea din dreapta - sus (cum apare pe desen). Putem alege un punct de pe aceasta dreapta care are X = Y pentru simplitate. (X' = Y' = Max(Xi + Yi) / 2)

Punctul cu X + Y minim se va afla similar pe latura din stanga jos a dreptunghiului. Daca alegem punctul care are X = Y si de pe aceasta dreapta, este mai usor sa calculam distanta dintre aceste doua puncte decat dintre cele doua drepte. Astfel aflam o latura a dreptunghiului, cea paralela cu prima bisectoare.
Cealalta latura se afla similar calculand punctele cu valoarea minima si maxima pentru X - Y.

O alta solutie ar fi putut fi rotirea tuturor punctelor cu 45 grade. Acum trebuie sa determinam dreptunghiul care incadreaza aceste noi puncte si care are laturile paralele cu OX / OY. Aria se poate determina calculand valoarea minima si maxima pentru X si Y.

Dragonas

Dacă linia pe care se află Lulu este mai "jos" decât linia pe care se află Smaug (l1 >= l2), este evident că Lulu va câştiga acest joc. Vom trata doar cazul în care l1 < l2.

Primul pas către rezolvarea problemei este să ne gândim care este strategia optimă pe care o foloseşte Lulu. Avem câteva cazuri:

  • Dacă Lulu face o mişcare către Nord, aceeaşi mişcare poate fi efectuată şi de Smaug. Deci, se va ajunge la aceeaşi configuraţie.
  • Dacă Lulu face o mişcare către Est sau către Vest, Smaug poate fie să efectueze aceeaşi mişcare, caz în care se va ajunge din nou la aceeaşi configuraţie, sau să se mute "mai aproape" de Lulu, caz care nu este optim pentru Lulu.

Deci, strategia optimă pentru Lulu este să se mişte la fiecare secundă către Sud. Implicit, optim pentru Smaug va fi să se mişte către coloana curentă pe care se află Lulu. În alte cuvinte, optim pentru Smaug este să ajungă cât mai repede pe căsuţa (l2, c1), iar numărul de secunde în care Smaug ajunge în această căsuţă este egal cu |c1 - c2|. Analog, numărul de secunde în care Lulu ajunge în aceeaşi căsuţă este egal cu l2 - l1. Dacă Lulu ajunge înaintea lui Smaug în acest punct, el câştigă jocul. Altfel spus, dacă l2 - l1 < | c2 - c1 |, Lulu câştigă jocul.

Alegeri

Vom considera fiecare oraş ca fiind un nod, iar fiecare autostradă ca fiind o muchie. Vom seta costuri pe muchii astfel:

  • Dacă muchia reprezintă o autostradă stricată, costul ei va fi costul necesar pentru repararea autostrăzii.
  • Dacă muchia reprezintă o autostradă buna, costul ei va fi 0.

Dorim ca la final, graful nostru sa fie unul conex, iar suma costurilor muchiilor sa fie minimă. Am redus astfel problema la determinarea arborelui parţial de cost minim.

Spargere

Vom căuta binar răspunsul. Este optim să luăm bani din fiecare seif, la fiecare moment de timp în care acesta este "dispus" să ne ofere bani. Având astfel setat un număr T de secunde, vom putea calcula numărul de bani câştigaţi în acel timp folosindu-ne de o formulă simplă.