695 Suma3

[•astronomy]

Aici puteţi discuta despre problema Suma3.

[•gabitzish1]

Nu reusesc sa trec de 90. Am TLE pe testul 9, iar celelalte imi intra in maxim 72ms.
Am sortat numerele si intru in backtracking in ordine descrescatoare a valorilor. Nu mai continua back'ul daca am ajuns la o suma > decat minimul gasit deja. (iese din timp pe testul 9 si daca verific doar un punct de plecare).
Alte sugestii? am vazut ca nimeni nu a luat 100 pana acum (exceptie astronomy).

[•fireatmyself]

tine o matrice P[i,j] = i*j. in loc sa aduni k*A[i,j] in back, aduni P[k, A[i,j] ]. k poate sa fie maxim pana la 32, deci ar trebui sa intre. de obicei folosesc astfel de optimizari cand imi iese din timp cu foarte putin. sper sa te ajute.

[•astronomy]

E ciudat fiindca testul 9 ruleaza cu sursa oficiala mai putin decat testul 10 si tie am vazut ca iti merge foarte rapid testul 10. Poate testul 9 are o structura in asa fel incat optimizarile tale nu sunt suficiente.

[•gabitzish1]

Mi se pare destul de mare diferenta de timp dintre testul 9 si celelalte, dupa cum am mai spus, testul 9 imi iese din timp chiar daca pornesc back'ul o singura data, pe cand primele 8 intra daca pornesc din toate punctele diferite de 0.

Bogdan, am incercat cu matricea, si am aceleasi rezultate.

[•fireatmyself]

fa-ti generator de teste si apoi .bat care sa ruleze generatorul si sursa ta, de 1000 de ori. trebuie sa nimeresti un test pe care sa-ti iasa din timp

[•anna_bozianu]

Intradevar urat testul asta 9. Eu am reusit sa-l pacalesc aplicand back plecand numai din pozitia de valoare maxima pentru acest test in timp ce pe celelalte am aplicat pana la jumatate din pozitii plecand in ordinea descrescatoare valorii a pozitiilor. Nu-i frumos da-i sanatos  . Ma intreb ce as fi facut in conditii reale de concurs. 

[•xtreme]

As fi foarte recunoscator daka m-ar putea ajuta cineva la aceasta problema...Ideea mea e urmatoarea:am luat o matrice care contine v[ i ][ 0 ]=elem,v[ i ][ 1 ]=linia,v[ i ][ 2 ]=coloana pe care se afla elementul.Cu un backtracking iterativ m-am gandit sa generez toate permutarile,procedura de validare continand pe langa conditia generarii permutarilor si conditiile de vecinatate a elementelor si suma actuala in procedura valid sa nu depaseasca suma minima...nu sunt sigur daka suma de inceput minima e buna... ...as vrea sa stiu makar daka is pe drumul bun?
codul sursa e in suma3.txt

Editat de admin: Pe viitor pune spatii cand ai constructii de genul A[ i ], pentru ca altfel ti se interpreteaza sectiunea [ i ] ca tag din html pentru scris italic.

[•anna_bozianu]

Ideea e corecta. O imbunatatire ar fi sa sortezi datele descrescator dupa v[][0] si astfel se va atinge mai repede solutia. Suma minima eu am initializat-o cu 2000000000. O alta imbunatatire ar fi sa stabilesti din start listele  vecinilor pt ca problema e de fapt una de grafuri in care fiecare nod are grad cel mult 8. Bafta.

[•xtreme]

Ideea e corecta. O imbunatatire ar fi sa sortezi datele descrescator dupa v[][0] si astfel se va atinge mai repede solutia. Suma minima eu am initializat-o cu 2000000000. O alta imbunatatire ar fi sa stabilesti din start listele  vecinilor pt ca problema e de fapt una de grafuri in care fiecare nod are grad cel mult 8. Bafta.

Iti multumesc pentru TIP-uri dar din pakate nu stiu nimic de grafuri...is in clasa IX,doar auzisem de asa ceva. 

[•sima_cotizo]

Nu te alarma, nu am citit problema dar sunt sigur ca nu e chiar de grafuri (am vazut ca a fost propusa la a 9-a)... incearca doar atunci cand faci back sa pui pe pozitii vecine elemente care chiar pot fi vecine, adica sa tii o lista de vecini posibili ai unui numar si in back sa alaturi doar ceva ce se poate alatura... asta elimina multe din solutiile posibile pe care tu le testezi

[•xtreme]

Imi poate da cineva atasamentele de la aceasta problema?

[•wefgef]

Pentru problemele din arhiva testele nu sunt facute publice .

[•xtreme]

Are cineva evaluatorul original de la Grigore Moisil pentru problema aceasta?...Acolo s-a dat limita de timp 1,5 secunde.Inca o intrebare:s-ar putea mari makar limita de timp la 0,45 sec ?

[zombie_tester_2]

numerele diferite de 0 sunt distincte?

[zombie_tester_2]

salut...iau TLE pe ultimele 2 teste.....
nu stiu ce optimizari sa mai fac
sortez numerele in ordine descrescatoare, retin si pozitia elementelor ca sa pot face verificare in back in O(1) si inca un vector fol[ i ] in care retin 1 daca elementul de pe pozitia i din sirul sortat a fost folosit si 0 in caz contrar, dupa care intru in back cu poz 1. Daca dau de un sir care are suma actuala mai mare decat minimul gasit deja dau un return. Ce optimizari as mai putea face? vreo idee?

[•danalex97]

Iau doar 80p cu DF si tot 80 cu un bkt. Voi cum ati facut sa luati 100 ?   Multumesc anticipat.

[•SpiderMan]

E ok limita de timp la aceasta problema ? Se poate uita cineva cu o sursa de 100 ?
[LE] Am rezolvat, am optimizat-o de o luat-o ameteala, am scos 12 ms pe testul ala naspa  .

[•gapdan]

Banuiesc ca nu se face cu back... Sau cel putin nu cu back din fiecare nod    Eu am incercat sa transform matricea intr-un graf si sa fac un DFS din fiecare nod <=> fill... a facut cineva BFS?