🚀 go-pugleaf

On Wed, 14 Jan 1998 18:55:22 +0100, SaBaTH 97 <sabath97@geocities.com>
wrote:

>Temat troche nie na czasie ale jest mi to potrzebne.
>------------------
>Jesli brales udzial w Olimpiadzie
>wyslij mi twoje algorytmy PLEASEEEE!!!
>A jesli udzialu nie brales tez mozesz cos wyslac

tak zle poszlo????

Jarek Woloszyn

ysr@kki.net.pl
http://free.polbox.pl/w/woljar
UIN: 1922941

On Thu, 15 Jan 1998, Yossarian wrote:

> On Wed, 14 Jan 1998 18:55:22 +0100, SaBaTH 97 <sabath97@geocities.com>
> wrote:
> 
> >Temat troche nie na czasie ale jest mi to potrzebne.
> >------------------
> >Jesli brales udzial w Olimpiadzie
> >wyslij mi twoje algorytmy PLEASEEEE!!!
> >A jesli udzialu nie brales tez mozesz cos wyslac
> 
> tak zle poszlo????

Z checia bym pogadal na grupie o tych algorytmach. Wyslac nie wysle bo nie
mam (nie bralem udzialu, jestem za stary :((((), ale jakbym mial to bym i
tak chyba nie wyslal :-|. Poza tym po zakonczeniu olimpiady wydaja
ksiazeczke z najlepszymi rozwiazaniami - mozna sobie kupic.

_______________________________________________________________________________
Michał Kaczmarczyk  mailto:mik@iname.com http://student.uci.agh.edu.pl/~kaczmar

> > >Temat troche nie na czasie ale jest mi to potrzebne.
> > >------------------
> > >Jesli brales udzial w Olimpiadzie
> > >wyslij mi twoje algorytmy PLEASEEEE!!!
> > >A jesli udzialu nie brales tez mozesz cos wyslac
> Z checia bym pogadal na grupie o tych algorytmach. Wyslac nie wysle bo nie
> mam (nie bralem udzialu, jestem za stary :((((), ale jakbym mial to bym i
> tak chyba nie wyslal :-|. Poza tym po zakonczeniu olimpiady wydaja
> ksiazeczke z najlepszymi rozwiazaniami - mozna sobie kupic.
Z rozwiazaniami "wzorcowymi", a nie najlepszymi.
W poprzedniej na przyklad do zadania XOR dali rozwiazanie wykladnicze...
Po to bylo ograniczenie przedzialu do 100000.
Moj program dzialal w O(nm) i dla danych:
000000000....000
111111111....111 (100 bitow)
dawal niemierzalny czas.

Tak wiec tych rozwiazan nie ma co stawiac za wzor :-(

*   *        *          ****          *                    
*  *   *     *          *   *       *****
* *          *     ***  *   *         *    ***
**     *     *    *   * ****  *   *   *   *   *
* *    *     *    *   * *   * *   *   *   *****
*  *   *     *    *   * *   * *   *   *   *
*   *   **    **   ***  ****   ***     **  ***
Where do YOU want to die today? *
                              **
 e-mail: kilobyte@iname.com
 URL   : http://free.polbox.pl/k/kilobyte/

On Fri, 16 Jan 1998, Adam Borowski wrote:

> Z rozwiazaniami "wzorcowymi", a nie najlepszymi.
> W poprzedniej na przyklad do zadania XOR dali rozwiazanie wykladnicze...
> Po to bylo ograniczenie przedzialu do 100000.
> Moj program dzialal w O(nm) i dla danych:
> 000000000....000
> 111111111....111 (100 bitow)
> dawal niemierzalny czas.

Kilobajt... moze bys tak oswiecil publicznosc co oznacza n i m ? 


--
   [ p00h ]____[ Stanisław Paśko ]____[ sp174751@students.mimuw.edu.pl ]
  /                                                                     \
 |                                                                       | 
  \_____________________________________________________________________/

> > Z rozwiazaniami "wzorcowymi", a nie najlepszymi.
> > W poprzedniej na przyklad do zadania XOR dali rozwiazanie wykladnicze...
> > Po to bylo ograniczenie przedzialu do 100000.
> > Moj program dzialal w O(nm) i dla danych:
> > 000000000....000
> > 111111111....111 (100 bitow)
> > dawal niemierzalny czas.
> Kilobajt... moze bys tak oswiecil publicznosc co oznacza n i m ? 

n - ilosc bramek
m - ilosc bitow liczby
 albo na odwrot

*   *        *          ****          *                    
*  *   *     *          *   *       *****
* *          *     ***  *   *         *    ***
**     *     *    *   * ****  *   *   *   *   *
* *    *     *    *   * *   * *   *   *   *****
*  *   *     *    *   * *   * *   *   *   *
*   *   **    **   ***  ****   ***     **  ***
Where do YOU want to die today? *
                              **
 e-mail: kilobyte@iname.com
 URL   : http://free.polbox.pl/k/kilobyte/

On Mon, 19 Jan 1998, Adam Borowski wrote:

> n - ilosc bramek
> m - ilosc bitow liczby
>  albo na odwrot

Czy mnie RAM nie myli czy tam ilosc bitow nie odpowiadala ilosci bramek ?
;) Anyway, algorytm w ksiazce nie byl wykladniczy tylko liniowy (to po
prustu kwestia podejscia) ... i zlozonosc byla okolo
iloscbramek*ilosckombinacji. Poniewaz zliczanie kombinacji po wstepnych
obliczeniach sprowadzalo sie tak naprawde do
log(iloscbramek)*ilosckombinacji. Dla pesymistycznych danych wynosilo to 
7 (log(100)) * 100 000 = 700.000 czyli ponizej 0.1 sekundy na pentium
a optymalny to bylo
iloscbramek*(Iloscbitow ktore trzeba sprawdzic), co w pesymistycznej
sytuacji dawalo
100 * 100 = 10.000 , czyli ponizej 0.01 sekundy na pentium ... 

Rozwiazanie optymalne polegalo na zliczaniu po calych blokach liczb,
rozwiazanie trywialne sprowadzalo sie do sprawdzenia po kolei wszystkich
kombinacji. To drugie bylo o wiele prostsze i latwiejsze do napisania
(chociaz akurat to bylo zadanie z pierwszego etapu.... wiec nieduzy
problem, choc np. mi udalo sie niedpatrzyc jednej literowki w optymalnym
;) 

A co do algorytmow to temat nadaje sie do dyskusji - ale moze by
oryginalny nadawca bardziej wyprecyzowal o co mu chodzi. Rozwiazania
specyficznych problemow niewiele dadza, proponuje zajrzec do paru ksiazek
(polecam Cormen : Wstep do Algortymow; Banachowski: Algorytmy i Struktury
Danych etc... )

--
   [ p00h ]____[ Stanisław Paśko ]____[ sp174751@students.mimuw.edu.pl ]
  /                                                                     \
 |                                                                       | 
  \_____________________________________________________________________/

> Czy mnie RAM nie myli czy tam ilosc bitow nie odpowiadala ilosci bramek ?
> ;) Anyway, algorytm w ksiazce nie byl wykladniczy tylko liniowy (to po
> prustu kwestia podejscia) ... i zlozonosc byla okolo
> iloscbramek*ilosckombinacji. Poniewaz zliczanie kombinacji po wstepnych
> obliczeniach sprowadzalo sie tak naprawde do
> log(iloscbramek)*ilosckombinacji. Dla pesymistycznych danych wynosilo to 
> 7 (log(100)) * 100 000 = 700.000 czyli ponizej 0.1 sekundy na pentium
> a optymalny to bylo
> iloscbramek*(Iloscbitow ktore trzeba sprawdzic), co w pesymistycznej
> sytuacji dawalo
> 100 * 100 = 10.000 , czyli ponizej 0.01 sekundy na pentium ... 
Bramek bylo AFAIR 1000, tak wiec algorytm "wzorcowy" dziala na pentiumie
sekunde. W instytucji ktora sprawdza rozwiazania raczej pentiumow bym sie
nie spodziewal, liczylbym raczej na 386 lub 486, tak wiec rozwiazanie
wzorcowe liczy dlugo. Miesci sie w czasie z definicji ;-) 
> Rozwiazanie optymalne polegalo na zliczaniu po calych blokach liczb,
> rozwiazanie trywialne sprowadzalo sie do sprawdzenia po kolei wszystkich
> kombinacji. To drugie bylo o wiele prostsze i latwiejsze do napisania
> (chociaz akurat to bylo zadanie z pierwszego etapu.... wiec nieduzy
> problem, choc np. mi udalo sie niedpatrzyc jednej literowki w optymalnym
> ;) 
Nie sadze. Wtedy jeszcze uczestniczylem w Olimpiadzie, robilem to zadanie
i mi taki algorytm nie przyszedl do glowy. Wedlug mnie najprosciej jest
policzyc ilosc liczb od zera do gornej granicy, od zera do dolnej granicy
i odjac.

*   *        *          ****          *                    
*  *   *     *          *   *       *****
* *          *     ***  *   *         *    ***
**     *     *    *   * ****  *   *   *   *   *
* *    *     *    *   * *   * *   *   *   *****
*  *   *     *    *   * *   * *   *   *   *
*   *   **    **   ***  ****   ***     **  ***
Where do YOU want to die today? *
                              **
 e-mail: kilobyte@iname.com
 URL   : http://free.polbox.pl/k/kilobyte/

Adam Borowski wrote:

> Bramek bylo AFAIR 1000, tak wiec algorytm "wzorcowy" dziala na pentiumie
> sekunde. W instytucji ktora sprawdza rozwiazania raczej pentiumow bym sie
> nie spodziewal, liczylbym raczej na 386 lub 486, tak wiec rozwiazanie
> wzorcowe liczy dlugo. Miesci sie w czasie z definicji ;-)

obecnie podobno maja pentiumki, nawet na nich testowali :)

--
+-----------------------------------------------+---------------+
| www.geocities.com/SiliconValley/Horizon/9357  | /-\-\--| | 97 |
+-----------------------------------------------+ \-\|<| |/|    |
| email: sabath97@geocities.com                 | \-/-/| | |    |
+------------------+----------------------------+---------------+
| ICQ UIN: 6337801 | Have some problems, need help at your page |
+------------------+ write to me.    Give your name and subject |
                   | and  I'll try to  answer  yours questions. |
                   +--------------------------------------------+