134 Balans

[ditzone]

Aici puteţi discuta despre problema Balans.

[u-92]

la problema asta nu iau mai mult de 35 puncte -> TLE !

pentru a afla o secventa de suma maxima de lungime intre L si U fac asa:
fixez o pozitie (i) si caut cea mai mica suma de la 1 la j, cu j < i (bineinteles j nu e neaparat mai mare ca 1 am restrictie suplimentare deoarece lg <= U)
si acum fac o scadere si aflu suma.. bineinteles folosesc acea structura de date, scot din coada cand nu-mi mai convin pozitiile, si bag in coada un element in locul lui corespunzator.. (si tratez si circularitatea). nu am dat prea multe detalii, dar sper ca ati inteles ce am vrut sa zic.

aveti vreo idee ce optimizari ar trebui sa fac pentru a lua 100?

[•gogu]

"Optimizarea" pe care am facut-o eu a fost de fapt un brute-force in O(N^2*M^2).

Am luat toate submatricele cu dimensiuni intre R*C si N*M ale matricii marite si vad care are media aritmetica maxima.Suma intr-o submatrice se face destul de usor in O(1), cu niste precalculari.Trebuie sa ai grija doar sa trunchiezi rezultatul, nu sa il rotunjesti.
Mai trebuie sa faci cateva mici imbunatatiri, de exemplu sa nu iei submatrici care nu au coltul stanga sus in matricea initiala de NxM, dar e mai simplu si parca mai rapid decat daca faci cu deque, ca in solutia oficiala.

[u-92]

am scapat acum de TLE, analizam prea multe pozitii.. dar acum iau WA pe mai multe teste si banuiesc ca din cauza preciziei.. ce pot sa fac mai mult de atat:

inmultesc toata matricea cu 10000, caut binar intre 1 si 2^30 rezultatul si afisez printf("%d.%03d\n", rez / 10000, (rez / 10) % 1000);
si cautarea binara e asa:

Cod:

while(dr - st > 1)
{
   if(conditie()) st = m;
   altfel dr = m;
}
rez = st;

[•fireatmyself]

incearca sa afisezi numerele reale cu ajutorulu functiei floor() (vezi problema Insula). s-ar putea sa spun prostii deoarece nu am rezolvat problema, dar daca tot ai intrebat de precizie ...  

[•Adriana_S]

sau poti sa incerci printf("%0.3f", variabila) pentru numere reale.

[u-92]

eu am cautat rezultatul inmultit cu 10000 si am luat WA, e putin probabil ca daca il caut pur si simplu fara sa inmultesc cu nimic si sa lucrez pe reale sa-mi mearga..

so, pt cei care au rezolvat problema de 100, cum ati facut cautarea asta binara? implementarea la determinarea secventei de suma maxima sigur nu e gresita, am folosit aceiasi idee ca la secv3.

[•bogdan2412]

Nu cred ca a luat cineva WA pentru erori de precizie... Daca inmultesti totul cu 1000 (sau 10000 daca vrei tu) nu de aici e problema.  Cauta greseala altundeva... fa de ex un test cu o matrice 50 x 50 si cu R si C 50 si 50 sa vezi daca iti da bine.... sau da N = M = R = C = 150 si toate elementele 100000 sau un test in care toate elementele cu exceptia unuia sunt 0.
La cautarea binara solutia trebuie sa o cauti pana la 100000 * 10000, deci in jur de 2 ^ 30.
Good luck

[•filipb]

Totusi pot aparea erori la afisare. La secv3 eu faceam afisarea asa ( Best era rezultatul optim inmultit cu 100):

Cod:

fprintf(fout, "%d.%d\n", Best/100, Best%100)

Si de exemplu pentru rezultate de forma 109 imi dadea 1.9, in loc de 1.09.

[•filipb]

Tot nu reusesc sa trec primele 10 teste pt. k am TLE...

"Optimizarea" pe care am facut-o eu a fost de fapt un brute-force in O(N^2*M^2).

? Am facut asa si am luat TLE pe 13 teste...  :cry:

