Zadanie Zalew, TLE

ďťż

Zadanie Zalew, TLE

Przemek Pietrzkiewicz - 27 lis 2009, o 19:35
" />W związku z lawiną reklamacji wyjaśniam - wszystkie TLE na zadaniu Zalew są jak najbardziej słuszne.

Dla osób testujących swoje rozwiązania lokalnie cenna będzie informacja, że kolejność testów w komunikatach sprawdzarki niedokładnie odpowiada numeracji 1-10 w paczkach. Sortowanie po nazwie wykonuje testy zgodnie z porządkiem leksykograficznym: 10,1,2,...,9. Wkrótce dodamy wyświetlanie w wynikach nazwy plików testowych.

Duża ilość TLE na największych testach wynika z tego, że oczekiwane rozwiązanie pracowało w złożoności liniowej, tymczasem większość z Was nadesłała rozwiązanie liniowologarytmiczne. Rozwiązanie Autora pracuje na największym teście 1.1 s, limit został ustawiony ze sporym zapasem na 3 s.

Bartosz Miszczak - 27 lis 2009, o 19:42
" />Aż dziw, że pożyczyliście kompa z muzeum
Intel Core 2 Duo 1,8GHz:

Adrian Jaskółka - 27 lis 2009, o 19:43
" />ale limity danych wyglądały tak że n*m*log cośtam powinno przechodzić! miałem pomysł na liniówkę ale stwierdziłem że dla takich ograniczeń z pewnością przejdzie n*m*log wysokość. nie powinno się rozróżniać takich rozwiązań. jeśli już to ograniczenia powinny być większe (wtedy jest większa różnica między rozwiązaniami), a limit czasu srogi.

mios - 27 lis 2009, o 19:45
" />

Mateusz Skórski - 27 lis 2009, o 19:47
" />A ja zrobiłem zalew w O(n*m*(lg max_h)). I mam 10/10. Najdłuższe dwa testy, 1- 2.36s, 9 - 1,97s. Reszta poniżej pół sekudy. Polak potrafi.

Edit: poprawiłem malą pomyłkę w złożoności. mój błąd.

Przemek Pietrzkiewicz - 27 lis 2009, o 19:50
" />

Adrian Jaskółka - 27 lis 2009, o 19:54
" />no mi nie przeszło :/ uważam że limit czasu powinien być tak dobrany aby KAŻDE rozwiązanie które ma satysfakcjonującą złożoność powinno mieć maksa.

Aleksander Kramarz - 27 lis 2009, o 19:55
" />kaalex@Lenovo:/media/Dane/Programming/FallSpot/Zalew$ for((i=1;i<=10;i++)) do time ./zal.o < ./ZALEW/tests/zal$i.in > out; diff -b -s ./out ZALEW/tests/zal$i.out; done

real 0m0.019s
user 0m0.004s
sys 0m0.000s
Pliki ./out i ZALEW/tests/zal1.out są identyczne

real 0m0.004s
user 0m0.000s
sys 0m0.000s
Pliki ./out i ZALEW/tests/zal2.out są identyczne

real 0m0.025s
user 0m0.000s
sys 0m0.008s
Pliki ./out i ZALEW/tests/zal3.out są identyczne

real 0m0.005s
user 0m0.000s
sys 0m0.000s
Pliki ./out i ZALEW/tests/zal4.out są identyczne

real 0m0.011s
user 0m0.004s
sys 0m0.004s
Pliki ./out i ZALEW/tests/zal5.out są identyczne

real 0m0.068s
user 0m0.040s
sys 0m0.008s
Pliki ./out i ZALEW/tests/zal6.out są identyczne

real 0m0.068s
user 0m0.036s
sys 0m0.008s
Pliki ./out i ZALEW/tests/zal7.out są identyczne

real 0m0.140s
user 0m0.100s
sys 0m0.012s
Pliki ./out i ZALEW/tests/zal8.out są identyczne

real 0m0.324s
user 0m0.312s
sys 0m0.008s
Pliki ./out i ZALEW/tests/zal9.out są identyczne

