424 Puncte

[•DITzoneC]

Aici puteţi discuta despre problema Puncte.

[•tm_radu]

Care ar fi complexitatea optima la problema asta? 

[•wefgef]

O(N+M).

[•tm_radu]

Nu-mi vine acuma in minte numai O(n*log n + m*log n). Care ii ideea de rezolvare pentru O(n+m)?

[Later Edit] : Am calculat gresit complexitatea. Cred ca stiu cum vine rezolvarea.

[•mariusdrg]

Am facut complexitate O(n + m * log (n)) .... am luat 100... Dar totusi poate cineva sa imi dea un hint cam cum s-ar face O(n + m)?...
                                         Multumesc anticipat!

[•wefgef]

Mda... se pare ca trebuie acolo ori o sortare si iti vine M log M sau o cautare binara si ai M log N

[•Mishu91]

Aveti un hint pentru O(M+N), va rog

[•Cosmin]

@Andrei Misarca, nu exista nici o solutie O(n + m).

Problema asta are limite prea stranse. Solutii ce au luat 100 iau 50 acum.

[•savim]

Am modificat limita de timp. Ar trebui sa nu se mai ia 50 cu o sursa de 100.

[•DorelBarbu]

Ar putea da cineva un mic hint ? Citirea solutiei oficiale nu prea m-a ajutat .  .