infoarena

Aici puteţi discuta despre problema Fold (http://infoarena.ro/problema/fold).

la problema asta...am WA pe toate...am un algoritm M*N^2...din cate am inteles eu...trebuie sa vad cate dreptunghiuri sunt pline de 1 si au dimensiunile cel putin 2...e bine?

Nu, trebuie sa numeri dreptunghiurile care au 1 in colturi.

doar...1 in colturi?...nu trebuie sa fie si pline de 1?

presepun ca se cere N*M...nu?

Nu ... merge in O(N^2 * M) dar cu o constanta multiplicativa mica.

Lucrez in Pascal si 65-70 era punctajul maxim pe care luasem.. O(N^2*M), am incercat si cu operatii pe biti, si fara si nu mai pot nici optimiza.. E posibil 100 cu Pascal?  :?

E posibil, doar ca mai trebuie sa te gandesti cum te ajuta operatiile pe biti.

imi dati si mie un point cum sa scot N^2 * M  :peacefingers: ca nu ma prind

Fixezi doua linii si vezi pentru fiecare coloana unde ai 1 pe ambele linii. Dar N^2*M nu iti aduce punctajul maxim, vezi cum te-ar puta ajuta operatiile pe biti sa scazi complexitatea.

oky ms :ok: intai sa fac in N^2 * M siu dupa aceea sa incerc sa optimizez ;)

Nu prea imi dau seama ce vrei sa spui prin "constanta multiplicativa mica"... Ai putea detalia, te rog? Am o rezolvare O(N^2* M), fara nicio o imunatatire si iau 65 de puncte.

O(N^2*M) cu constanta 1/32. Te flosesti de operatii pe biti.

De fapt e O(N^2*M/lg M) :P

pot sa aflu direct cati biti de 1 are x?
Ca dupa ce fac and intre doua linii nu trebuie sa numar bitii de 1 din fiecare element din rezultat  ?:sad:

Pai.. ai doua solutii ca sa afli bitii de 1 dintr`un numar.
1. Daca in program, trebuie sa afli bitii de 1, din foarte multe numere, poti face o precalculare in O(Nmax), apoi raspunzi in O(1) pt fiecare numar.
2. Daca in program, trebuie sa aflii bitii de 1, din foarte putine numere, poti face chestia asta in O(nr_de_biti_de_1). [Practic imparti la 2 numarul pe care il ai, si numeri de cate ori nr respectiv % 2 ==1).
 In ambele cazuri, e bine sa folosesti operatiile pe biti, ca sa micsorezi timpul de executie.
Apropo, problema poate fi rezolvata si O(N^2*M) cu parsarea citirii.  :D

Eu am facut n^2 (am fixat cate 2 linii) si am facut and intre ele (intr-un vector cu m/32 componente). De aici am numarat elementele 1 (cu operatii pe biti). Deci este n^2*m. Insa iau 75 -80 de puncte. Nu imi dau seama la ce te referi cu "parsarea citirii"

La 2 e O(log₂Numar) sau O(numar_total_de_biti) asa cum zici tu, nu O(nr_biti_de_1), pentru ca tu verifici si bitii care sunt pe 0 impartind la 2 si facand modulo 2 la fiecare pas.

Intr-adevar. My bad..


Parsarea citirii se refera la citirea intregului fisier intr`un char, iar apoi transformarea lui in ce ai tu nevoie [matrice int, probabil in cazul tau]. Oricum, asta e o metoda de bulaneala. :D Mai bine iti faci rezolvarea corecta.

Am zis mai inainte cum am rezolvat problema si iau 75-80 de puncte. Se poate obtine o complexitate mai buna ca a mea sau trebuie doar sa optimizez codul?

Foloseste tipul bool. O sa mearga mai rapid.

Se poate O(nr_biti_de_1) daca se elimina in mod repetat ultima cifra de 1 cu

Daca Nmax e foarte mare (sa zicem 2³²), poti sa precalculezi doar pentru o parte din valori (primele 2¹⁶). Apoi cand ai o intrebare pentru un numar il vei imparti in doua bucati: primii 16 biti ( x >> 16) si ultimii 16 biti (x & 65535), iar pentru bucatile astea ai precalculat numarul de biti.

Este o greseala in tabelul de la exemplu. In dreapta ar trebui sa fie fold.out nu fold.in

 ](*,) iau 95 pct cu 1 TLE.am parasat citirea + am folosit bool la matrice.ce as mai putea reduce? :-k

incearca si varianta in care comprimi fiecare linie in numere; asa nu vei avea m numere(de 0 si 1) ci vei m/x (x = numarul de biti din care formezi un numar)

Ce zici de timpii mei "In PASCAL!"  http://infoarena.ro/job_detail/736408    :D
Si nu-mi amintesc sa fi facut mare lucru,am impartit linia in numere de 16 biti + mi-am precalculat un vector in care tin cite cifre de 1 are in reprezentarea sa binara orice numar de 16 biti.
SPOR   :)

Imi da OK pana la testul 10, Incorect de la 11 pana la 19 si TLE pe 20 cu citirea parsata si liniile comprimate in numere. De ce merge pana la 10 si dupaia Incorect? Ce se poate schimba la un test mai mare?  :'(

Later edit:
Am reusit sa o fac. Citire parsata + SI pe bit este suficient, nu e nevoie de comprimarea liniilor in numere. Nu-mi iesea pentru ca nu citeam toate caracterele de pe linie pe testele mari, citeam 2000 in loc de 4000   :fool: