Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: 232 Fold  (Citit de 9950 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
ditzone
Vizitator
« : Aprilie 09, 2006, 14:27:09 »

Aici puteţi discuta despre problema Fold.
Memorat
crus
Strain
*

Karma: 3
Deconectat Deconectat

Mesaje: 44



Vezi Profilul
« Răspunde #1 : Martie 15, 2007, 19:53:32 »

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?
Memorat
astronomy
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #2 : Martie 15, 2007, 21:19:10 »

Nu, trebuie sa numeri dreptunghiurile care au 1 in colturi.
Memorat
crus
Strain
*

Karma: 3
Deconectat Deconectat

Mesaje: 44



Vezi Profilul
« Răspunde #3 : Martie 15, 2007, 21:43:29 »

doar...1 in colturi?...nu trebuie sa fie si pline de 1?
Memorat
cos_min
Nu mai tace
*****

Karma: 48
Deconectat Deconectat

Mesaje: 493


live


Vezi Profilul
« Răspunde #4 : Martie 15, 2007, 22:25:37 »

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

vid...
crus
Strain
*

Karma: 3
Deconectat Deconectat

Mesaje: 44



Vezi Profilul
« Răspunde #5 : Martie 17, 2007, 00:06:57 »

presepun ca se cere N*M...nu?
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #6 : Martie 17, 2007, 02:23:12 »

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


Karma: 0
Deconectat Deconectat

Mesaje: 14



Vezi Profilul
« Răspunde #7 : Martie 18, 2007, 21:39:29 »

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?  Confused
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #8 : Martie 19, 2007, 19:34:08 »

E posibil, doar ca mai trebuie sa te gandesti cum te ajuta operatiile pe biti.
Memorat
Robytzza
De-al casei
***

Karma: -49
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #9 : Ianuarie 09, 2008, 14:21:41 »

imi dati si mie un point cum sa scot N^2 * M  peacefingers ca nu ma prind
Memorat
astronomy
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #10 : Ianuarie 09, 2008, 14:24:03 »

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.
Memorat
Robytzza
De-al casei
***

Karma: -49
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #11 : Ianuarie 09, 2008, 14:26:56 »

oky ms Ok intai sa fac in N^2 * M siu dupa aceea sa incerc sa optimizez Wink
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #12 : Ianuarie 09, 2008, 19:17:27 »

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.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #13 : Ianuarie 09, 2008, 19:23:09 »

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

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #14 : Ianuarie 09, 2008, 19:43:03 »

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

De fapt e O(N^2*M/lg M) Tongue
Memorat
free_coder
Strain


Karma: -1
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #15 : Februarie 09, 2008, 13:40:41 »

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
« Ultima modificare: Februarie 09, 2008, 13:46:58 de către Dancu Ioana » Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #16 : Februarie 09, 2008, 13:59:02 »

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.  Very Happy
Memorat
free_coder
Strain


Karma: -1
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #17 : Februarie 09, 2008, 14:07:28 »

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"
Memorat
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #18 : Februarie 09, 2008, 14:11:54 »

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

La 2 e O(log2Numar) 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.
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #19 : Februarie 09, 2008, 14:16:36 »

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

La 2 e O(log2Numar) 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. Very Happy Mai bine iti faci rezolvarea corecta.
Memorat
free_coder
Strain


Karma: -1
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #20 : Februarie 09, 2008, 14:22:55 »

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?
Memorat
cos_min
Nu mai tace
*****

Karma: 48
Deconectat Deconectat

Mesaje: 493


live


Vezi Profilul
« Răspunde #21 : Februarie 09, 2008, 14:24:38 »

Foloseste tipul bool. O sa mearga mai rapid.
Memorat

vid...
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« Răspunde #22 : Februarie 09, 2008, 18:04:24 »

La 2 e O(log2Numar) 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)
Memorat

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« Răspunde #23 : Februarie 12, 2008, 01:05:55 »

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 232), poti sa precalculezi doar pentru o parte din valori (primele 216). 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.
Memorat
shnako
Client obisnuit
**

Karma: 3
Deconectat Deconectat

Mesaje: 50



Vezi Profilul
« Răspunde #24 : Martie 19, 2009, 17:53:10 »

Este o greseala in tabelul de la exemplu. In dreapta ar trebui sa fie fold.out nu fold.in
Memorat
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines