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: 8 ] 
Wieża - tylko 8 punktów 
Autor Wiadomość
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Wieża - tylko 8 punktów
Czym mogą być spowodowane runtime errory w tym zadaniu?
I tak patrzę, że nie tylko ja mam 8 pkt...

PS. Mam 8/10, a jeśli się nie mylę to dostałem 10 pkt. serwisowych (gwiazdki).


23 mar 2011, o 14:28
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 7 gru 2010, o 21:24
Posty: 24
Post Re: Wieża - tylko 8 punktów
Może przekroczenie limitu pamięci.


23 mar 2011, o 15:08
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: Wieża - tylko 8 punktów
Niemożliwe (chyba).
Dane z wejścia trzymane są w dużych strukturach (vector<int> w[1000000]), ale trzymam tylko te dane (wejściowe), nic więcej nie dorzucam.
Dodam, że są to testy 7., 9.


23 mar 2011, o 16:10
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 7 gru 2010, o 21:24
Posty: 24
Post Re: Wieża - tylko 8 punktów
Ja posłałem dwie wersje programu:
Wersja 1.
z dużymi tablicami vectorów - wynik taki jak u Ciebie. Zwracam uwagę, że jeden pusty vector<int> to 24B, a jeśli coś się do niego dorzuca...?

Wersja 2.
z mapami vectorów - wynik: 10 pkt.


23 mar 2011, o 16:49
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: Wieża - tylko 8 punktów
Że niby (przy vector<int> w[1000000]) jeśli dam 100 razy w[123].PB(a) to mam złożoność pamięć jako 1000000*128, a nie jako 1000000+128?
Bo nie rozumiem...


23 mar 2011, o 16:59
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 7 gru 2010, o 21:24
Posty: 24
Post Re: Wieża - tylko 8 punktów
Nie wiem czy rzeczywiście przekroczenie limitu pamięci jest tu problemem, ale na razie (tzn. bez gruntownego przemyślenia) kombinuję tak:

vector<int> w[1000000] ma rozmiar ~24MB

Czy w Twoim algorytmie każdą wieże dokładasz tylko do jednego z tego miliona wektorów?
U mnie, kolejna wieża mogła przedłużać wiele ciągów (o różnych różnicach), więc dokładałem ją do wielu wektorów.
Załóżmy tak złośliwy układ (nie szukałem go jeszcze), że każda z 10^5 wież dokładana jest do 100 wektorów w tablicy w[]:
100*10^5*4B=40MB
+sama tablica=24MB
razem 64MB


23 mar 2011, o 17:27
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: Wieża - tylko 8 punktów
U mnie 1 wieża do 1 wektora.
Przy wczytywaniu wrzucałem wysokości do wektorów, a potem już nic nie dorzucałem.


24 mar 2011, o 00:52
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 7 gru 2010, o 21:24
Posty: 24
Post Re: Wieża - tylko 8 punktów
W takim razie, nie wiem co jest grane.


24 mar 2011, o 09:26
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 8 ] 


Kto przegląda forum

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


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