Solutii Junior Challenge 2019

Solutia problemei Deletegcd

Soluţia `O(N + QN^2log(valmax)) - 15 puncte`

Încercăm să eliminăm fiecare element şi să vedem explicit dacă cel mai mare divizor comun al celorlalte numere este mai mare ca 1, parcurgându-le şi folosind algoritmul lui Euclid.

Soluţii de `35 puncte`

Soluţia anterioară se poate optimiza, precalculând cel mai mare divizor comun pentru toate secvenţele din şir în O(N*N*log(valmax)), pentru a verifica în timp constant efectul eliminării unui număr (se observă că rămân maxim 2 secvenţe compacte de numere după eliminarea unui număr, a căror c.m.m.d.c poate fi calculat uşor). Această soluţie are complexitatea O(N*(N+Q)*log(valmax)), obţinând 35 de puncte, şi poate fi optimizată cu tehnici precum Range Minimum Query sau precalcularea în O(valmax*valmax) a tuturor c.m.m.d.c posibili, dar nu este necesar.

Soluţia `O((Nlog(valmax)+Qlog(valmax)*log(N)) - 75 puncte`

Ne vom baza pe 2 observaţii:

Pentru ca o secvenţă de numere să aibă c.m.m.d.c diferit de 1, trebuie ca toate numerele să aibă un factor prim comun.
Dacă alegem 2 elemente din secvenţă, cel puţin unul din ele va rămâne în secvenţa finală, din care a fost scos un element.

Ca o urmare a acestor 2 observaţii, putem vedea dacă un şir respectă condiţia din enunţ verificând dacă cel puţin un factor prim a oricăror 2 numere de pe poziţii diferite din secvenţă divide toate numerele în afară de unul (sau toate numerele).Ţinând o listă sortată cu poziţiile numerelor care divid un numar prim p, pentru fiecare număr prim p, putem folosi căutare binară pentru a determina câte numere din o anumita secvenţă divid un anumit număr prim în O(log(N)).De asemenea, avem doar O(log(valmax)) numere prime relevante datorită celor 2 observaţii.

Soluţia `O((N+Q)*log(valmax)) - 100 puncte`

Pentru a obţine 100 de puncte, este necesară optimizarea următoare: în loc de căutare binară, în lista unui număr prim vom ţine pentru fiecare poziţie din listă cât de multe numere consecutive există dacă începem cu poziţia respectivă. Astfel, putem sări în O(1), la prima poziţie din dreapta care nu divide un număr prim, verificând dacă putem acoperi întreaga secvenţă cu cel mult 2 salturi.Astfel, complexitatea se reduce la O(log(valmax)) pe query. Precalcularea listelor se poate face cu un ciur şi o parcurgere a şirului.

Soluţie alternativă `O(N*log(ValMax) + Q) - 100 puncte`

Ne creăm o structură care suportă următoarele operaţii:

Inserăm un număr X.
Ştergem un număr X.
Query: ne răspunde cu DA dacă putem elimina un număr din structură astfel încât c.m.m.d.c.-ul lor să fie diferit de 1

Putem menţine structura de mai sus astfel: vom ţine un vector de frecvenţa în care pentru fiecare factor prim ţinem minte câte numere din structură sunt divizibile cu acel factor prim. Pentru a afla răspunsul la query din structură, vom ţine un vector de frecvenţă pe primul vector de frecvenţă. Inserarea, respectiv ştergerea se realizează în O(log(valmax)), iar răspunsul la un query se realizează în O(1).

Acum putem rezolva problema iniţială cu algoritmul lui Mo, dar se poate mai bine de atât. Calculăm vectorul expand[R] = cel mai mic L astfel încât subsecvenţa [L...R] să fie aproape-şmecheră. Observăm că expand[R] ≤ expand[R+1]. Putem aplica astfel tehnica two-pointers pentru a calcula vectorul expand.

Pentru a răspunde la un query l...r, putem pur şi simplu să vedem dacă l ≥ expand[r].

Soluţia problemei Mixed Signals

Observaţia de baza

Dacă le-am acorda valoarea 1 oamenilor care mint, iar 0 celor care spun adevărul, operaţia de tip 1 se poate traduce că operaţia SAU-EXCLUSIV (XOR) între valorile oamenilor $X_1, X_2, ... X_K$ (desigur, această proprietate aplicandu-se doar în cazul când nu există o persoană mută printre cei $K$ oameni).

