232 Fold

[ditzone]

Aici puteţi discuta despre problema Fold.

[•crus]

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?

[•astronomy]

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

[•crus]

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

[•cos_min]

Cei patru tarusi pot fi infipti in pamant numai in parcele nivelate.

[•crus]

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

[•Cosmin]

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

[•fogab]

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? 

[•Cosmin]

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

[•Robytzza]

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

[•astronomy]

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.

[•Robytzza]

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

[•Florian]

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

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.

[•wefgef]

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

[•domino]

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

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

[•free_coder]

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  ?

[•Florian]

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. 

[•free_coder]

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"

[•Dastas]

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. 

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.

[•Florian]

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. 

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..

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"

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. Mai bine iti faci rezolvarea corecta.

[•free_coder]

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?

[•cos_min]

Foloseste tipul bool. O sa mearga mai rapid.

[•stef2n]

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.

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

Cod:

N = N & (N-1)

[•DITzoneC]

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.

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.

[•shnako]

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