027 Loto

[•mastermage]

poti sa faci 90 de puncte si cu 6 for-uri

[•Dorin]

poti sa faci 90 de puncte si cu 6 for-uri

cum ai facut cu 6 foruri 90 p
ai parcurs siru de la sfarsit la inceput

[•Dorin]

mersi bogdan2412 pentru idee am facut shi asha dar din cate exemple am dat nici unul nu e gresit
este insa o diferenta cu sase foruri da alte numere dar suma este aceeasi
are vreo importanta ??

----------------------------------
cine poate sa imi dea un test asemanator cu testul unu sa vedem ce e gresit?
poate fac shi eu de 100

[•mastermage]

exact, il parcurgi de la sf la inceput pt ca il scutesti sa mai incarce variabila "n" in memorie.
daca sortezi siru' o sa primesti 95 puncte

[andreit1]

Eu a luat 100 cu un O(N^6). Am sortat vectorul si dupa aceea am verificat la fiecare pas sa se poate obtine suma cu numerele ramase

[•efer]

Se poate si O(N^3), iar implementand cu set din stl, implementarea iese in cateva randuri...
Dupa sortarea sumelor, pornesti de la fiecare capat (deci un indice este 0 si celalalt n-1) si, daca suma curenta (adica suma celor doua elemente unde ai pozitionati indicii in acel moment) e corecta, te opresti, daca e mai mica cresti indicele mic, iar daca e mai mare scazi indicele mare...

[nivan]

Mei oameni buni.....
  Eu am facut problema asta in doua moduri:
    1) Backtracking  ----------------> pe care primesc 20 puncte
    2) Backtracking  optimizat -----> pe care primesc 40 puncte
    3) O(n^3) -----------------------> pe care primesc 90 puncte shi TLE la penultimele doua teste

  Este ciudat cum O(n^6) poate lua acelasi punctaj cu O(n^3). Dar nu asta este problema ci daca puteti puteti sa-mi ziceti cate numere sunt la penultimul test ( Asa estimativ ~ ca sa vad cam ce ar mai trebui optimizat ca deja m-a scos din sarite aceasta problema   )

[nivan]

Shi cu O(n^6) tot 95 puncte iau !!!!!!      Cred ca punctajul asta imi e predestinat      
  Totusi poate sa-mi explice cel cu 100 la O(n^6) cum a facut astfel incat poate scot shi eu asa 100 puncte (Nu ca e mare diferenta de la 95 doar ca imi sta pe creier   ).

[•svalentin]

A mai rezolvat cineva problema asta dupa ce s-a schimbat calculatorul pe care era evaluatorul?!
Eu am rezolvat problema in N^3*logN; cu map din STL... si imi da TLE pe ultimile 3 teste.
(ma rog, si un WA pe primul.. )

de curiozitate: intre find din set si find din map e vre-o diferenta in termeni de complexitate?!

[•bogdan2412]

Am trimis din nou sursa cu care luam 100 si a intrat in timp fara probleme. 0.09 p testul cel mai mare...
Atat Set cat si Map sunt "Associative Container" si au ambele complexitate logaritmica la find() (daca am inteles bine eu).

[•svalentin]

ok, mersi.

da, asa e, au aceeasi complexitate, dar despre constanta se poate spune ceva..?
o sa experimentez si cu hash_map, am inteles ca merge mai repede pentru cautari dupa key (neajunsul este ca nu sunt sortate.. dar la aceasta problema nu ne trebuie asta)

[later edit] ... se pare ca hash_map nu e chiar in standardul de C++

[•hitmann]

imi poate da cineva cateva sugestii la aceasta problema ? eu n-am reusit decat 25 p cu backtracking si cu 6 for-uri tot 25 parca am luat...
anyway ce-i ala stl ?
cele n numere din fisierul de intrare sunt in ordine crescatoare ?
(offtopic) backtracking recursiv are vreun avantaj fata de backtracking iterativ ? eu din cate stiam e cam tot acolo si l-am lasat balta
Sarbatori Fericite

[•bogdan2412]

Daca citesti mai sus solutia e O(N ^ 3 log (N ^ 3)), folosind cautare binara... Ar trebui sa poti sa te prinzi cum o faci...  Despre STL exista un articol pe info.devnet.ro, dar ca sa-l folosesti ar fi bine sa cunosti bine limbajul C/C++.
Backtrackingul recursiv e mult mai scurt si mai simplu de implementat. Cel iterativ e putin mai rapid ca nu se fac apele recursive si nu se fac operatii pe stiva.

