Wątki bez odpowiedzi | Aktywne wątki
Regulamin działu
Zachęcamy do dyskusji na temat zadań z konkursu Zadanie Tygodnia. Można dzielić się uwagami i np. testami do zadań. Pamiętaj, aby nie publikować metody ani samego rozwiązania zadania z bieżącej rundy.
|
Strona 1 z 1
|
[ Posty: 7 ] |
|
Autor |
Wiadomość |
Dołączył(a): 11 paź 2010, o 21:22 Posty: 163
|
owoce - zły algorytm?
Czy coś jest nie tak w następującym algorytmie: 1) Dodaj do (np.) listy wszystkie liście 2) Dla każdego elementu listy: 2a) Jeśli w[*it]>0 w[ojciec[*it]]+=w[*it] - czyli jeśli piękno poddrzewa dodatnie powiększamy o nie piękno ojca, inaczej odcinamy te poddrzewo. 2b) Zmniejszamy stopien ojca o 1, w stopniu trzymamy ilość synów. 2c) Jeśli stopien ojca == 0, to dodajemy ojca do listy. 3) Wypisujemy w[1]. Dodam, że dostałem 7 pkt. - WA na 3 ostatnich testach (co mnie trochę dziwi, bo czemu akurat na ostatnich?).
|
28 lut 2011, o 18:19 |
|
|
Dołączył(a): 25 lut 2010, o 20:19 Posty: 69
|
Re: owoce - zły algorytm?
Mam dokładnie tak samo. Mój algorytm polegał na stworzeniu grafu nieskierowanego i przejściu go DFS'em, poprawiając wartości (jeśli w[syn]>0, to w[ojciec]+=w[syn]) wierzchołków po przejściu każdego z synów. Na koniec wypisujemy wartość w[1]. EDIT: zamiana int'ów na long long int'y i weszło na 10
Ostatnio edytowano 28 lut 2011, o 18:58 przez Michał Zezyk, łącznie edytowano 1 raz
|
28 lut 2011, o 18:56 |
|
|
Dołączył(a): 27 maja 2009, o 18:20 Posty: 126
|
Re: owoce - zły algorytm?
Drodzy Panowie, dwa słowa - long long !
|
28 lut 2011, o 18:59 |
|
|
Dołączył(a): 11 paź 2010, o 21:22 Posty: 163
|
Re: owoce - zły algorytm?
Jedno słowo - wstyd
|
28 lut 2011, o 19:41 |
|
|
Dołączył(a): 22 lis 2009, o 14:14 Posty: 217
|
Re: owoce - zły algorytm?
To bardzo wyraźny sygnał, że zabrakło LL, ewentualnie jakieś inne głupoty typu jedno zero za mało w rozmiarze tablicy.
|
28 lut 2011, o 23:57 |
|
|
Dołączył(a): 25 lut 2010, o 22:45 Posty: 72
|
Re: owoce - zły algorytm?
Tak przy okazji tematu, chciałbym zgłosić, że nie ma mnie w rankingu dotyczącym tego zadania.
|
1 mar 2011, o 19:14 |
|
|
Dołączył(a): 27 maja 2009, o 18:20 Posty: 126
|
Re: owoce - zły algorytm?
Zostało to poprawione, dziękuję za zwrócenie uwagi:)
|
1 mar 2011, o 23:32 |
|
|
|
Strona 1 z 1
|
[ Posty: 7 ] |
|
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
|
|