Wrocławski Portal Informatyczny
http://informatyka.wroc.pl/forum/

Do organizatorów: Rozwiazaniado zadan i podpowiedzi
http://informatyka.wroc.pl/forum/viewtopic.php?f=83&t=1181
Strona 1 z 1

Autor:  Szczota [ 26 kwi 2011, o 23:07 ]
Tytuł:  Do organizatorów: Rozwiazaniado zadan i podpowiedzi

Witam!
Kiedy ukaza sie linki do rozwiazando zadan konkursowych. Swietnie bylo by , jak obiecaliscie, dodac przed rozwiazaniem podpowiedz tak by przed zapoznaniem sie z rozwiazaniem sprobowac ponownie rozwiazac zadania (wielu z nas uczy sie jeszcze algorytmiki)
pozdrawiam

Autor:  Kamil Dębowski [ 28 kwi 2011, o 11:34 ]
Tytuł:  Re: Do organizatorów: Rozwiazaniado zadan i podpowiedzi

Damian Rusak napisał(a):
To ciekawa propozycja, rozważymy, może parę zdań rozpoczynających omówienie rozwiązania byłoby skonstruowane jako podpowiedź.

Szczota napisał(a):
Swietnie bylo by , jak obiecaliscie, dodac przed rozwiazaniem podpowiedz ...

Ja w poście Damiana żadnej obietnicy nie widzę...

Coś wątpię, by pomysł z podpowiedzią się udał. Jeśli organizatorzy się o to postarają to będzie fajnie-super-extra, ale raczej nie da się (lub będzie to trudne) do każdego zadania dać podpowiedź. IMHO całkiem dobre są obecne omówienia, tzn. omówienia zadań z poprzednich spotów. Czasem 1. akapit takiego omówienia to właśnie podpowiedź.

Autor:  Przemek Pietrzkiewicz [ 30 kwi 2011, o 00:39 ]
Tytuł:  Re: Do organizatorów: Rozwiazaniado zadan i podpowiedzi

Publikacja omówień nieco się przeciągnęła ze względu na Święta. W ten weekend na pewno opublikujemy omówienia zadań pierwszej rundy.

Co do podpowiedzi - zobaczymy co uda się zrobić.

Autor:  Damian Dyńdo [ 3 maja 2011, o 22:57 ]
Tytuł:  Re: Do organizatorów: Rozwiazaniado zadan i podpowiedzi

Witam,

Takie pytanie (nie oglądałem omówień poprzednich rund) - dlaczego w zadaniach tych nie ma wzmianki o rozwiązaniu (sposobie) wzorcowym? Czytam np. do "Dlaczego oni sprawdzają" i widzę zwykły O(n^2) o ile się nie mylę (na oko, nie śledziłem za b. rozwiązania, choć sama końcówka "rozwiązanie brutalne" sugeruje że się nie mylę). Rozumiem że rozwiązanie rozwiązaniem, ale liczyłem też na coś, co jest lepsze od mojego aktualnego kodu (o ile tą rundę rozwiązałem). Szkoda trochę...

Autor:  Przemek Pietrzkiewicz [ 3 maja 2011, o 23:29 ]
Tytuł:  Re: Do organizatorów: Rozwiazaniado zadan i podpowiedzi

Damian Dyńdo napisał(a):
Witam,

Takie pytanie (nie oglądałem omówień poprzednich rund) - dlaczego w zadaniach tych nie ma wzmianki o rozwiązaniu (sposobie) wzorcowym? Czytam np. do "Dlaczego oni sprawdzają" i widzę zwykły O(n^2) o ile się nie mylę (na oko, nie śledziłem za b. rozwiązania, choć sama końcówka "rozwiązanie brutalne" sugeruje że się nie mylę). Rozumiem że rozwiązanie rozwiązaniem, ale liczyłem też na coś, co jest lepsze od mojego aktualnego kodu (o ile tą rundę rozwiązałem). Szkoda trochę...

Szczerze mówiąc, nie rozumiem. We wszystkich omówieniach opisano rozwiązania wzorcowe.

Autor:  Bartek Dudek [ 4 maja 2011, o 12:44 ]
Tytuł:  Re: Do organizatorów: Rozwiazaniado zadan i podpowiedzi

