Multumesc... o sa incerc sa vad daca-mi iese ceva..

Trebuie sa folosesti un arbore de intervale pentru a raspunde in O(logN) fiecarei intrebari . In numarul de ianuarie 2006 Ginfo gasesti doua metode de rezolvare a problemei .

Ai putea da un link catre articol, ca nu-l gasesc nicaieri. Am gasit unul despre arbori de intervale si aplicatii in geometrie (am inteles ce e un astfel de arbore din el), dar sincer nu stiu cum l-as putea aplica in problema... iar solutia de la oni nu prea e explicata, si as vrea si eu sa inteleg cum se poate face, daca poate cineva explica sau da un link..

Am vazut ce se retine in fiecare nod in solutia de la maxq, dar in rest nu prea e explicat...

Multumesc.

Nu e buna forma poloneza, citeste mai cu atentie algoritmul. Trebuie sa-ti dea 178 66 -1 234 -1 89 -2 54 -1 13 -2 22 -2 67 -1, unde -1 = m, -2 = M. Operatorii au aceeasi prioritate.

Desi cel mai elegant e cu notatie poloneza Si trebuie sa intre in timp.

Pai descrie exact cum faci. Transformarea o faci nerecursiv, iar evaluarea la fel. Pentru evaluare iti mai iei o stiva, parcurgi vectorul in care ti-ai format sirul in notatie poloneza, iar in momentul in care pui un operator in acea stiva, vei avea operanzii deja adaugati, deci ii scoti din stiva, calculezi, adaugi rezultatul inapoi in stiva, iar la sfarsit stiva va contine o singura valoare: rezultatul care te intereseaza.

Ideea asta e, cu asta am luat 100... poate te complici pe undeva, da si tu mai multe detalii si incerc sa te ajut.

Ti-am dat un link unde practic ai algoritmul de rezolvare... ai incercat sa-l implementezi?

Poate e gresita formula - in prelucrarea datelor (eu unul) nu vad nicio greseala. Parca eu luam 80-90 pana si cu float... deci putin probabil sa iei numai 20 din cauza preciziei.

cel mai bine e sa folosesti tipul long double, si sa citesti/afisezi cu %Lf

Multumesc! am luat pana la urma 100.

Imi spuneti va rog daca pentru exemplul:

abcabcaa
acbacba

Matricea Nr arata in felul urmator:

Cod:

1 1 1 1 1 1 1
1 1 1 0 0 1 0
1 1 0 0 1 0 0
1 0 0 2 0 0 1
1 0 1 0 0 3 0
1 1 0 0 3 0 0
1 0 0 1 0 0 6
1 0 0 1 0 0 7

Multumesc.

Poate te ajuta http://en.wikipedia.org/wiki/Shunting_yard_algorithm. Poti transforma sirul in notatie poloneza, care se evalueaza foarte usor si intra in timp.

Nu sunt chiar asa de slabe testele .

Ideea nu e buna, formuleaza pe foaie matematic problema si o sa te prinzi .

Initial si programul meu afisa 0 3 1. Dar, daca ne luam dupa enunt, un raspuns care contine 0 nu este corect. Desi ambele variante iau 100 de puncte... ar trebui modificate ori niste teste ori enuntul.

Dar, din pacate, iei 100 cu un program care nu trateaza cazul cand numerele sunt nule .

Pai uite, pt 3 1 4 de exemplu tu ai:

primul termen: 1-3 = -2 , 3-(-2) = 5

5, -2, -1

Care nu e corect.

Pentru primul exemplu nu cred ca-ti da bine cum zici tu:
3
4 5 3

Daca primul element e p = 5-4 = 1 tu afisezi urmatorul sir, daca te-am inteles eu bine:
1 4 2

Gandeste-te cum poti formula problema matematic.

Dar... ma ajuta asta cu ceva cand rotesc matricea? Ca atunci tot nu pot scapa de spargerea liniei de cache...

Edit: Am luat 100 folosind sort din STL. Ultimul test intra in ~250 ms... totusi, daca binevoieste cineva sa ma ajute cu o solutie de 100 fara stl, eventual pe biti, i-as fi recunoscator .

Intr-adevar, daca liniile sunt mai putine decat coloanele, matricea o citesc gata rotita (accesez elementele ceva de genul a[n-j+1][ i ], cu for-uri i=1..m, j =1..n), poate fi de la asta? O sa incerc sa scap de asta facand back-ul direct pe minimul dintre linii si coloane atunci...

Asemanator am facut... adica, daca linii < coloane, am citit matricea inversata, am interschimbat nr_linii cu nr_coloane si r cu c, iar apoi am facut back pe coloane (care sunt minime...). Inainte sa fac asta luam vreo 60... asa tle pe ultimul test :/.

Eu iau 90, TLE pe ultimul test. A luat cineva 100 generand combinarile cu backtracking? La flip a intrat lejer asa... aici se pare ca nu vrea...

Pe biti nu prea ma prind cum se face. Pur si simplu ma folosesc de bitii numerelor din intervalul [0, 2^N], eliminand coloanele a caror biti corespunzatori sunt 1 (Daca acesti biti de 1 sunt C in total)? Nu prea inteleg ce vrea sa spuna Adrian Diaconu prin "si nu pui 0 daca numarul de biti ramasi necompletati nu iti ajunge pentru a pune in total C de 1.". Eu ma gandeam sa parcurg numerele din [0, 2^N], iar daca am C biti de 1, elimin acele coloane...

Putin ajutor va rog

da, faci normal, vezi de cate ori se imparte la 2 cu un while. atata doar ca in loc de impartire la 2 si modulo 2, faci operatiile pe biti pe care ti le-am spus.

64 & 1 == 0, 64 >> 1 = 32 etc..

probabil testezi daca n % 2 == 0 si apoi faci n /= 2

incearca sa faci operatiile astea pe biti: if ( (n & 1) == 0 ) pt modulo si n = (n >> 1) pt impartire

cel putin la mine asta a fost problema...

Inca o sugestie: foloseste compilatorul GCC. Cu asta se evalueaza si pe site, si nu degeaba, este mult superior borland-ului. Pentru IDE ai mai multe variante: rhide (interfata asemanatoare cu cea din borland), DevCPP, Code::Blocks...

Ai incercat sa-i declari dinamic, cu new? de exemplu, in loc de int a[NMAX], sa ai int *a = new int[NMAX];

Desi mie imi merge daca nu-i declar dinamic... esti sigur ca nu faci nimic altceva?

Este memorie, mie mi-a intrat lejer cu 3 vectori de 1 milion. De la altceva trebuie sa fie...