Soluţii

Precizări :

Acestea sunt câteva dintre soluţiile problemei, aceasta puntandu-se rezolva în foarte multe moduri
De acum încolo prin $X_i$ mă voi referi la valoarea omului i

Fără persoane mute, cu întrebări de tip 2, N întrebări în total - 30 de puncte

O să punem o întrebare de tip 2 despre primul om, astfel aflându-i valoarea. Acum punem $N-1$ întrebări de tip 1 despre fiecare persoană şi prima, aflând $X_i xor X_1$ , automat ştiind chiar $X_i$ datorită faptului că ştim $X_1$ .

Cu persoane mute, cu întrebări de tip 2, N+5 întrebări în total - 50 de puncte

Acum, fiind şi persoane mute, nu mai putem pune o întrebare de tip 2 doar despre primului om pentru că acesta poate fi mut (şi orice întrebare de tip 1 care îl include ar da răspunsul 2). Astfel vom pune 5 întrebări de tip 2 despre 5 persoane alese aleatoriu. Fiind maxim $N/2$ persoane mute, este o probabilitate foarte mare să găsim măcar un om care nu este mut printre cei 5. După vom proceda la fel ca la soluţia de 30 de puncte.

Fără persoane mute, fără întrebări de tip 2, N întrebări în total - 60 de puncte

Metoda 1: Punem 2 întrebări de tip 1 pentru a afla : $A = X_1 xor X_2 xor X_3$ şi $B = X_2 xor X_3$ . Din proprietăţile xor-ului rezultă că $X_1 = A xor B$ . Ştiind valoarea primului om, putem aplică strategia din primele 2 soluţii.
Metoda 2: Această metodă ne aduce mai aproape de soluţia de 100. În loc să ne gândim la un mod de a afla valoarea primului om, vom încerca să clasificăm restul persoanelor în funcţie de el. Se observă faptul că dacă $X_1 xor X_i = 0$ , atunci $X_i = X_1$ , respectiv $X_i != X_1$ dacă $X_1 xor X_i = 1$ . Vom forma 2 grupe, în prima fiind persoanele cu valoare egală cu cea a primului (inclusiv primul), iar în a două fiind cei diferiţi. Acum doar trebuie să mai aflăm care dintre grupe spune adevărul şi care nu, asta putându-se realiza în mai multe moduri. De exemplu putem pune întrebarea de tip 1 despre 3 oameni din aceaşi grupă sau despre 2 oameni dintr-o grupa şi unul din cealaltă (de avut grijă la cazul când o grupa este goală sau acela când nicio grupa nu are mai mult de 2 oameni).

Cu persoane mute, fără întrebări de tip 2, N+10 întrebări în total - 100 de puncte

Având şi persoane mute nu putem aplică direct metodă a 2-a de la soluţia de 60 de puncte pentru că primul om poate fi mut. Aşadar, o să alegem aleatoriu 2 persoane şi o să punem întrebarea de tip 1 despre ele. Dacă răspunsul este diferit de 2 atunci înseamnă că am găsit o persoană care nu este mută, astfel putând proceda la fel că la soluţia de 60 de puncte. Altfel, vom continuă să alegem 2 persoane şi să repetăm procesul. Datorită faptului că sunt maxim $N/2$ persoane mute, este o probabilitate foarte mare de a găsi o pereche de persoane care să nu fie mute în maxim 10 întrebări.

Soluţia problemei Obstacole

Pentru început, vom reaminti o formulă esenţială în rezolvarea acestei probleme:

Daca avem un segment {{x1, y1}, {x2, y2}} şi un anumit X între x1 şi x2, pentru a afla punctul {X, Y} care aparţine segmentului putem proceda astfel:

Calculăm ecuaţia dreptei de forma aX + bY + c = 0 şi calculăm pe Y după formula Y = (-c - aX) / b
Putem utiliza formula Y = y1 + (x - x1) * (y2 - y1) / (x2 - x1)

O să denumim funcţia de mai sus pentru un segment getY(X).

Deoarece sunt utilizate împărţiri, Y va fi un număr raţional. Ca să comparăm două numere Y1 şi Y2, putem folosi:

double/long double
Putem crea o clasă de fracţii. Nu vom putea să le comparăm făcând produsul "în cruce" din cauza faptului ca depăşeşte long long-ul, dar dacă ţinem minte fracţiile ca pereche de parte întreagă şi fracţie subunitară, putem compara mai întâi părţile întregi şi în caz de egalitate, comparăm fracţiile făcând produsul "în cruce". Astfel nu vor exista probleme de precizie.

