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.



Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 7 ] 
owoce - zły algorytm? 
Autor Wiadomość
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post 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
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 25 lut 2010, o 20:19
Posty: 69
Post 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 :P


Ostatnio edytowano 28 lut 2011, o 18:58 przez Michał Zezyk, łącznie edytowano 1 raz



28 lut 2011, o 18:56
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 27 maja 2009, o 18:20
Posty: 126
Post Re: owoce - zły algorytm?
Drodzy Panowie, dwa słowa - long long !


28 lut 2011, o 18:59
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: owoce - zły algorytm?
Jedno słowo - wstyd


28 lut 2011, o 19:41
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: owoce - zły algorytm?
Kamil Dębowski napisał(a):
Dodam, że dostałem 7 pkt. - WA na 3 ostatnich testach (co mnie trochę dziwi, bo czemu akurat na ostatnich?).

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
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 25 lut 2010, o 22:45
Posty: 72
Post 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
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 27 maja 2009, o 18:20
Posty: 126
Post Re: owoce - zły algorytm?
Wojciech Szałapski napisał(a):
Tak przy okazji tematu, chciałbym zgłosić, że nie ma mnie w rankingu dotyczącym tego zadania. :)


Zostało to poprawione, dziękuję za zwrócenie uwagi:)


1 mar 2011, o 23:32
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ 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

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