4268. Listy i koperty [LETTERS]

[witman]

http://pl.spoj.pl/problems/LETTERS/

Mam wprawdzie to zadanie zaliczone, ale intryguje mnie, jak można je zrobić z czasem równym lub bliskim 0.00s (Charyzjusz Chakier i parę innych osób).
Sugerowałoby to, że istnieje algorytm O(k), bo z moim O(max(n

i

)+k) mam czas powyżej sekundy.
Czy ktoś mógłby się wypowiedzieć na ten temat?

[manjaro]

Jakim cudem ktoś ma zaliczone z wynikiem ponad 5 sekund kiedy czas na wykonanie jest 0.1 sek?
Mój program na ideone dla skrajnie dużego testu n=1000000 trwa 0.03s a na spoju przekraczam limit czasu… Co jest nie tak?

[tarpauwatratar]

Jakim cudem ktoś ma zaliczone z wynikiem ponad 5 sekund kiedy czas na wykonanie jest 0.1 sek?

Nie mam pojęcia. Podejrzewałbym, że kiedyś w zadaniu obowiązywały inne limity, po zmianie których nie zrobiono rejudge / zrobiono rejudge ale pominięto choć jedno zgłoszenie.

Mój program na ideone dla skrajnie dużego testu n=1000000 trwa 0.03s a na spoju przekraczam limit czasu… Co jest nie tak?

Zapewne istnieje nieskrajnie duży test, który powoduje TLE.

[manjaro]

Zapewne istnieje nieskrajnie duży test, który powoduje TLE.

No właśnie nie, bo liczę w pętli od 1 do 10^6. Czyli mniejsze testy trwają krócej niż 0.03s. Widziałem że rozwiązałeś to zadanie wczoraj dlatego się za to zabrałem Niby proste ale sposób rozwiązania jest jeden, bez pętli się nie obejdzie. A pętla u mnie powoduje przekroczenie czasu. Można trochę iść na skróty i policzyć kilka/kilkadziesiąt wyników ręcznie i stablicować w programie. Ale takie rozwiązanie jest trochę mało eleganckie to raz a po drugie nadal nie rozwiązuje problemu jeśli zawężę pętlę do 10^5.
Trochę jeszcze ugryzłem na szybkości i nadal za wolno

[mariusz193]

Jakim cudem ktoś ma zaliczone z wynikiem ponad 5 sekund kiedy czas na wykonanie jest 0.1 sek?

ten czas to na pojedynczy test, suma może być większa
wątpliwe też, aby robiono rejudge - miałem czas 0,21 (w 2009 roku) a puszczone dziś dało czas 0,01

Mój program na ideone dla skrajnie dużego testu n=1000000 trwa 0.03s a na spoju przekraczam limit czasu… Co jest nie tak?

prawdopodobnie i algorytm, i test jest nie tak

prześlij program, to może w wolnej chwili spojrzę (na swój stary program spojrzałem i nic nie rozumiem - chyba kiedyś byłem mądrzejszy )

[manjaro]

Mariusz wysłałem na priv.
Raczej algorytm jest dobry bo dla n z zakresu 0-450 daje na 100% poprawne wyniki

[tarpauwatratar]

ten czas to na pojedynczy test, suma może być większa

wątpliwe też, aby robiono rejudge - miałem czas 0,21 (w 2009 roku) a puszczone dziś dało czas 0,01

No dobrze, ale jeżeli czas na pojedynczy test to 0.102 sekundy wówczas mamy dla zaledwie 5 sekund 5 / 0.102 = 49 testów. Trochę za dużo jak na moje oko…

EDIT
W moim oknie problemsettera mogę wprowadzić limit czasu dla każdego przypadku testowego. Jeżeli w treści zadania wyświetla się minimum z limitów czasu dla każdego przypadku testowego (nie chce mi się sprawdzać bo interfejs nie jest zbyt przyjazny, a ostatnio SPOJ zachowuje się jakby był DDoSowany) to wszystko jest jasne.

EDIT2
Chociaż właśnie piszę na ten temat z @manjaro i chyba są zadania, gdzie limit czasowy jest postaci 1 - 3 sek.

[mariusz193]

to odpowiedź też na priv.

[manjaro]

No więc wychodzi chyba na to że 0.102s to jest sumaryczny czas wszystkich przypadków i ja go przekraczam spoko mogę to poprawić myślę. Ale w takim razie dlaczego 63% osób dostały zaliczenie z czasami powyżej 0.102s? A już grubym przegięciem jest 5.76s

[yula]

No więc wychodzi chyba na to że 0.102s to jest sumaryczny czas wszystkich przypadków

Nie, to jest czas wykonania jednego pliku testowego. Jeśli jest ich więcej to i czas odpowiednio dłuższy. W większości zadań są czasy dłuższe w zaliczeniach od tego podanego w zadaniu, no chyba że jest tylko jeden test.

[manjaro]

Zaraz chwila co znaczy 1 pliku testowego? Że zestawy testowe składają się z 10 plików i w każdym z nich 10 testów? A jaki byłby niby sens takiego kombinowania?

[tarpauwatratar]

Na wejściu program otrzymuje plik te(k)stowy zgodny ze specyfikacją zadania. Ich liczba jest dowolna, narzucana przez autora zadania.