Runda druga - zadania

ďťż

Rafał Nowak - 3 cze 2009, o 17:09
" />Moim zdaniem najtrudniejsze zadanie to "Migający tłum".

Marcin Grzywaczewski - 3 cze 2009, o 17:12
" />Dla mnie z kolei najtrudniejszym jest i było planowanie potopu - do teraz nie jestem pewien rozwiązania. W pozostałych mam tylko wątpliwości co do czasów .

Pozdrawiam.

Rafał Nowak - 3 cze 2009, o 17:13
" />Interesuje mnie jeszcze, czy spośród wielu poprawnych rozwiązań zadania "Górskie szlaki", udało się komuś udowodnić poprawność?

Rafał Nowak - 3 cze 2009, o 17:15
" />

Marcin Grzywaczewski - 3 cze 2009, o 17:18
" />Rozszerzający się BFS ze 'źródła wszelkiego zła' + wrzucanie na kopiec 'ścian' ograniczających ten teren - w przypadku, gdy za pierwszym wykonaniem BFSa ze źródła okazało się to niewystarczające - brałem najmniejszą możliwą 'ścianę' i stamtąd odpalałem BFS. Aż do skutku .

Pozdrawiam.

Agnieszka Dudek - 3 cze 2009, o 17:32
" />Jak będą wyniki, to będę dyskutować. Póki co nie jestem niczego pewna. Ten cały potop mi chyba nie wyszedł i twierdzę, że jest najtrudniejszy. Jeśli szlaki mam dobrze, to mogę udowodnić czemu są dobrze, jeśli nie, to w każdym razie sobie udowodniłam poprawność. Na migający tłum wymyśliłam dwa rozwiązania. Z czego jedno przeraziło mnie pamięciowo więc... No, jest zabawnie.

Rafał Nowak - 3 cze 2009, o 17:33
" />

Marcin Grzywaczewski - 3 cze 2009, o 17:34
" />No to implementacyjnie się kopsnąłem. Przynajmniej jednak wiem, że pomysł był dobry - a to się liczy bardziej.

Następnym razem będzie lepiej, hehe.

Pozdrawiam.

Wiktor Janas - 3 cze 2009, o 17:36
" />

Karol Kontny - 3 cze 2009, o 17:37
" />Potop wydaje mi się najtrudniejszy. Wiedziałem jak się mniej więcej zabrać do tego zadania, ale nie wymyśliłem działającego algorytmu.

Aleksander Łukasiewicz - 3 cze 2009, o 17:46
" />

Rafał Nowak - 3 cze 2009, o 17:50
" />

Marcin Grzywaczewski - 3 cze 2009, o 17:52
" />

Wiktor Janas - 3 cze 2009, o 17:54
" />

Olga Rosik-Rosińska - 3 cze 2009, o 18:03
" />

Łukasz Hanuszczak - 3 cze 2009, o 18:11
" />No to ja też bardzo podobnie z potopem. BFS tylko że zamiast kolejki użyłem kopca (set), mam nadzieję że będzie dobrze. Wszystkie testy z forum przechodzi elegancko. Mam tylko nadzieję, że nie dowaliłem sobie za dużo "ifów" przy "rozlewaniu" wody.

Aleksander Łukasiewicz - 3 cze 2009, o 18:15
" />Grupujemy liście w pary i przechodzimy od jednego do drugiego. Tak ze wszystkimi parami. W ten sposób przejdziemy przez wszystkie wyżej położone wierzchołki. Ciężko mi to wytłumaczyć ;/. Myślę, że wystarczy sobie narysować drzewo i sprawdzić, że to działa.

Michał Łowicki - 3 cze 2009, o 18:17
" />

Wiktor Janas - 3 cze 2009, o 18:24
" />

Marcin Grzywaczewski - 3 cze 2009, o 18:26
" />

Aleksander Łukasiewicz - 3 cze 2009, o 18:31
" />Ale przecież można sparować 5, 1 i 4,2. Można tak zrobić w każdym drzewie.

Wiktor Janas - 3 cze 2009, o 18:33
" />

Łukasz Hanuszczak - 3 cze 2009, o 18:35
" />Hmm... Wszyscy robili to "liśćmi" a ja zrobiłem to inaczej (ale nie wiem czy poprawnie). Po prostu kombinowałem z ilością "skrzyżowań". Do wyniku dodawałem dla każdego wierzchołka "(ilość sąsiadów) div 2 + (ilość sąsiadów) mod 2 - 1".

Olga Rosik-Rosińska - 3 cze 2009, o 18:39
" />Przy założeniu, że w drzewie mamy znaleźć jak najmniejsze x szlaków, które mogą na siebie dowolnie nachodzić, a jedynym ograniczeniem jest to, że przez dowolny fragment szlaku nie może się powtarzać, pierwsza intuicja to to, że szlaki powinny być możliwie jak najdłuższe. Skoro jak najdłuższe, to początek każdego będzie w jednym z liści (jeżeli by nie był, to widzimy, że można skonstruować dłuższy szlak). Sugerując się założeniami idziemy 'przez sąsiadów' tak długo jak się da, tj do napotkania elementu, który nie ma więcej sąsiadów (a więc musi być liściem). Żeby nie było niepotrzebnych szlaków, fajnie byłoby, żeby początki i końce każdego z nich były różne od pozostałych par początków i końców (o ile to możliwe). Skoro początek jest liściem i koniec jest liściem, to po prostu dobieramy sobie te liście w pary. Jeżeli jakiś liść zostanie bez pary to wtedy dobieramy mu dowolny inny (z własności drzew wiemy, że od każdego liścia można dojść do innego). Stąd widać, że x= k/2 + k%2 (k - liczba liści)

Agnieszka Dudek - 3 cze 2009, o 18:41
" />Postaram się wyjaśnić mój tok rozumowania. Z liścia można się wydostać tylko jedną drogą. I wychodząc z liścia chcemy pójść jak najdalej, nie wracając się. (Ponieważ jeśli mamy jakąś ilość elementów i chcemy je podzielić, tak by było jak najmniej zbiorów to przekłada się to na to, że w tych zbiorach będzie jak najwięcej elementów) Najdalej jak nam się uda dojść to będzie drugi liść. Jednym słowem, szlak zacznie się w liściu i w innym skończy. Stąd k/2. Skąd wiadomo, że przejdziemy przez wszystkie krawędzie? Jeżeli wyjdziemy z liścia to już nas nie interesuje. Teraz stoimy w miejscu, które mogło stać się liściem, lub też nie. Jeśli tak jest to znowu mamy tylko jedną drogę. Jeśli nie, to nie wiemy za bardzo, w którą stronę iść, ale nasz kolega, który idzie z innego liścia wkrótce do nas dołączy i tedy będziemy wiedzieć, że ta droga była już odwiedzona, więc nie pozostanie nam nic innego jak pójść razem w nieznane. (W kupie raźniej) No w końcu będzie tak, że nie będzie gdzie się wybrać. No i obeszliśmy wszystko...

Wiktor Janas - 3 cze 2009, o 18:55
" />

Rafał Nowak - 3 cze 2009, o 19:03
" />

Wiktor Janas - 3 cze 2009, o 19:08
" />

Rafał Nowak - 4 cze 2009, o 20:33
" />Jeśli to kogoś jeszcze interesuje, to pojawiło się omówienie zadania "Planowanie potopu".

Darmowy hosting zapewnia PRV.PL