Orice combinaţie de mai sus ar trebui să ia punctajul complet pe subtask.

Soluţia `O(N^2 * M) - 20 puncte`

Putem să calculăm pentru un punct {X, Y} care este primul segment de deasupra lui, luând segmentul care are getY(X) minim, mai mare sau egal decât Y şi care nu are unul din capete care să coincidă cu punctul de query. Deoarece avem N query-uri şi cu un query putem trece prin maxim M segmente. Complexitatea finală va fi O(N^2 * M)

Soluţia `O((N+M) * N) - 50 puncte`

O observaţie importantă în rezolvarea problemei este următoarea:
Dacă nişte puncte cad pe acelaşi segment, ele se vor duce în capătul superior al segmentului, şi de acolo drumul lor va fi identic, deci vor fi comprimate într-un singur query. Acel query, împreună cu alte query-uri, se poate duce şi el în alt segment şi de acolo şi el se comprimă cu celelalte. Practic drumurile vor desena pe foaie mai mulţi arbori.

Soluţia va fi următoarea: la cele M query-uri de la input, mai adăugăm N query-uri, acelea fiind capetele superioare ale segmentelor, iar pentru fiecare query calculăm primul segment de deasupra, asemenea subtaskului anterior. Astfel pentru fiecare query, vom ştii în ce query se comprimă şi vom avea pentru fiecare query un punct tată. Pentru a da răspunsul final la query, calculăm care este rădăcina componentei în care se află punctul iniţial ori cu mai multe dfs-uri, ori memoizând.

Soluţia `O(N+M) * log(N) - 100 puncte`

Vom folosi tehnica liniei de baleiere. Vom avea mai multe evenimente:

Inserează un segment în set.
Şterge un segment din set.
Query: pentru un punct, află primul segment de deasupra lui.

Pentru a menţine această structură, putem implementa orice arbore binar echilibrat de căutare sau putem folosi set-ul implementat în STL. Pentru a compara două segmente, le putem compara după getY(X), unde X este o variabilă globală (asemenea Convex Hull Trick-ului dinamic). Pentru a afla primul segment de deasupra unui punct, putem folosi pur şi simplu lower_bound/upper_bound, interogând un segment punctiform.

Soluţia problemei Supersenzor

Notăm cu ceil(x) partea întreagă superioară a lui x. Exemplu : ceil(34) = 34, ceil(27,3) = 28, ceil(5,8) = 6.

Pentru o valoare val fixată, durata totală de timp pentru care becul stă aprins este :
ceil(a[ 1 ] / val) * val + ceil(a[ 2 ] / val) * val + ... + ceil(a[ n ] / val) = val * (ceil(a[ 1 ] / val) + ceil(a[ 2 ] / val) + ... + ceil(a[ n ] / val)).

Aşadar observăm că trebuie să minimizăm funcţia f(x) = x * (ceil(a[ 1 ] / x) + ceil(a[ 2 ] / x) + ... + ceil(a[ n ] / x)).
Prin urmare, dacă fixăm ceil(a[ i ] / x) pentru i = 1..n ne interesează doar x-ul minim.
Astfel vom verifica doar x = T şi valorile la care se modifică ceil(a[i] / x) cu i arbitrar.

Se ştie că funcţia ceil(N / x) cu x întreg are maxim 2 * sqrt(N) valori distincte : 1, 2, ... sqrt(N), ceil(N / sqrt(N)) ... ceil(N / 2), ceil(N / 1).
Aceste ~2 * sqrt(N) valori reprezintă şi valorile în care funcţia ceil(N / x) se modifică, astfel luând aceste valori pt N = a[i] cu i = 1..n
vom obţine toate valorile relevante pentru funcţie.

Soluţia problemei Overpower

Observatia de baza este ca pentru a descompune optim un numar X pentru a obtine "puterea" maxima, este mereu optim sa alegem numarul exponentiat ca fiind prim.

Subtask1

Descompunem fiecare numar din intervalul (A, B) in factori primi, raspunsul este exponentul maxim.

Subtask2

Pentru fiecare putere de numar prim din intervalul (1, 10⁶) vedem daca apare sau nu in intervalul (A, B) ($p$ apare in intervalul (A, B) daca divide cel putin un numar din interval <=> B / p - (A - 1) / p > 0).