real 0m0.448s
user 0m0.428s
sys 0m0.008s
Pliki ./out i ZALEW/tests/zal10.out są identyczne

A mam liniowo-logarytmicznie... DualCore 2.0GHz...

Anna Piekarska - 27 lis 2009, o 19:56
" />Mi również przeszło rozwiązanie O(n*m*log h_max) i mam najwyższy czas 2.45s.

Moim zdaniem różnicowanie rozwiązań z logarytmem od tych bez jest dość trudne. Choćby dlatego, że wczytywanie danych zajmuje sporą część czasu - u mnie test 10. działa 0.63s a samo czytanie danych - 0.26s.

Aleksander Kramarz - 27 lis 2009, o 19:58
" />Śmiem twierdzić, że trafiłem na duże obciążenie serwera...

Marcin Dublański - 27 lis 2009, o 19:59
" />

Kacper Kula - 27 lis 2009, o 19:59
" />

Rafał Bielenia - 27 lis 2009, o 20:03
" />Warto też zauważyć, że limity powinny być dobrane tak, żeby rozwiązanie w rozsądnej złożoności przechodziło bez większych optymalizacji implementacyjnych, w tym przypadku za dużo STL'a = klapa

Bartosz Miszczak - 27 lis 2009, o 20:07
" />

Szymon Sidor - 27 lis 2009, o 20:10
" />Takie pytanko do organizatorów, czy którykolwiek z testow byl tak dobrany zeby wywalac rozwiazania z nierangowanym find & union? Bo w sumie mi jeden test nie przeszedl i zastanawiam sie czy ogolnie napisalem taki program z duza stala, czy po prostu metoda byla zla (bo nie przeszlo mi testu oznaczonego w wynikach jako 1)?

Przemek Pietrzkiewicz - 27 lis 2009, o 20:10
" />

Karol Różycki - 27 lis 2009, o 20:15
" />

Adrian Jaskółka - 27 lis 2009, o 20:16
" />

Adrian Jaskółka - 27 lis 2009, o 20:21
" />miałem do zalewów 2 wysyłki:
1) z drobnym bugiem 4/10 w tym jeden time limit oraz reszta wa i rte
2) zdebugowana 8/10 dwa tle

mój bug nie powinien zmieniać liczby wykonywanych operacji, a jednak mam tle mimo iż wcześniej nie było.
myślę że to coś z tymi przeciążonymi serwerami...

edit: ten test co w 2) miałem tle w 1) dział 2.70

Jarosław Gomułka - 27 lis 2009, o 20:23
" />

Aleksander Kramarz - 27 lis 2009, o 20:27
" />Gdyby czasy mojego rozwiązania były podejrzane, tj. działałoby ledwo poniżej 3s, mocno zastanawiałbym się nad innym algorytmem. Ale czemu miałem mieć wątpliwości gdy czasy mojego rozwiązania były 6 razy mniejsze od limitu?

Przemek Pietrzkiewicz - 27 lis 2009, o 20:28
" />

Karol Różycki - 27 lis 2009, o 20:30
" />

Adrian Jaskółka - 27 lis 2009, o 20:32
" />

Adrian Jaskółka - 27 lis 2009, o 20:36
" />

Marcin Dublański - 27 lis 2009, o 20:43
" />

Adrian Jaskółka - 27 lis 2009, o 20:52
" />

gm.promix gm.promix - 27 lis 2009, o 21:04
" />Takie rzeczy moga sie dziac jesli na komputerze na ktorym sa testowane programy jest procesor z HT.

anteq - 27 lis 2009, o 21:17
" />kurcze, ludzie, po co się bez sensu kłócicie. I tak to nic nie zmieni; lepiej zabierzcie się do rozwiązywania 3 rundy. Sam nie mam liniowego rozwiązania, ale wystarczyło się przyłożyć do implementacji, pomyśleć trochę nad pesymistycznymi przypadkami i bez problemu przechodzi.

Darmowy hosting zapewnia PRV.PL