Puteti sa mariti limita de timp? Se pot lua maxim 80 de puncte, cu parsare. Multumesc anticipat!

Incearca cu back simplu, nu pe biti. 

Salut!
Am rezolvat problema astfel :
 - am determinat puterea la care apare P in N! in O ( log _P N ) , folosind o formula;
 - am gasit , daca mai este cazul , N! % P ignorand toti factorii lui P din N! , in O (log _P N * log ₂ P ).
  Primul logaritm vine de la descompunerea lui N! in factoriale mai mici care se repeta din P in P , iar al doilea de la ridicare la putere. Am incercat si ridicarea la putere pe biti insa nu reusesc sa scap de TLE pe 11 teste. Operatiile necesare le fac pe long long , iar operatia rest nu imi dau seama cum s-o inlocuiesc cu scadere.

Ce as mai putea optimiza pentru ca sursa sa intre in timp? ( am citit solutia oficiala si are aceasi complexitate , l-am rugat pe Popa Mihai sa trimita sursa lui care lua 100 si acum primeste 70).
Multumesc anticipat!

Cam stransa limita de timp. Cu Hierholzer iau TLE pe 4 teste. Am renuntat la cautarea secventiala din stergere folosind hashing dar merge mai lent iar parsarea scade din timp , dar nu suficient. Complexitatea algoritmului este O(m). Ce as mai putea optimiza? Multumesc anticipat!

Se mai poate lua 100 de puncte? Eu folosesc algoritmul pentru ciclu eulerian , iterativ, identic cu cel care ia 100 in arhiva educatonala si am TLE pe testul 8. Am implementat liste simplu inlantuite manual si TLE - ul ramane.

Am luat pana la urma 100 de puncte inlocuind doar listele care nu erau necesare cu vectori alocati static.

Vad ca ai si parsat citirea si tot ai un TLE. Asta e problema, complexitatea nu este cea optima, de aceea trebuie dinamica cu memoizare.

Tu iei incorect pentru ca abordarea ta este gresita. In primul rand trebuie sa faci un fel de Bellman-Ford adica in conditia asta :

Cod:

if( ii>=1 && jj>=1 && ii<=n && jj<=n &&  a[i][j] < a[ii][jj] ) {
	d[ii][jj]=d[i][j]+1;
	Q.push(mp(ii,jj));
}

Mai trebuie sa adaugi d[ ii ] [ jj ] < d[ i ] [ j ] + 1 si cred ca merge.In al doilea rand nu inteleg de ce introduci in coada casutele care au toti vecinii mai mici.Pentru exemplul tau respunsul corect este :

Cod:

5
1 3
1 4
2 4
3 4
4 4

Deci incepe in 1,3 pe care tu nu il introduci in coada. Insa oricum vei lua TLE pe cateva teste. Eu am rezolvat folosind dinamica cu memoizare. Daca nu te prinzi da-mi un PM.

Poti face dinamica folosind doar ultima linie. Eu asa am scapat de TLE.

Uite aici un articol despre numere complexe : http://bacmd.com/attachments/186_numere_complexe.pdf .
Este destul de bun din cate am citit eu. Cat despre a doua intrebare... Stii ca tg a = m unde m=unghiul dintre axa OX si dreapta. Aflii unghiul a, si aduni/ scazi unghiul de rotatie, deci stii noua panta (trebuie sa tratezi cazurile particulare = atunci cand nu exista tangenta, si sa vezi in ce cadran(e) se afla segmentul.

Stii panta dreptrei (si neaparat un punct A care apartine dreptei, eventual mijlocul segmentului). Ai formula care spune ca daca doua drepte sunt perpendiculare atunci produsul pantelor este -1, deci afli panta noii drepte. Cunosti panta si un punct <=> ecuatia dreptei este d : y-yA=md(x-xA) .
Insa abordarea este greoaie si se poate pierde precizie . Daca ai notiuni de baza despre numere complexe , stii condititia ca un triunghi sa fie echilateral si gradul de dificultate al problemei se reduce foarte mult.

Pai in loc sa citesti numar cu numar citesti blocuri de caractere folosind functia fread.
Mai multe detalii aici : http://infoarena.ro/parsarea-numerelor

Sursa oficiala ia 60 de puncte cu TLE pe ultimul test. Cred ca ar trebui marita putin limita de timp (pentru 100 de puncte trebuie parsata citirea).

Pentru ca tipul int lucreaza pe 32 de biti, iar long long pe 64. Astfel ca la fiecare operatie de inmultire, adunare , atribuire , etc. , procesorul are mai multi biti de prelucrat. Deci long long este mult mai incet decat int ,dar foarte folositor in unele cazuri.

Multumesc amandurora pentru indicatii. O sa incerc sa vad ce iese.

PS : Am citit solutia oficiala pana la urma si am gasit 3 optimizari propuse : pe primele 2 le am deja, iar a treia : in cazul cautarii binare, intervalul initial de cautare nu trebuie sa fie [1,N], ci un interval mai restrans (de exemplu, [10 la (X/P)-1, 10 la (X/P)+1]), unde X este numarul de cifre ale numarului N dat. Nu imi dau seama de ce afirmatia este adevarata (  daca am baza 10000 atunci trebuie 10000 la puterile respective ) . Astfel scap de TLE dar iau incorect.

Am implementat operatiile pe numere mari folosind baza 10000 si am un TLE pe al doilea test. Cu baza 1000000000 am din nou TLE pe testul al doilea. Folosesc cautarea binara. Am incercat si parsarea citirii cu fread dar tot TLE. Mentionez ca folosesc classes si aceleasi operatii pe numere mari ca la problema http://infoarena.ro/problema/numere2 unde am luat 100.
Trebuie cumva marita limita de timp sau mai trebuie sa fac ceva optimizari ( desi nu mai am nici o idee )?

Da, intradevar nu trebuie long long, insa este destul de ciudat ce se intampla. Nu trebuie neaparat sa folosesti AIT , merge si in complexitate patratica foarte repede deoarece n <= 4000. Incearca asa si vedem pa urma ce se intampla.

La problema "Potrivire" in sectiunea "Scorul tau" imi apare 20 de puncte desi am obtinut 100.

Incearca sa pui inline la functii iar apoi scapa de parametrii aceeia multi de la functii( de ultimii 2 ), ei se salveaza pe stiva pentru nimic. Tu oricum nu ii mai folosesti.

Am gasit ceva interesant despre algoritmi si probleme de geometrie computationala aici :
http://campion.edu.ro/arhiva/index.php?page=paper&action=view&id=41
Sper sa fie de folos.

Multumesc. Am fost neatent, in loc de secventa m-am gandit la un caracter.

In enuntul problemei steluta este inlocuita de ce caracter?

Pentru testul:

Cod:

8 5
zxabedgh
*****

trebuie sa afiseze 1 1? Iar pentru

Cod:

 8 5
zxabedgh
**a**

1 4?

Nu, nu vei primi niciun punct.http://infoarena.ro/documentatie/evaluator
Din cate am vazut eu tu nu primesti TLE ci SIGSEGV. Uite aici ( http://infoarena.ro/documentatie/borderoul-de-evaluare ) ce inseamna.

Eu inca mai iau 100 de puncte cu aceeasi sursa. Incercati sa optimizati programul, desi eu nu am cine stie ce optimizari.

Exista un bug la problema Plus2. Daca postez un comentariu este afisat la problema Amedie si cred ca exista o eroare in evaluator , iau 20 de puncte cu toate ca imi merg toate testele oficiale.