176 NextSeq

[•domino]

Aici puteţi discuta despre problema NextSeq.

[•alberte]

Am facut problema plecand de la primul sir si ajungand la al doilea, prin incrementare. Problema e ca nu reusesc sa depasesc 55 de puncte (la celalalte teste imi spune raspuns incorect sau fisier inexistent). Stie cineva unde as fi putut gresi?

[•silviug]

Pai nu putem sti judecand doar dupa punctaj. Sigur ai gresit ceva in implementare. Tot ce pot sa-ti spun e sa-ti construiesti singur niste teste (este relativ usor) si sa nimeresti unul care nu merge.

Succes.

PS: Nu post cod ca nu vom sta sa analizam. Debugheaza in continuare

[•devilkind]

shi eu fac acelasi lucru si tot 55 de puncte primesc, doar ca mie nu imi da incorect ci TLE

[andreit1]

Vezi poate intra undeva in ciclu infinit sau poate poti sa mai imbunatatesti ceva. Daca nu reusesti sa o faci sa intre in timp incearca solutia cu scaderea numerelor in baza n( precizata in solutia oficiala). Asta sigur o sa intre in timp.

[•cos_min]

ii ceva caz special la testu 17 ? nu inteleg dc nu merge  , in rest restul testelor imi merg

[•devilkind]

nu tin minte sa fie vreo ceva ciudat la vreo unul din teste, eu luam 55 la inceput ptr ca citeam cu streamuri, dupa ce am schimbat am luat 100 din prima. vezi restrictiile poate e de acolo.

[•cos_min]

mda, so rezolvat, declaram siruri de 10000 inloc de 10001 

[•peanutz]

Am incercat toate chestiile(iau 95) si nu iau primul test nici sa ... Nu-mi da cineva idee de un test banal de simplu?

[•marcelcodrea]

Poate ca nu ai luat in calcul cazul in care A si B sunt consecutive in ordine lexicografica si trebuie sa afisezi 0 !

[•peanutz]

Multumesc, dar nu e asta, eu ma gandeam la un x mai ciudat.. ma rog..

[•silviug]

Multumesc, dar nu e asta, eu ma gandeam la un x mai ciudat.. ma rog..

X-ul contine si cifra 0 pentru testu 1

[•Florian]

Eu nu pricep o chestie fundamentala:

Cod:

Este usor de observat ca cele doua siruri pot fi interpretate ca numere in baza N (numarul de elemente din setul X). 
Acest lucru se poate efectua sortand numerele din setul X si asociind 
fiecaruia o valoare intre 0 si N-1 (procedeul poarta numele de normalizare). 
....
Astfel, dupa ce am calculat reprezentarile sirurilor A si B in baza N, putem efectua o scadere pe numere mari  

Deci...eu am intelesc cam asa [ma voi referi la datele de intrare din exemplul problemei] :

*ordonez x => 1389
*asociez fiecaruia un nr din baza 4 (baza n) :0123 asadar am: 1-0 , 3-1, 8-2, 9-3 ;
*apoi....in loc sa folosesc nr din sirurile a si b, folosesc reprezentarea lor in baza n, deci sirul a[ 9, 3 ]    devine  A[ 3 1 ] iar sirul B[1 3 8] devine B[0 1 2 ].. si apoi trebuie sa scad B-A care evident nu da 8..kat ar trebui sa dea...
         Asa am intelesc eu..ku singuranta gresit... Insa, unde e greseala? 

[•peanutz]

Am o vaga banuiala ca trebuie sa transformi in baza 10 rezultatul

Vezi sa nu ajungi atunci cand faci operatii pe numere mari sa apara cifre mai mari ca si n-1, bafta!

Later edit: vezi ca mai tre scazut un 1 pe undeva si tine numerele invers.

[•Florian]

Iau 95 de puncte, cu WA pe testul 1. Ce ar putea sa fie? Nu vad nimic special daca x-ul contine si cifra 0...mie imi da pe testele mele...Si nu e nici din cauza ca A si B ar fi consecutive in ordine lexicografica...Care ar putea fi problema...?


[Edit] S-a rezolvat! Am luat 100. Greseala era k eu ma opream cand gaseam in a[] elemnte identice cu b[], numai k nu verificam si lungimea celor 2. 

[•taloibogdan]

Nici eu nu inteleg lucrul acela esential

[•Florian]

Pai ..din ce imi amintesc, eu nu`mi dadeam seama ca trebuie alese doar numerele care apartin bazei n. Deci scaderea aia, trebuie sa o simulezi k fiind in baza n, si nu in baza 10 (daca scazi pur si simplu A-B, e ca si cum ai scadea in baza 10). Sper ca ai inteles ce am spus. Mult succes! 

[•taloibogdan]

Dar ce-i cu scaderea unui 1?
Si cat ajung A si B dupa "normalizare" ?Nu 3,1 si 0,1,2 ?

[•Florian]

sirul A devine  A[ 3 1 ] iar sirul B[1 3 8] devine B[0 1 2 ]

[•SpiderMan]

Imi puteti da o indicatie cum sa fac transformarea in baza 10? Eu fac normalizarea si fac asa: B-(A+1), dar ... nu stiu cum sa transform optim in baza 10.