Un subsir format din elemente consecutive ale sirului initial nu e o subsecventa?

In solutia oficiala scrie ca pentru fiecare buton apasat consideri intervale continue (stanga si dreapta), dar din problema se intelege ca la apasare butonul apasat nu se transforma; e o gaura in interval.
Deci un contraexemplu ar fi sirul aa cu puterea 1 pentru a.
aa
11
2 intervale [1;2] si [1;2] => solutia ar fi 1.
dar solutia e 2, poti apasa ambele butoane (fiecare il transforma pe celalalt).
Deci e solutia oficiala gresita sau problema incomplet formulata? In orice caz, nu prea e ok, ca doar e problema de ONI.

@laurion, SpiderMan
Stiu ideea cu resetarea super rapida cu setarea lungimii numarului la 0 (am si spus mai devreme asta).

La functiile acelea de operatie pe numere mari, presupui ca in numar, dincolo de digitii care indica numarul gasesti doar 0. Adica nu putea fi adaptata ca sa functioneze si cand restul digitilor nu-s buni? Ca pierzi mult timp cand egalezi un nr cu 0 sa stai sa faci toate cifrele 0 (in loc sa reglezi direct dimensiunea 0).

Dar am inteles ca abordarea asta complica implementarea operatiilor si de multe ori nu este necesara.
La adunare nu merge daca sunt cifre reziduale in fata, se presupune ca sunt 0. Asa ca nu inteleg de ce scaderea ar fi diferita? De ce o functie este implementata intr-un stil si cealalta in alt stil?

[ambele]

La scaderea a doua numere mari, ce rol are conditia (i <= B[0])? Oricum vectorii in care se retin numerele mari trebuie sa aiba aceeasi lungime declarata si sa aiba numai cifre de 0 in fata. Se observa foarte clar asta la adunare, unde i avanseaza pana cand se termina ambele numere (si restul), si folosirea directa a termenilor A[ i ] si B[ i ] implica automat existenta de 0 la inceputul (dreapta) numarului pana la sfarsit.
Astfel, la scadere, daca i > B[0], B[ i ] va fi oricum 0, deci conditia ((i <= B[0]) ? B[ i ] : 0) mi se pare inutila.

Super tare. Dar Craciun are dreptate: imaginea arata cam urat.

Ok, atunci poza dispare (mie nu mi se parea asa urata, dar daca asa e de parere lumea, schimbam). Poate ca era prea mare si trebuia mai mica ca un desen la inceput de propozitie (toate wiki-urile au asa ceva pentru tot felul de lucruri, inclusiv pe infoarena).

Ok. Ms.

Dar pe TopCoder e punctarea aia ciudata in care nici nu-ti dai seama daca ai rezolvat corect sau nu.
Sunt recomandari si de probleme de pe infoarena sau campion sau usaco sau alte site-uri care puncteaza sursele clasic?

De ce e windows-ul o problema la concursurile de programare?

http://www.youtube.com/watch?v=fzMhh8zhTiY&feature=plcp&context=C39fd4a3UPOEgsToPDskKgX1rn9vnNlTdnZGhF6I6M
http://www.youtube.com/watch?v=8zwP9ErgIWs&feature=plcp&context=C3b0676fUPOEgsToPDskI7r2ukEwYYqFmQAy65SU81
http://www.youtube.com/watch?v=jzq2O54LLIw&feature=plcp&context=C356b6beUPOEgsToPDskLI4XVGtWRS9m6Paaj97YMZ

Vre-un fan starcraft 2 pe-aici?

Poate bifati din nou auto-refresh monitor la evaluator.

Citeste solutia oficiala si ai sa vezi legatura.

ms

Eu am rezolvat-o presupunand ca e neorientat.

Da, se vede ca e neorientat din exemplu. Ar trebui specificat.

LE: Se pot mari restrictiile problemei un pic sa nu fie nevoie sa faci parsare si alte lucruri de genul asta?

Graful e orientat sau neorientat?

Ce greseala? 

Vre-un exemplu in care solutia nu are lungime k? Pt ca la o solutie ipotetica de lungime mai mare ca k i-ai taia elementele de la sfarsit sa ajunga de lungime k. Astfel ar avea prioritate in fata secventei initiale (are indicele de sfarsit mai mic), iar baza ei nu poate decat sa creasca in urma taierii, deci sa aiba o baza fie egala, fie chiar mai mare.

_______
Mai tarziu:
Da, am luat 100 considerandu-le doar pe cele de lungime k.
80 cu scanf, 100 cu stream-uri

Pentru n = 5 da

Cod:

36
000001000110010100111010110111110000

Tu cum ai reusit sa rezolvi problema fara sa trimiti sursa? Daca dau filtrare la monitor, nu apare nici o sursa, dar pe profilul tau apare problema drept rezolvata. 

Auzi iti bati joc de forumul asta? Nu vezi ca postul ala e deja de mult timp ? Nu apare sursa fiindca a fost pe InfoArena 1 si nu s-au mai pastrat sursele  .

Nu imi bat joc de forum-ul asta. Nu am vazut scris ca nu se pastreaza sursele deci m-am mirat. Oricum, e rau daca nu se pastreaza pentru ca eu credeam ca le poti pastra pe infoarena.
Si ce daca e de mult timp? E un motiv pentru care nu e inchis.

Pentru n = 5 da

Cod:

36
000001000110010100111010110111110000

Tu cum ai reusit sa rezolvi problema fara sa trimiti sursa? Daca dau filtrare la monitor, nu apare nici o sursa, dar pe profilul tau apare problema drept rezolvata. 

eu iau 40 cu arbori de intervale
si am implementat la fel cum am implementat la "arbori de intervale" din arhiva educationala, unde am luat 100.

Pe TopCoder scrie ca pot fi folosite oricare 2 pozitii ale aparitiilor nodurillor din query in reprezentarea Euler a arborelui.
Eu cred ca ar trebui specificat ca se pot lua oricare aparitii, dar pentru simplitate se pot lua primele.
Asa ar parea ca primele au vreo proprietate speciala.

ideea la algoritmu' asta este ca merge pe grafuri cu costuri negative, spre deosebire de dijkstra

ms

ideea la algoritmul acesta e ca e rapid de implementat decat dijkstra, nu?

ca de n ori dijkstra cu heap-uri ar avea complexitate O(N^2 * logM) in loc de O(N^3)...

sau mai are si alte avantaje?

Foarte bine prezentat articolul, dar e cam stransa memoria dupa parerea mea.

[;]

"Daca acesta este intr-una din camerele gazate moare pe loc; daca nu, camera nu pateste nimic si sobolanul poate circula prin ea imediat dupa detonarea bombei."

Cred ca e un pic mai clar asa.

Mai mariti limitele de timp un pic.
50 cu scanf, 100 cu fstream.

Poti sa adaugi in problema ca in fiecare camera exista cate un aparat care-l vindeca de efectele radiatiilor, deci conteaza doar cat se expune intr-un singur tunel (sa nu i se faca rau), dar nu conteaza suma expunerilor pe tot drumul.