340 Take 5

[•DITzoneC]

Aici puteti discuta despre problema Take 5.

[•cosser]

De fapt, problema aceasta cum se rezolva?
backtracking iese din schema, nu?
 
---------
putin offtopic dar o includem si pe asta
ce-ar fi sa puneti problemele de la All you can code 2008 la sfarsitul listei, in arhiva de probleme
asa trebuie cautate pe la pagina 7
http://infoarena.ro/arhiva?display_entries=50&first_entry=300

iar cine se pricepe poate implementa o optiune de sortare dupa titlu, autor, numar, sursa, etc, etc. la tabelul cu probleme, asta daca nu s-a gandit nimeni pana acum


astept pe cineva sa vad ce pareri sunt despre rezolvarea acestei probleme.
cred ca e ceva chiar mai interesant decat ma gandesc...

[Edit] Nu mai posta de 2 ori consecutiv atata timp cat ai buton de edit

[•wefgef]

Din pacate nu putem sa schimbam ordinea problemelor in arhiva. Acestea apar cronologic.

Sortari, filtrari in arhiva avem in plan... Va trebui insa sa mai asteptati pentru asta deoarece suntem foarte ocupati.

[•ciuperca]

Poate merge un back asa mai optimatizat    daca nu baga ceva foruri pe acolo.

[•Mishu91]

Ce complexitate trebe, cu O(N^3) iau numa 50 

[•ciuperca]

Poti sa iei si 70 daca optimatizezi mult si poti sa incerci sa reduci spre N^2 

[•visanr]

Limita de timp cred ca este cam mica, iau maxim 70 80 de puncte, complexitatea teoretica e O(N ^ 3). Stiu ca e cam mare, dar 2 din cele 4 surse de 100 au timpi in jur de 3.2-3.6 sec.
E buna limita de timp.

[•soriyn]

Apropo...cum se rezolva problema asta de 100 de puncte ? Se poate O(n^2) ? Avand in vedere ca sunt asa putine scoruri de 100 chiar nu cred ca s-ar supara nimeni daca ar da cineva o solutie.

[•mika17]

Uitanduma pe leetcode, mi-am amintit iar de aceasta problema, cum ca de un an tot nu stiu sa scot mai bun de N^3 cu un hash, si eu sunt foarte curios cum se face aceasta problema de 100 de puncte
Am gasit un articol http://en.wikipedia.org/wiki/3SUM pe wikipedia care zice ca pentru cazul cu 3 numere nu se poate mai bine decat N^2, asa ca banuiesc ca pentru 5 numere marginea inferioara teoretica e N^3 . Se poate face de 100 cu N^3 si hash sau tre sa schimb total algoritmul ?

[•S7012MY]

Limita de timp probabil e buna. Cred ca merge n^3 fara hash. Hash-ul merge in O(1) amortizat, dar probabil din cauza memoriei la problema asta n-o sa prea mearga in O(1)

[•elfus]

Poate cineva care a luat 100 sa-mi spuna ce a optimizat? Ma chinui la problema asta de ceva vreme si nu mai am nicio idee cum sa o mai imbunatatesc 

[•Fayed]

Am facut O(n^3) cu hashuri si iau 65 de pct cu TLE si am incercat sa fac putin altfel si acum iau 25 de pct cu MME. Cum e posibil sa iau MME cand memoria folosita este aceeasi ? Chiar nu inteleg ce naiba se intampla 
Iata codul initial:

inline void solve(){
 
int S=0;
    for(register int i=1;i<=N-2;++i){
        for(register int j=i+1;j<=N-1;++j){
            for(register int k=j+1;k<=N;++k){
                    S = V+V[j]+V[k];
 
            if(C-S>0)
                Search(C-S);
            }
 
        }
 for(register int z=1;z<i;++z)
            Add(V+V[z]);
}
 
printf("%d",nr);
}

Si iata codul cu care iau MME:

inline void solve(){

int S=0;
    for(register int i=1;i<N;++i){
        for(register int j=i+1;j<=N;++j){

                    S = V+V[j];
                if(C-S>0)
                Search(C-S);
}

 for(register int z=1;z<i;++z)
    for(register int j=z+1;j<i;++j)
            Add(V+V[z]+V[j]);
}

printf("%d",nr);
}