Damian Dyńdo napisał(a):
Witam,

Takie pytanie (nie oglądałem omówień poprzednich rund) - dlaczego w zadaniach tych nie ma wzmianki o rozwiązaniu (sposobie) wzorcowym? Czytam np. do "Dlaczego oni sprawdzają" i widzę zwykły O(n^2) o ile się nie mylę (na oko, nie śledziłem za b. rozwiązania, choć sama końcówka "rozwiązanie brutalne" sugeruje że się nie mylę). Rozumiem że rozwiązanie rozwiązaniem, ale liczyłem też na coś, co jest lepsze od mojego aktualnego kodu (o ile tą rundę rozwiązałem). Szkoda trochę...


Ja chyba zrozumiałem pytanie kolegi. Damianie, tutaj rozwiązanie brutalne = wzorcowe, bo nie da się inaczej, niż sprawdzić każdą parę okręgów, a potem coś z nimi robić. Nawet, gdyby dało się to jakoś szybciej robić, to pesymistycznie graf, który rozpatrujemy będzie miał n^2 krawędzi.
Podsumowując: brut = wzorcówka.

Autor:  Damian Dyńdo [ 6 maja 2011, o 22:14 ]
Tytuł:  Re: Do organizatorów: Rozwiazaniado zadan i podpowiedzi

@Przemek P. - rzuciłem okiem ostatnio na opis innych zadań i jest naprawdę dobrze opisane. Doczepiłem się jedynie do opisu "Dlaczego oni śpiewają" gdyż opisany jest "brut" (kwadrat). Zaciekawiony opisem oraz wynikami znajomych (którzy mieli właśnie na grafach - moje rozwiązanie w ogóle na nich nie bazuje) sprawdziłem przed chwilą na udostępnionych testach i dla przykładowo K=20 algorytm ma średnio ~40 obrotów + sortowanie (kulawe).

Tak więc dla k=20 mam 20*log(20) (trochę więcej, taki wynik byłby przy poprawionym sortowaniu) + ~40 obrotów samego algorytmu co daje <70obrotów. Nie chce mi się pisać teraz rozwiązania opartego na grafach, ale jeśli komuś się nudzi to może sprawdzić ile jest u niego. Wydaje mi się, że nawet jeśli dla k^2 = 400 było by te 200obrotów (1/2) to byłby niezły wynik (zważywszy że to bez sortowania).

Maksymalna złożoność wynosi: K * log(K) + K-1 + suma ciągu arytmetycznego 1,2,3...K. Przypadek po posortowaniu danych: każdy następny okrąg łączy się z wszystkimi poprzednimi, a ostatni łączy się zarówno z wszystkimi poprzednimi jak i lewą ścianą. Wynika z tego, że dla takiego testu i K=1000 mam ~500tys obrotów, kwadrat to 1mln.

Kod do przetestowania / porównania: http://pastebin.com/UuRFPP0t (uprzedzam że sortowanie jest kijowo zaimplementowane. Wystarczyło by bodajże (o ile dobrze pamiętam) tylko 1 element wektora sortować (tylko wg. niego cały wektor, a sprawdza też kolejne elementy).

Autor:  Paweł Michalak [ 7 maja 2011, o 12:42 ]
Tytuł:  Re: Do organizatorów: Rozwiazaniado zadan i podpowiedzi

Mam wrażenie, że nie rozumiesz pojęcia złożoności obliczeniowej, poczytaj o tym chociażby w Cormenie.

Btw.
1 + 2 + 3 + ... + K = O(K^2)

Autor:  Damian Dyńdo [ 7 maja 2011, o 15:21 ]
Tytuł:  Re: Do organizatorów: Rozwiazaniado zadan i podpowiedzi

@up w sumie racja, wartość ta rośnie "kwadratowo". Różnica taka, że zazwyczaj suma 1-K jest bliska połowie kwadratu czyli jakaś tam różnica jest :P.

A co do Cormena - dzięki za polecenie książki :) o ile znajdę chwilę na pewno rzucę okiem :) (szczerze to na razie jestem po (nie całym) megatutorialu :P)

Strona 1 z 1 Strefa czasowa: UTC + 1 [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/