Subtask3

Daca raspunul este mai mare de 1, inseamna ca numarul exponentiat trebuie sa fie mai mic de sqrt(B), deci incercam toate puterile ale numerelor prime pana in sqrt(B), si daca niciuna nu apare in intervalul (A, B) atunci raspunsul este 1.

Subtask 4

Cum A = B, ni se cere sa il descompunem pe A.
Verificam toate numerele prime pana in radicalul de ordin 3 al lui n (si daca n se divide cu vreunul din ele atunci updatam raspunsul si il impartim pe n).
Daca n nu este 1 dupa acest algoritm, atunci fie este de forma

n = p
n = p * q
n = p²

Unde p si q sunt numere prime.
Inafara de al 3-lea caz pe care il putem verifica cu functia sqrt(x) sau cautare binara, celelalte doua cazuri au ambele raspunsul 1 deci le putem ignora.

Subtask 5

Subtaskul 5 este un hibrid dintre subtaskul 4 si subtaskul 3:

Daca B - A + 1 < 4, atunci avem un interval de lungime maxim 3 deci ne permitem sa aplicam algoritmul de la subtaskul 4.
Daca B - A + 1 >= 4, atunci stim ca exista un numar in interval divizibil cu 4 = 2², deci nu are sens decat sa cautam un exponent de cel putin 3, si facem aceasta analog subtaskului 3 (Dar ducandu-ne pana in radical de ordin 3).

Soluţia problemei Abba

O buna cale de inceput in rezolvarea oricarei probleme este obtinerea unui exemplu mai mare si efectuarea unor observatii:

a b
a ab b
a aab ab abb b
a aaab aab aabab ab ababb abb abbb b

O prima observatie ar fi ca propozitia $N$ are $2^N-1$ cuvinte. O alta observatie ar fi ca un cuvant nu apare decat o singura data intr-o propozitie (demonstratia o sa devina evidenta pana la sfarsitul solutiei).

O observatie rapida ce si pare mai utila ar fi ca daca avem doua cuvinte consecutive $u$ si $v$ intr-o propozitie, in urmatoarele propozitii, toate cuvintele dintre $u$ si $v$ il vor avea pe $u$ ca prefix si pe $v$ ca sufix. Desi triviala, urmand sirul deductiv de la aceasta, daca avem trei cuvinte consecutive $u,v,w$ , in propozitiile urmatoare, singurele cuvinte care se vor termina in $v$ vor fi cele dintre $u$ si $v$ , iar singurele cuvinte ce vor incepe cu $v$ vor fi cele dintre $v$ si $w$ . Spre exemplu, verificand daca un cuvant incepe sau se termina cu ab, aflam daca cuvantul se afla in prima respectiv a doua jumatate a propozitiei. Acest lucru deja ne sugereaza o abordare in stilul unei cautari binare / divde et impera.

raspuns(str, prefix, sufix):
        if (lungime(sufix) + lungime(prefix) > lungime(str))
            (Cuvantul nu apare in nicio propozitie!)
        if (prefix + sufix == str)
            return 1
        mid = prefix + sufix
        if (mid este sufix al str)
            return 2 * raspuns(str, prefix, mid) - 1
        else if (mid este prefix al str)
            return 2 * raspuns(str, mid, sufix)
        else
            (Cuvantul nu apare in nicio propozitie!)

Pseudocodul de mai sus este o schita a solutiei, ce returneaza pozitia in propozitie a cuvantului cautat, prima propozitie in care apare cuvantul fiind adancimea recursivitatii in care s-a dat return 1. Observam ca suma lungimilor sufix si prefix creste cu cel putin 1 la fiecare apel si functia isi atinge conditia de oprire atunci cand suma depaseste sau egaleaza lungimea cuvantului. Astfel, observam ca avem cel mult $O(N)$ apeluri de functie, unde $N$ este lungimea cuvantului cautat. Astfel, daca reusim sa verificam rapid daca un cuvant este prefix sau sufix al altuia, avem solutia de complexitate optima (liniara in marimea inputului). Aceasta verificare este realizabila in $O(1)$ folosind hash-uri, noi nu trebuind sa stocam sau trimitem ca parametri ai functiei raspuns efectiv prefixul si sufixul unui string, putand trasmite ca parametri si concatena direct hash-urile stringurilor corespondente.

infoarena informatica de performanta