Am incercat si cu solutia oficiala, imi cad primele 10 teste. Caut binar intre minimul si maximul din matrice. Ce optimizari mai pot sa fac? Dequeul l-am facut asa:

for (i = c+1; i < 2 * n; i++)
{
    while (prim <= ultim && st[prim].poz < i-n)               prim++;
    while (ultim >= prim && st[ultim].VAL > SUM[i-c])     ultim--;
    st[++ultim].poz = i-c; st[ultim].VAL = SUM[i-c];

     if (SUM - st[prim].VAL >= 0)
   return 1;

}

Ce as putea sa fac sa scap de TLE?  

[•domino]

Incearca sa scapi de struct-uri.

[u-92]

poate analizezi prea multe pozitii.. daca prima linie o alegi doar de la 1 la N nustiu de ce iti iese din timp (eu initial alegeam prima linie de la 1 la 2*N si luam TLE)

p.s: oricum, eu tot nu mi-am dat seama de ce iau WA.. si am motive sa cred ca e de la cautarea binara.. la secv3 am incercat mai multe tipuri de cautari binare, unele luau WA (de exemplu intr-o varianta cresteam doar st, in alta cresteam st si micsoram dr)

[•filipb]

Am scapat de deque si merge acum ( constanta de la deque era cam maricica - 2) Adica pentru ca SUM - SUM[j] sa fie maxim trebuia SUM[j] minim, cu i-C >= j >= i-N... Pentru testele mari am inlaturat conditia j >= i-N si fac pur si simplu cu minimul in primele x printr-o simpla parcurgere.. Pt. testele mici unde exista sansa sa gresesc am lasat deque... Si luasi necinstit 100...  

Am incercat sa scot struct-urile... Tot nu vrea... Pe primele 10 TLE...

[•cyron]

ba nene nu mai stiu ce sa fac :cry:
miam facut brute force si intre sursa si brute force da diferentza de 0.1-2
dar dreptunghiurile pentru care afla solutia coincid...cum pot sa fac sa scap de erori de precizie  

[u-92]

nustiu, da` daca iti dai seama cum sa-mi spui si mie (ma repet: am 11 WA`uri si nustiu cum sa mai fac cautarea aia binara  

[ditzone]

Dupa cum se mentioneaza si in solutia oficiala se poate lucra doar cu numere intregi inmultind totul cu 1000. Astfel se va obtine si un timp de execuie mai bun si se evita erorile de precizie...

[•cyron]

am sursa si cu intregi tot la fel da cu diferentza intre 0.1 si 2 si acelasi dreptunghi...

[•wefgef]

timpii aia de sub 0.1 sunt cu brute force, nu?

[•gogu]

Daca te referi la timpii mei, e un brute force cam ciudat cu destule submatrici neverificate. Nu stiu daca ar merge pe orice test dar vad ca merge pe testele lor.

[•tzipleatud]

Cred ca limita de timp e prea stransa la problema asta. Nu a mai luat nimeni 100 de anul trecut, cu nicio solutie. Cred ca ar trebui verificata, si marita putin limita.

[•savim]

Limita de timp era intr-adevar prea stransa, multumim pentru observatie.

L.E.: Intrucat au fost putine surse trimise cu noua limita de timp mi-am permis sa le reevaluez pe toate...vad ca au fost cativa care au luat 100 .

[•claudiumihail]

Problema asta ar trebui data ca un exemplu graitor pentru articolul asta:

https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920

Un brute cu 2 optimziari interesante scoate timpi semnificativ mai mici decat multe implementari ale solutiei oficiale:

1)

Asta (good):

Cod:

if (sum > flMaxBalans * r * c)
{
    flMaxBalans = (double)sum / (r*c);
}

versus asta (bad):

Cod:

flMaxBalans = max(flMaxBalans, (double)sum / (r*c));

Mi s-a injumatatit timpul de executie cu "optimizarea" asta.

2) Mai putin spectaculoas, a fost sa ma joc cu indicii buclelor. In final mi-a mai scazut timpul de executie pe cel mai greu test cu inca vreo 500ms.

Destul de interesant. Poate ajuta pe cineva...

Claudiu