[•mocke]

cum se face problema aceasta in O(n^6)....parcurgand sirul de la capat e acelasi lucru cu a-l parcurge de la inceput...nu e nici o diferenta si tot iese din timp nu am idee cum s-au luat 95 de puncte sau chiar 100 folosindu-se complexitatea asta

[•filipb]

Se sorteaza sirul intai si solutia se gaseste mult mai repede, desi complexitatea teoretica ramane O(N^6).

[•Florian]

Am sortat sirul...l-am parcurs de la sfarsit spre inceput....(solutie O(n^6))..insa iau doar 40 de puncte...mi se pare imposibil sa se ajunga la 100 de puncte in felul asta...ciudat...

[•pauldb]

Atunci incearca sa rezolvi problema intr-o complexitate mai buna.

[•Florian]

Ai dreptate...voiam doar sa incerc faza cu O(n^6) k am citit pe forum k cik se pot lua 100 de puncte...ma kam indoiesc..

[•Darth_Niculus]

 Problema se poate rezolva f usor in O(N^3 * log (N^3)).... cum s-a scris si mai sus. Dar am implementat si varianta cu O(N^6)... de curiozitate si luasem 90-95 pct fara nici o optimizare speciala. Binenteles ca de atunci pan' acuma probabil s-au modernizat testele.
 Pe vremea cand a mers faza, nici nu era infoarena 2 sa nu mai vb de optimizarea testelor. 

[•nash]

 ok .. ma calca pe nervi .. acum nu imi merge testul 1 .. si la toate solutiile mai proste ( back .. si o(n^6) testul 1 .. merge .. .. nu vad cazul particular of .. frustrant  95p ...

[•marcelcodrea]

Din cate stiu , nu exista caz particular .... sigur ai gresit la implementare !
Gasesti aici o cautare binara implementata ca la carte , poate te ajuta :

http://infoarena.ro/Multe-smenuri-de-programare-in-CC-si-nu-numai

Sau poti sa alegi calea neortodoxa si pentru teste mici sa faci 0(n^6)....pentru teste mari O(N^3*log(N^3)) !

[•Darth_Niculus]

 Asta e o idee mai aiurea.... in regim de concurs nu stai sa implementezi 2 probleme in loc de 1 (mai alea cand una din ele e corecta). Nu exista cazuri particulare... sau cel putin nu existau.
 Vezi daca-ai facut cautarea binara bine.....

[•nash]

Cod:

ok=1;
	for(i=1;i<=nr && ok ;i++)
	{
		util=s-v[i].s;
		ok=1;
		a=1;
		b=nr;
		for(;a<b && ok;) {
			mij=(a+b)/2;
			if(v[mij].s==util) {
				fout<<v[i].i<<" "<<v[i].j<<" "<<v[i].k<<" "<<v[mij].i<<" "<<v[mij].j<<" "<<v[mij].k;
				ok=0;
			}
			if(v[mij].s>util) b=mij-1;
			if(v[mij].s<util) a=mij+1;
		}	
	}

	if(ok) fout<<-1;
	fout.close();

mie mi se pare destul de bine facuta cautarea asta binara ,sau .. nu e 

[•Darth_Niculus]

 Intradevar pare sa fie ok..... ce iti da pe testul 1.... WA?

[•nash]

Test     Timp executie     Memorie folosita     Mesaj    Punctaj/test
1   0ms   8kb   Wrong answer!   0
2   0ms   12kb   OK!   5
3   0ms   12kb   OK!   5
4   0ms   12kb   OK!   5
5   4ms   496kb   OK!   5
6   12ms   596kb   OK!   5
7   12ms   868kb   OK!   5
8   16ms   1084kb   OK!   5
9   20ms   1420kb   OK!   5
10   28ms   1784kb   OK!   5
11   36ms   2308kb   OK!   5
12   12ms   1092kb   OK!   5
13   112ms   4424kb   OK!   5
14   104ms   5364kb   OK!   5
15   172ms   6952kb   OK!   5
16   348ms   8664kb   OK!   5
17   344ms   11380kb   OK!   5
18   664ms   13728kb   OK!   5
19   376ms   15068kb   OK!   5
20   344ms   15728kb   OK!   5
Punctaj total   95