 |
Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
hansu
Nieomylny Admin
Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów
Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?
|
 Wysłany: Pon 18:23, 13 Lis 2006 Temat postu: Zadanie N* - Fabryka |
|
|
Tak nietypowo dzisiaj ;)
[link widoczny dla zalogowanych]
|
|
| Powrót do góry |
|
 |
|
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Rogal
Zjeb z kaszanką
Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów
Skąd: koło podbiegunowe
|
| Wysłany: Pon 21:37, 13 Lis 2006 Temat postu: |
|
|
|
Nie warto przesadzać z obiektowością... Przez to dostałem bombkę za TLE.
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
kg86
zielony żul
Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów
Skąd: pochodze?
|
| Wysłany: Wto 0:44, 14 Lis 2006 Temat postu: |
|
|
|
albo ja jestem slepy, albo w tresci nie jest okreslone ograniczenie gorne na szybkosc dzialania poszczegolnych maszyn :P
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Skrobocik
[SKROBORANGA]
Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów
Skąd: Skarżysko , Kraków
|
| Wysłany: Wto 1:37, 14 Lis 2006 Temat postu: |
|
|
|
Już Hansik zapytał na forum TCSu ;)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
hansu
Nieomylny Admin
Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów
Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?
|
| Wysłany: Wto 1:54, 14 Lis 2006 Temat postu: |
|
|
| Skrobocik napisał: | | Już Hansik zapytał na forum TCSu ;) |
Grrrrrr :/ Ile razy mam powtarzac? 'H' != 'h' :!: :!: :!:
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
cct
pijak
Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów
|
| Wysłany: Wto 1:56, 14 Lis 2006 Temat postu: |
|
|
| Rogal napisał: | | Nie warto przesadzać z obiektowością... Przez to dostałem bombkę za TLE. |
Przejdzie k*log( max{a, b} ) ? (Wstępnie dwa kopce mi się widzą tak po przeczytaniu tego zadanka...) W sumie zakresy b i a są małe...
EDIT: jednak najlepsze co w tej chwili wymyśliłem to O( k*b ) :/ (chociaż w praktyce niby dużo mniejsza stała niż b, to jednak...).
A w ogóle, powiedz na jakiej Ty przepchnąłeś.
| kg86 napisał: | | albo ja jestem slepy, albo w tresci nie jest okreslone ograniczenie gorne na szybkosc dzialania poszczegolnych maszyn |
A w sumie ma to jakieś znaczenie? ;))
Ostatnio zmieniony przez cct dnia Wto 5:27, 14 Lis 2006, w całości zmieniany 1 raz
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
kg86
zielony żul
Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów
Skąd: pochodze?
|
| Wysłany: Wto 2:12, 14 Lis 2006 Temat postu: |
|
|
|
ma znaczenie, bo moze wynik np. przekroczyc inta :P
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
cct
pijak
Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów
|
| Wysłany: Wto 2:16, 14 Lis 2006 Temat postu: |
|
|
| kg86 napisał: | | ma znaczenie, bo moze wynik np. przekroczyc inta :P |
Czyli nie ma, bo to nie zwiększa złożoności asymptotycznej ;))
A na serio, to nie myślałem jeszcze nad implementacją, ale sumie to słuszna uwaga. Z góry więc pewnie za jakieś zaoszczędzone bombki.
EDIT: hmm, w sumie może mieć to jednak znaczenie duże przy implementacji na szybkość ;/
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
kg86
zielony żul
Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów
Skąd: pochodze?
|
| Wysłany: Wto 3:15, 14 Lis 2006 Temat postu: |
|
|
@Rogal - zarzucisz binarka? :D :)
albo jakims dobrym testem poprawnosciowym? :) bo mam ANSa, a nie udowodnilem, ze moj algorytm jest poprawny ;P
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Skrobocik
[SKROBORANGA]
Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów
Skąd: Skarżysko , Kraków
|
| Wysłany: Wto 3:44, 14 Lis 2006 Temat postu: |
|
|
| hansu napisał: | | Skrobocik napisał: | | Już Hansik zapytał na forum TCSu ;) |
Grrrrrr :/ Ile razy mam powtarzac? 'H' != 'h' :!: :!: :!: |
Sorki hansu ( :twisted: ), ale ja już przyzwyczajony jestem, że jak operuję ksywkami, to po prostu stosuję wiekie litery, bo to prawię jak imiona ;)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Makros
pijak
Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów
Skąd: Kraków
|
| Wysłany: Wto 8:06, 14 Lis 2006 Temat postu: |
|
|
| kg86 napisał: | @Rogal - zarzucisz binarka? :D :)
albo jakims dobrym testem poprawnosciowym? :) bo mam ANSa, a nie udowodnilem, ze moj algorytm jest poprawny ;P |
Jestem w podobnej sytyacji... :D przydała by się binarka :D
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Spectro
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów
Skąd: Kurdwanów
|
| Wysłany: Wto 8:59, 14 Lis 2006 Temat postu: |
|
|
|
Binarkę możesz wrzucić, ale rozwiązania jeszcze nie mów ;) . Niektórzy chcą chwilę pomyśleć nad tym zadaniem, a jego termin jest sensowny.
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
kg86
zielony żul
Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów
Skąd: pochodze?
|
| Wysłany: Wto 14:37, 14 Lis 2006 Temat postu: |
|
|
|
@Spectro - a czy my prosimy o rozwiazanie? :P
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Makros
pijak
Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów
Skąd: Kraków
|
| Wysłany: Wto 15:15, 14 Lis 2006 Temat postu: |
|
|
|
wlasnie :D
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Rogal
Zjeb z kaszanką
Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów
Skąd: koło podbiegunowe
|
| Wysłany: Wto 15:51, 14 Lis 2006 Temat postu: |
|
|
Zgodnie z zadadą mówisz masz...
[link widoczny dla zalogowanych]
Rozwiązanie jest wolne (ma niepotrzebnie dużą stałą) więc raczej wszystko co działa dłużej niż 2x czas mojego powinno dostać TLE.
edited: Test poprawnościowy na którym uwaliłem już algorytmy 2 osób :D :
Poprawna odpowiedź to 9 :wink:
Naprawdę polecam przeanalizowanie tego testu zanim zaczniecie wogóle myśleć nad rozwiązaniem tego zadania
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
cct
pijak
Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów
|
| Wysłany: Wto 21:33, 14 Lis 2006 Temat postu: |
|
|
| Rogal napisał: | Zgodnie z zadadą mówisz masz...
[link widoczny dla zalogowanych]
Rozwiązanie jest wolne (ma niepotrzebnie dużą stałą) więc raczej wszystko co działa dłużej niż 2x czas mojego powinno dostać TLE. |
Ale zdradź jaka jest ta złożoność, bo ja na Th( k*( lg( max{ a, b } ))) dostaje uparcie TLE (tak naprawdę to jest to k*(lg(a) + lg(b)), ale jedno wchodzi pod drugie)...
Z góry dzięki.
EDIT: Generatorka testów leży [link widoczny dla zalogowanych]
A wyniki mi generuje dużo wolniej niż Rogalowi - dla dużych testów parokrotna różnica, chociaż głównie przy dużej ilości testów. Ech :/
EDIT2: Prawie 300 MB input (10k testow na maksa) Rogalowa liczy 3 min, moja 4:40. Czyli czeka mnie zmudna walka ze stala, ale juz praktycznie nie widze, gdzie :/
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Rogal
Zjeb z kaszanką
Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów
Skąd: koło podbiegunowe
|
| Wysłany: Wto 22:42, 14 Lis 2006 Temat postu: |
|
|
cct: Wybacz, nie podam Ci tak dokładnej złożoności bo po prostu nie umiem tego policzyć :D
Ale działa to w O(N * (log(A)+log(B)) gdzie N to ilość półproduktów do przetworzenia, a A i B to ilości maszyn.
Poza tym wydaje mi się, że jeśli po optymalizacjach masz znacząco gorsze czasy ode mnie to powinineś pomyśleć nad jakąś poprawą samego algorytmu... Bo ja kilkoma kliknięciami mógłbym przyspieszyć swój kod pewnie gdzieś o połowę.
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
cct
pijak
Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów
|
| Wysłany: Wto 22:51, 14 Lis 2006 Temat postu: |
|
|
| Rogal napisał: | cct: Wybacz, nie podam Ci tak dokładnej złożoności bo po prostu nie umiem tego policzyć :D
Ale działa to w O(N * (log(A)+log(B)) gdzie N to ilość półproduktów do przetworzenia, a A i B to ilości maszyn.
Poza tym wydaje mi się, że jeśli po optymalizacjach masz znacząco gorsze czasy ode mnie to powinineś pomyśleć nad jakąś poprawą samego algorytmu... Bo ja kilkoma kliknięciami mógłbym przyspieszyć swój kod pewnie gdzieś o połowę. |
Sęk w tym, że ja nie mogę tak naprawdę rzec "po optymalizacjach", bo nie za bardzo mam gdzie optymalizować [deleted].
A w notacji masz na pewno O, a nie Th? Bo jeśli da się to zrobić w O, to będę musiał faktycznie nad optymalizacją pomyśleć jakąś algorytmiczną...
EDIT: chwilka, w sumie z kopca nie trzeba niczego wyciągać ani wkładać, right? jak ja lubię te momenty, gdy błyska nadzieja ;)
Ostatnio zmieniony przez cct dnia Śro 0:34, 15 Lis 2006, w całości zmieniany 1 raz
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Rogal
Zjeb z kaszanką
Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów
Skąd: koło podbiegunowe
|
| Wysłany: Wto 23:14, 14 Lis 2006 Temat postu: |
|
|
| cct napisał: | | A w notacji masz na pewno O, a nie Th? Bo jeśli da się to zrobić w O, to będę musiał faktycznie nad optymalizacją pomyśleć jakąś algorytmiczną... |
Ja się naprawdę na tym nie znam... Poza tym myślałem, że Th(n) jest podzbiorem O(n), więc jeśli coś działa w Th(n) to w szczególności działa też w O(n).
edited: Tak przeczytałem co zostało napisane na forum apropo tego zadania i w zasadzie jak się to wszystko zbierze do kupy to mamy gotowe rozwiązanie.
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
cct
pijak
Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów
|
| Wysłany: Śro 0:20, 15 Lis 2006 Temat postu: |
|
|
| Rogal napisał: | | Ja się naprawdę na tym nie znam... Poza tym myślałem, że Th(n) jest podzbiorem O(n), więc jeśli coś działa w Th(n) to w szczególności działa też w O(n). |
Tak, ale tu nigdy nie zrobi mniej (co najwyżej można by próbować uzasadniać to O faktem, że przesiewanie nie jest O( lg(a) ) a nie Theta).
Optowałbym jednak za tetą.
Anyway, przeszło po wywaleniu zbędnego wyciągania i wkładania rzeczy do kopca.
A co z tym Y? Bo ja tego nie widzę chwilowo za cholerę ;))
| Rogal napisał: | | edited: Tak przeczytałem co zostało napisane na forum apropo tego zadania i w zasadzie jak się to wszystko zbierze do kupy to mamy gotowe rozwiązanie. |
A czy to źle? :)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
r4ku
żul
Dołączył: 09 Lut 2006
Posty: 722
Przeczytał: 0 tematów
Skąd: klikash? :D
|
| Wysłany: Śro 0:28, 15 Lis 2006 Temat postu: |
|
|
| cct napisał: | | A czy to źle? :) |
tak, bo ja jeszcze nie mialem czasu nad nim przysiasc, a wole jednak wykminic je sam... i chyba nie tylko ja...
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
cct
pijak
Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów
|
| Wysłany: Śro 0:38, 15 Lis 2006 Temat postu: |
|
|
| r4ku napisał: | | cct napisał: | | A czy to źle? :) |
tak, bo ja jeszcze nie mialem czasu nad nim przysiasc, a wole jednak wykminic je sam... i chyba nie tylko ja... |
To się zdecyduj - wolisz przysiąść nad nim i wykminić, czy czytać ten wątek? Bo widzę konflikt wewnętrzny objawiający się w działaniu ;)
Nawet gdyby było wprost napisana - a nie jest! - to wystarczy przerwać czytanie.
Zresztą, dyskutowaliśmy o złożoności cały czas (jedyne w miarę bezpośredni opis wywaliłem), co może jedynie pomóc - to chyba pierwsze zadanko na ASD2 gdzie można dostać dość łatwo TLE mając dobrą asymptotyczną i wszystko liczone po drodze.
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
r4ku
żul
Dołączył: 09 Lut 2006
Posty: 722
Przeczytał: 0 tematów
Skąd: klikash? :D
|
| Wysłany: Śro 0:44, 15 Lis 2006 Temat postu: |
|
|
jak jest to czyta sie wszystko jak leci na tym forum (tak przed snem, do poduszki :P ), natomiast gdybym nie mial wazniejszych (a takie istnieja i nie jest to analiza...:D ) rzeczy na glowie to bym przysiadl i zrobil...
ale fakt nikt nie zmusza do czytania akurat tego wantku... musze potrenowac moja slaba silna wole :P
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
hansu
Nieomylny Admin
Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów
Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?
|
| Wysłany: Śro 1:56, 15 Lis 2006 Temat postu: |
|
|
| cct napisał: |
Tak, ale tu nigdy nie zrobi mniej (co najwyżej można by próbować uzasadniać to O faktem, że przesiewanie nie jest O( lg(a) ) a nie Theta).
Optowałbym jednak za tetą.
|
To zle bys optowal... Zreszta sam sobie napisales dlaczego - przy kopcu nie da sie thety okreslic. A notacja O istotnie zawiera w sobie thete. Scislej mowiac - zbior funkcji theta(f(n)) dla pewnego f(n) jest istotnym podzbiorem zbioru O(f(n)) (przypominam ze mowimy tu o notacji "O duze" - "o male" to zupelnie inna bajka...)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
cct
pijak
Dołączył: 21 Mar 2006
Posty: 202
Przeczytał: 0 tematów
|
| Wysłany: Śro 4:01, 15 Lis 2006 Temat postu: |
|
|
| hansu napisał: | | To zle bys optowal... Zreszta sam sobie napisales dlaczego - przy kopcu nie da sie thety okreslic. A notacja O istotnie zawiera w sobie thete. Scislej mowiac - zbior funkcji theta(f(n)) dla pewnego f(n) jest istotnym podzbiorem zbioru O(f(n)) (przypominam ze mowimy tu o notacji "O duze" - "o male" to zupelnie inna bajka...) |
Yup, ale argument pod logarytmem jest de facto rzędu [zakres danych] dużo mniejszego niż czynnik liniowy, więc to O sugeruje co najwyżej zbicie lekkie współczynnika. I parafrazując Ciebie z tej podstrony: optować != uważać za zgodne z formalną definicją.
[BTW nie chce mi się teraz szukać, ale jeśli dobrze pamiętam, to to jednak nawet formalnie chyba jest to notacja Th ( k*lg(b) ), bo istnieją takie m i n, że m*k*lg(b) <= n*k*lg(b) <= n*k*lg(b); w tym przypadku: m = 1/lg(10000), n = 10000: oba niezalezne od glownego argumentu, czyli k, ktore nie dosc, ze ma duzo wieksze limity, ale i w wyzszej 'potedze' jest ].
To mniej więcej jak w smokach - co z tego, że liniowe były, skoro nie od tego, od czego byśmy chcieli ;/
A tak w ogóle, to chyba Theta (równe) była podzbiorem O (mniejsze lub równe, inaczej: co najwyżej równe na rząd). Ale to tylko luźne wspomnienia z zamierzchłych wieczorów nad Cormenem, może coś mylę, albo mówimy o innych definicjach.
Ogółem intuicyjnie wolę uważać za Thety wszystkie algosy które główne współczynniki mają zawsze wykonywane niezależnie od układu danych wejściowych.
|
|
| Powrót do góry |
|
|
|
|
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
|
fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Szukaj
Użytkownicy
Grupy
Galerie
Rejestracja
Zaloguj się, by sprawdzić wiadomości
Zaloguj
