Soluţii ONIS 2015, Runda 3

• Lista de probleme
• Ceasuri
• Ecotraseu
• Prezenta
• Aurel
• Prietenie3
• Blas
• Produs4
• Verlab
• Spatiu
• Parcele2

Ceasuri

Pentru a rezolva problema trebuie intai determinata prima suprapunere a celor trei ace ale ceasului.
Acest lucru se poate realiza determinand suprapunerile orarului cu minutarul si a minutarului cu secundarul.
Daca consideram ca x este numarul de ore din jumatate de zi, adica n/2, si y este numarul de minute dintr-o ora, adica m, atunci:
- viteza de deplasare a orarului (vo) într-o ora este: 360/x (grade/ora)
- viteza de deplasare a minutarului (vm) într-o ora este: 360 (grade/ora)
- viteza de deplasare a secundarului (vs) într-o ora este: 360*y (grade/ora)
Intr-o ora orarul parcurge o distanta d, iar minutarul d+360 => do = dm - 360.
Deoarece d=v*t, relatia de mai sus devine: t*360/x = t*360 - 360 => t = x/(x-1)
Astfel, prima intalnire a orarului si a minutarului este dupa x/(x-1) ore.
Deci periodicitatea cu care se intalnesc orarul si minutarul este x/(x-1).
In mod analog se determina periodicitatea cu care se intalnesc minutarul si secundarul: 1/(y-1).
Problema se rezuma la a gasi toate suprapunerile orar-minutar si de a verifica daca nu cumva coincide cu suprapunerea minutar-secundar.
Ceea ce inseamna ca trebuie determinate toate pechile k1, k2 (numere naturale) astfel incat: k1*x/(x-1)=k2/(y-1)
Daca incercam pentru toti k1 incepand cu 1 si mai mici decat n, atunci gasim o suprapunere a celor trei ace daca x * k1 * (y - 1)) se divide la (x - 1).
Prima valoare k1 care indeplineste conditia de mai sus ne da timpul primei suprapuneri, k1*x/(x-1), iar numarul total de suprapuneri dintr-o zi este calculat ca fiind 2*x/(k1*x/(x-1)).

Ecotraseu

Gasim un nod central, care prin stergerea sa transforma arborele de dimensiune n in arbori de dimensiuni cel mult n / 2. Parcurgem in adancime din nodul central si retinem frunzele, impreuna cu distantele de la nodul central. Daca doua drumuri de distante opuse trec prin nodul central, am gasit drumul ca fiind concatenarea celor doua drumuri. Altfel, sterg nodul central si repet procedeul in fiecare arbore din padurea care se formeaza. Complexitatea timp este O(n log n), iar complexitatea spatiu este O(n).

Prezenta

Se cere numarul de permutari care au exact k+1 secvente crescatoare.

Notam cu a[i][j] numarul de permutari de lungime i care au j secvente creascatoare.

O permutare din a[i][j] se poate obtine dintr-o permutare din a[i - 1][j] prin adaugarea lui "i" la sfarsitul oricarei din cele j secvente crescatoare (numarul de secvente ramane acelasi) sau din a[i - 1][j - 1] prin adaugarea lui "i" in oricare din celelalte i - j + 1 pozitii (creste numarul de secvente crescatoare cu 1).

Deci am obtinut relatia de recurenta:

  a[i][j] = j * a[i - 1][j] + (i - j + 1) * a[i - 1][j - 1];

Initial a[i][i] = a[i] = 1.

Raspunsul se gaseste in a[n][k + 1].

Implementand relatia de recurenta de mai sus obtinem o complexitate de O(n * k).

Aurel

Problema se rezolva prin metoda programarii dinamice. Notam cu A[i][j] multimea de siruri de aur de lungime i cu suma elementelor egala cu j. Analizam doua cazuri pentru sirurile din A[i][j]:

Cazul 1: sirul incepe cu valoare 1
* Observam ca daca eliminam primul element din sir si scadem valoare 1 din celalalte n - 1 elemente obtinem un sir din A[i - 1][j - i]. In plus, exista o bijectie intre A[i - 1][j - i] si multimea sirurilor din A[i][j] care incep cu valoarea 1.

Cazul 2: sirul incepe cu o valoarea strict mai mare ca 1
* Observam ca daca scadem valoarea 1 din fiecare element din sir obtinem un sir din A[i][j - i]. In plus, exista o bijectie intre A[i][j - 1] si multimea sirurilor din A[i][j] care incep cu o valoare strict mai mare ca 1.

Din observatiile de mai sus deducem relatia de recurenta |A[i][j]| = |A[i - 1][j - i]| + |A[i][j - i]|.
Pentru a optimiza consumul de memorie, observam ca la un anumit pas e nevoie sa retinem doar doua linii din matrice (linia curenta si linia precedenta).
Complexitatea timp este O(N * S). Memoria folosita este O(S).

Prietenie3

1. Folosind cautare binara/ternara:
Definim functia distance(k) = (numarul de operatii pentru ca min(V) >= k) + (numarul de operatii pentru ca max® <= k). Se poate demonstra matematic faptul ca functia distance este convexa (prima paranteza descreste, in timp ce a doua paranteza creste).

2. Sortare si calcul folosind o observatie
Sortam V crescator si R descrescator. Deoarece vom dori intotdeauna sa crestem valoarea minima din V si sa scadem valoarea maxima din R, pana le vom aduce la o valoare comuna. Oricare va fi valoarea comuna, numarul de operatii va fi Ri Vi.
Vom repeta procedeul cat timp i <= N si i <= M si cat timp Ri > Vi.

Blas

Observam ca, daca intr-un termen din secventa exista un 0 urmat imediat de 1, intre 0 si 1 apare un punct de separare in sensul ca
cele doua subsecventa (cea care se termina in 0 si cea care incepe cu 1) inainteaza independent.

In continuare am scris primii termeni ai secventei, in care punctele de separare sunt marcate printr-un “|”:

s_1 = 1
s_2 = 11
s_3 = 10|1
s_4 = 1110|11
s_5 = 11110|10|1
s_6 = 100|110|1110|11
s_7 = 11100|10|110|11110|10|1
s_8 = 111100|1110|10|110|100|110|1110|11
s_9 = 100|1100|11110|1110|10|110|11100|10|110|11110|10|1
s_10 = 11100|10|1100|100|110|11110|1110|10|110|111100|1110|10|110|100|110|1110|11
s_11 = 111100|1110|10|1100|11100|10|110|100|110|11110|1110|10|110|100|1100|11110|1110|10|110|11100|10|110|11110|10|1
s_12 = 100|1100|11110|1110|10|1100|111100|1110|10|110|11100|10|110|100|110|11110|1110|10|110|11100|10|1100|100|110|11110|1110|10|110|111100|1110|10|110|100|110|1110|11

Se observa ca toti termenii sunt concatenari de secvente “atomice”:

1, 11, 10, 1110, 11110, 100, 110, 11100, 111100, 1100

(orice secventa atomica se transforma intr-un pas intr-o alta secventa atomica sau intr-o concatenare de doua secventa atomice).

In tabelul urmator este sumarizat modul in care se transforma fiecare secventa atomica:

a_1  1 -> 11
a_2  11 -> 10 | 1
a_3  10 -> 1110
a_4  1110 -> 11110
a_5  11110 -> 100 | 110
a_6  100 -> 11100
a_7  110 -> 10 | 110
a_8  11100 -> 111100
a_9  111100 -> 100 | 1100
a_10  1100 -> 10 | 1100

Daca se noteaza cu l(i, j) lungimea termenului obtinut din a_i dupa j pasi, avem ca:

- l(i, 0) = |a_i| (dupa 0 pasi, lungimea este chiar numarul de caractere din a_i - l(i, j) = l(i’, j - 1) daca a_i -> a_i’ (a_i avanseaza intr-un pas intr-o singura secventa atomica a_i’) sau - l(i, j) = l(i’, j - 1) + l(i’’, j - 1) daca a_i -> a_i’ | a_i’’ (a_i avanseaza intr-un pas intr-o pereche de secvente atomice a_i’ | a_i’’.

Daca implementam direct relatia de recurenta, obtinem un algoritm care calculeaza l(1, n) (rezultatul problemei) in timp O(n).

Pentru a obtine o complexitate mai buna, notam vectorul l(_, j) cu k_j. Se observa ca exista o matrice M astfel incat k_j = k_(j-1) * M.
Rezultatul k_n este deci k_0 * M^{n. Este suficient sa calculam M}n folosind exponentierea rapida pentru a obtine un timp de rulare O(log n).

Matricea M:

  1  11  10  1110  11110  100  110  11100  111100  1100
---------------------------------------------------------------------------------
1  | 0  1  0  0  0  0  0  0  0  0
11  | 1  0  1  0  0  0  0  0  0  0
10  | 0  0  0  1  0  0  0  0  0  0
1110  | 0  0  0  0  1  0  0  0  0  0
11110  | 0  0  0  0  0  1  1  0  0  0
100  | 0  0  0  0  0  0  0  1  0  0
110  | 0  0  1  0  0  0  1  0  0  0
11100  | 0  0  0  0  0  0  0  0  1  0
111100  | 0  0  0  0  0  1  0  0  0  1
1100  | 0  0  1  0  0  0  0  0  0  1

-----------------------------------------------------

Produs4

Produsul maxim se poate alege din doua posibilitati care acopera toate cazurile:
* cele mai mari trei numere din vector
* cel mai mare numar si doua cele mai mici valori (in cazul in care sunt numere negative).
Se pot calcula ambele valori iar apoi se afiseaza maximul dintre ele.

Verlab

Verificam sa avem bordat caroiajul si sa nu avem doua celule care au pereti dubli intre ele. Transformam caroiajul intr-un graf cu r x c noduri si cel mult 4 x r x c muchii. Apoi parcurgem graful dintr-un nod, si verificam sa putem ajunge in fiecare celula din caroiaj. Apoi verificam sa nu avem cicluri, folosind algoritmul lui Tarjan in timp O((n = r x c) + (m = r x c)). Algoritmul final are complexitatea timp O(r x c) si complexitatea spatiu O(r x c).

Spatiu

Se poate observa ca dupa fiecare pas, punctele posibil vor fi asezate sub forma unui diamant (sau mai bine spus, un dreptunghi pe diagonala). Acesta poate fi reprezentat folosind 2 valori:
lungime si latime. De fiecare data cand intalnim o operatie de tipul 1, 2 sau 5, incrementam lungimea iar de fiecare data cand intalnim o operatie de tipul 3, 4 sau 5, incrementam latimea.
Afisam lungime * latime;

Parcele2

Intrucat intre inaltimea unui copac si varsta acestuia este o relatie de 1 la 1, vom lucra doar cu varsta, iar la final o vom transforma pe aceasta in inaltime. Ne vom folosi de un arbore de intervale in 2 dimensiuni, in care vom salva pentru fiecare nod sumele XOR din dreptunghiul determinat de origine si pozitia x, y din AIB; fiecare bit din numarul AIB[x][y] ne spune daca avem un numarul par (in cazul in care bit-ul este 0) sau un numarul impar (int care bit-ul este 1) de copaci cu de varsta V in dreptunghiul ({0,0}, {x,y}), unde V=pozitia bit-ului in cadrul numarul AIB[x][y]; La sfarsitul fiecarui query vom updata AIB-ul, a.i. zona interogata sa devina "frumoasa";