Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 9 ] 
Do organizatorów: Rozwiazaniado zadan i podpowiedzi 
Autor Wiadomość
Gwiazda 1

Dołączył(a): 20 lis 2009, o 10:49
Posty: 9
Post 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


26 kwi 2011, o 23:07
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post 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ź.


28 kwi 2011, o 11:34
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 4 cze 2009, o 14:29
Posty: 349
Post 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ć.


30 kwi 2011, o 00:39
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 11 paź 2010, o 17:26
Posty: 100
Post 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ę...


3 maja 2011, o 22:57
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 4 cze 2009, o 14:29
Posty: 349
Post 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.


3 maja 2011, o 23:29
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 21 wrz 2009, o 16:03
Posty: 55
Post 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.


4 maja 2011, o 12:44
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 11 paź 2010, o 17:26
Posty: 100
Post 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).


6 maja 2011, o 22:14
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 30 maja 2010, o 20:46
Posty: 69
Post 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)


7 maja 2011, o 12:42
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 11 paź 2010, o 17:26
Posty: 100
Post 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)


7 maja 2011, o 15:21
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 9 ] 


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Szukaj:
Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL