^ Nu cred ca ramane corect. Ambele surse verifica cate 8 puncte in ordine. Avand distanta setata mai mare, ar trebui verificate mai mult de 8 puncte (nu se mai respecta supozitia din care s-a dedus numarul de 8 puncte).

Solutiile in O(N) cu convex hull trick nu sunt "bulaneli"? Din ce stiu, ca sa aplicam corect optimizarea in O(N) ar trebui ca sirul pantelor (-S[ i ]) sa fie monoton, iar enuntul nu garanteaza asta.

[la patrat]

Am o dilema legata de solutiile postate pentru 100 de puncte.

Linia 39 @ http://www.infoarena.ro/job_detail/383250?action=view-source (are echivalent si in sursa cealalta, de complexitate N * log^2(N))

Cod:

for (int i = st; i < dr; ++ i) if (abs(Y[i].second - X[mid].first) <= best)

Conditia nu ar fi, de fapt:

Cod:

if (1ll * (Y[i].second - X[mid].first) * (Y[i].second - X[mid].first) <= best)

Din cate inteleg, best fiind cea mai mica distanta la patrat, ar trebui sa alegem punctele a caror distanta patrata pe orizontala fata linia verticala este mai mica sau egala cu best.
Avand conditia curenta (cea din sursele oficiale) se mai pastreaza invariantul verificarii a doar 8 puncte consecutive?

Sper sa ma ajute cineva cu o clarificare.
Multumesc mult!

LE: sursa de 100p care foloseste conditia cu distanta patrata: http://www.infoarena.ro/job_detail/1803161?action=view-source

Ma gandesc asa: combin sirul normal cu sirul reversed despartite de un caracter si construiesc suffix array-ul. Parcurg in ordine descrescatoare sufixele (de exemplu) si ma intereseaza suma tuturor LCP-urilor dintre sirul curent si cele de sub el, pe care o adun la solutie. La schimbarea indexului, va trebui sa modific LCP-urile de dedesubt, si am nevoie de inca o structura de date care sa-mi spuna cate valori mai mari decat o anumita valoare am si sa le transforme pe toate intr-o anumita valoare. M-am gandit aici la un arbore de intervale cu lazy update.
Indexul va fi intotdeauna pe un sufix al sirului reversed, iar suma LCP-urilor o voi lua doar din cele care apartin sirului normal.

S-ar putea sa ma complic tare, dar asta e ideea la care am ajuns.

Totusi, nu-mi dau seama inca cum voi elimina solutiile care nu sunt disjuncte.

Ma poate ajuta cineva cu o idee de rezolvare? M-am gandit la suffix arrays, dar nu vad nici asa cum as putea scoate mai putin de O(N^2).

Ma poate ajuta si pe mine cineva cu o scurta idee despre rezolvarea aceastei probleme?

Multumesc mult de tot!

LE: Rezolvat!

Nu merge... L-am scris in ambele moduri, nu iau 100p cu asta.... Ceva trebuie sa fie gresit.

//LE: Am inteles greseala asupra careia mi-ai atras atentia, si (cel putin cred eu) am corectat corespunzator.

Cod:

int new_rest = (j + P10[len - 2 * i] * k) % K;
new_rest = (new_rest * P10[1] + k) % K;

52p

Eu m-am gandit asa.

Sa spunem ca am un numar de forma aa si vreau sa-l aduc la forma baab.

Am restul de la aa, il numesc Rest. Ca sa aflu restul de la baab, fac urmatorul lucru.

aa * 10 + b -> (Rest * 10 + b) % K
si am restul lui aab la impartirea cu K acum

Adaug si b in fata
=> b * (10 ^ 3) + aab -> (b * (10 ^ 3) + Restul_lui_aab_la_impartirea_cu_K) % K

Si acum m-am gandit ca iese restul lui baab la impartirea cu K.

Rezultatele partiale ar trebui sa fie diferite fata de cealalta formula. Dar ma gandesc ca cel final ar trebui sa fie acelasi...

Ce e gresit?

Salut,

Am facut problema. Dar am o intrebare.
Cunosc doua metode de a calcula resturile in dinamica. Aparent, una merge, cealalta nu.

Prima, cea de 100, este chiar cea din descrierea solutiei realizata de autori.

Cod:

int new_rest = (j + (P10[len - i] + P10[i - 1]) * k) % K;

unde j este vechiul rest, P10[y] = (10 ^ y) % K, k noua cifra adaugata la inceputul si sfarsitul numarului anterior din dinamica si K - numarul din input cu care numarul trebuie sa se divida

A doua:

Cod:

int new_rest = (j + P10[len - 2 * i + 1] * k) % K;
new_rest = (new_rest * P10[1] + k) % K;

Literele au ramas identice cu cele de mai sus.
Inteleg ambele variante, insa, a doua pare a fi incorecta. Nu inteleg de ce.

Ma poate ajuta cineva?

Va multumesc anticipat!

@Sarac Sau Rege: in ce interval se incadreaza numerele din secventa?

Care-i treaba cu testele 7, 9, 11 si 13?

Salut!

Ma poate ajuta cineva cu un test verificabil de mana?

Merci!

//Nu mai am nevoie.

Salut!

Ma poate ajuta cineva cu un test, va rog frumos? (in afara de testul 1)

Va multumesc mult!

Ma poate ajuta cineva cu o idee de rezolvare? M-am impotmolit rau de tot...

Merci mult!

//Am rezolvat. Merci oricum.