Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 70 ]  Przejdź na stronę Poprzednia strona  1 ... 3, 4, 5, 6, 7  Następna strona
Mistrzostwa - testy 
Autor Wiadomość
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: Mistrzostwa - testy
Sry, nie chodziło mi o przodków, tylko potomków xp.
Ja w górę przekazywałem tylko ile mam niesparowanych ludzi w danym poddrzewie. Liczba potomków w każdym poddrzewie była mi potrzebna do tego, aby ich móc odpowiednio "przepinać". Np. jeżeli pewien wierzchołek miał 3 synów przy czym z jednego poddrzewa nie można było sparować 10 ludzi, a z pozostałych np. 2 i 1, ale w tych dwóch ostatnich poddrzewach było co najmniej 10 potomków, to mogłem tych niesparowanych z pierwszego poddrzewa przepiąć do tych potomków z pozostałych poddrzewach.


15 paź 2010, o 19:29
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 25 paź 2009, o 12:35
Posty: 37
Post Re: Mistrzostwa - testy
Jakub Sygnowski napisał(a):
Adam Nieżurawski napisał(a):
To jak robiliście to zadanie moi mili?
Ono chyba było najtrudniejsze z tej rundy.

Ja sobie zrobiłem dodatkowy wierzchołek -1, aby ten graf był spójny. No i puszczam sobie DFS od tego wierzchołka. I to trochę taki dynamik. Rozwiązujemy dla liści, dla większego poddrzewa, mając to to rozwiążemy dla większego i tak dalej. Każde poddrzewo (każdy syn) zwraca ojcu dwie liczby. Ile par się udało utworzyć i ile niesparowanych zostało. No i ojciec otrzymuje od synów te wartości i kombinuje z nimi. Jakąś parę z jednego poddrzewa można zniszczyć by 2 powstałe wierzchołki sparować z niesparowanymi dwoma z innego poddrzewa. :)


Strasznie skomplikowane.
Ja zawsze łączyłem 2 korzenie o największej ilości synów (drugim kryterium był rozmiar poddrzewa). Jak nie było dwóch korzeni - to wywalałem ten korzeń, który był.


Okazuje się, że moje rozwiązanie było błędne - dostaje 'jedynie' 9/10 ^^ (WA na jednym z 100 przypadków).


15 paź 2010, o 19:56
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: Mistrzostwa - testy
Uff... Mi na szczęście wszystkie testy dobrze przechodzi :). Tylko ten czas mnie niepokoi, bo u mnie na kompie to działa ponad 5 sekund :/.


15 paź 2010, o 20:18
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 30 maja 2010, o 20:46
Posty: 69
Post Re: Mistrzostwa - testy
Uuu.. u mnie przy użyciu seta niecałe dwie sekundy (1.969s), a sprawdzaczka jest +/- 2 razy szybsza, więc nie wiadomo..


15 paź 2010, o 20:25
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 1 sie 2010, o 23:23
Posty: 34
Post Re: Mistrzostwa - testy
Ja użyłem seta, ostatni test 0.804s, O(nlogn).
Na początku wrzucałem "minus jedynki" do seta, sortującego według wielkości danego poddrzewa i brałem 2 korzenie z największych poddrzew i łączyłem je, jak już połączyłem dany korzeń, to usuwałem go z seta, a następnie dodawałem do tego seta jego synów.


15 paź 2010, o 21:23
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 31 maja 2009, o 18:24
Posty: 107
Post Re: Mistrzostwa - testy
Adam Nieżurawski napisał(a):
To jak robiliście to zadanie moi mili?
Ono chyba było najtrudniejsze z tej rundy.

W sumie ja nie zrobiłem Studni, dla mnie ona była trudniejsza. A za to mam 10/10 i bardzo się z tego cieszę, bo moje rozwiązanie było takie bardziej "na czuja" - formalnie nie byłem pewny dowodu. Leciałem BFS i obliczałem odległość wierzchołków od korzenia każdego drzewa składowego (czyli od -1). Ponieważ można parować ze sobą wierzchołki o jednakowej odległości od korzenia, to to robiłem, zaczynając od dołu. Z danego poziomu mógł mi zostać jeden niesparowany wierzchołek. No to przekazywałem go do sparowania do góry (bo tylko jeden wierzchołek z wyższego poziomu może być ojcem, więc zawsze da się sparować, o ile jest więcej niż jeden wierzchołek danego poziomu). Problem jest jedynie, gdy na danym poziomie jest tylko jeden wierzchołek we wszystkich składowych. To oznacza, że jest ojcem wszystkich wierzchołków, które nam zostały niesparowane. W takim razie przekazujemy go dalej, razem z tymi niesparowanymi. Kiedy w końcu na jakimś poziomie będzie więcej wierzchołków, wtedy postaramy się sparować z nimi te wolne. Najfajniejsze jest to, że to działa. Jak ktoś nie bardzo rozumie ten bełkot, to mogę udostępnić kod, żeby rozjaśnić lub jeszcze bardziej zaciemnić obraz mojego rozwiązania ;).


15 paź 2010, o 22:18
Zobacz profil
Gwiazda 1Gwiazda 1Gwiazda 1Gwiazda 1
Avatar użytkownika

Dołączył(a): 8 paź 2010, o 21:56
Posty: 40
Post Re: Mistrzostwa - testy
15
-1 1 2 3 3 3 1 7 8 9 9 8 14 7 14

Mógłby ktoś mi wyjaśnić dlaczego dla tego zestawu wychodzi 7?
Licząc na kartce wychodzi mi 6 i taki również algorytm napisałem. To był jedyny wynik, który mi się różnił z przykładów tu podanych i mam 1/10.


15 paź 2010, o 22:23
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: Mistrzostwa - testy
To zadanie miało to do siebie, że jeżeli test nie był jakoś specjalnie układany, to z bardzo dużym prawdopodobieństwem wychodzi wynik n/2, gdzie n to liczba zawodników. W tym zadaniu można było naprodukować bardzo dużo heur, które dawały poprawne wyniki na ogromnej liczbie forumowych testów xp.
Ja się bardzo cieszę, bo dostałem 10/10, program na sprawdzarce działał mi 0.18s, mimo, że na moim kompie ponad 5s xD.


15 paź 2010, o 22:30
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 20 lis 2009, o 18:40
Posty: 105
Post Re: Mistrzostwa - testy
Looooozeeer!
Mój działał 0.15s :D


15 paź 2010, o 22:33
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 20 lis 2009, o 14:15
Posty: 106
Post Re: Mistrzostwa - testy
Mój ma w 9 i 10 0.17s :(


15 paź 2010, o 22:52
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: 70 ]  Przejdź na stronę Poprzednia strona  1 ... 3, 4, 5, 6, 7  Następna strona


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