1 / 12
Jul 2004

Hi there!

I think, that the main problem with haskell programs is doing I/O within the time limit. For example "Help R2/D2" would be a really nice problem, but I testet my haskell O(n log(n) ) solution with the judge input data and noticed, that I need already 30 seconds for reading the data, whereas my algorithm solves the problem within 10 seconds (everything local measurements on my PC).

To hit the point: Does anyone know, how to do input better than in the code block below? For with better I/O routines I think, I could solve more problems in haskell, and I noticed, that there are some rather fast haskell solutions to other problems, which I think do their I/O in a better way.

By the way: Is it right, that Word32 gives worse performance than Int?

compute :: Int -> Int -> [(Int, Int)] -> (Int, Int)
compute k n list = (indres, countTo treeres indres (2^dep))
	where
		(indres, treeres) = foldl eval (0, construct k dep 1) list
		dep = min (next2powerPot n) 17
		eval (ind, tree) (val, times) = if a > 0 then error "impossible" else (max ind b, c)
			where (a, b, c) = insert tree val times
readQ :: Int -> IO [(Int, Int)]
readQ 0 = return []
readQ k = do
	l <- getLine
	if head l == 'b' then do
			let [t, v] = (map read . tail . words) l
			r <- readQ (k - t)
			return ((v, t):r)
		else do
			r <- readQ (k - 1)
			return ((read l, 1):r)
readCase :: Int -> IO ()
readCase 0 = return ()
readCase cases = do
	k <- readLn
	n <- readLn
	q <- readQ n
	let (i, w) = compute k n q
	putStrLn (show i ++ " " ++ show w)
	readCase (cases - 1)
main :: IO ()
main = do
	cases <- readLn
	readCase cases
  • created

    Jul '04
  • last reply

    Dec '14
  • 11

    replies

  • 1.5k

    views

  • 9

    users

  • 1

    link

I tested your solution a bit, because another problem popped (I think you mentioned it earlier):
Stack space overflow: current size 1048576 bytes.
Use `+RTS -Ksize' to increase it.

Now all ghc programs are ran with +RTS -K24000k (and that amount of memory is guaranteed in addition to that set by the problemsetter) and your solution is a clear TLE, giving correct answer after about 6 minutes smile

2 years later
9 months later

Czy ktoś mógłby naświetlić o co chodzi w tym zadaniu ? Rzucić jakimś linkiem z teorią albo coś smile

Dotyczy to również zadania: Aproksymacja Średniokwadratowa Dyskretna

3 years later

Spróbuj całkiem wywalić tego cosinusa. Gdy zamieniasz go tylko na sin to dostajesz bazę w stylu: sinx, sinx, sin2x, sin2x. Dlatego musisz to tak pozmieniać, żeby baza się zgadzała dokładnie z tą oczekiwaną (w przeciwnym razie nigdy wyniki nie będą takie jak chce autor zadania). Co do tego dlaczego [tex]y \not\in \left\langle -1;1 \right\rangle[/tex]. Jeśli dobrze zrozumiałem pytanie - dla kazdego z zapytań x, wynikiem działania algorytmu jest suma postaci F(x) = a1*cos(x) + b1*sin(x) + ... + am*cos(mx) + bm*sin(mx). Może ona swobodnie przyjąć wartość [tex]y \not\in \left\langle -1;1 \right\rangle[/tex].

20 days later

Ok, już rozumiem z tą dziedziną i tymi bazami. Dzięki. smile
Jednak wychodzi na to, że nie rozumiem tego sposobu, bo wyniki są ciągle zpełnie inne.
Oto kod, choć wątpię czy ktoś znajdzie błąd, bo pewnie jest on logiczny i okaże się, że cały algorytm jest zły:

tu był kod

Edit:AC

3 years later

Dzięki za okazanie zainteresowania, ale wydaje mi się, że problem leży w czym innym.

Jeszcze raz napiszę, że w moim przypadku baza to: 1,sinx,sin(2x),...
Mój program daje wyniki takie same jak w komentarzu pod tym zadaniem napisał Damian Straszak, który zaznaczył że jego program ma AC (a mój z identycznymi wynikami - WA).

Tutaj macie wątek:
http://devel.sphere-research.com/phpBB3-spoj-pl/viewtopic.php?f=1&t=207
gdzie pewien użytkownik ma bazę 1,cosx,cos(2x),... oraz podaje wyniki, które są identyczne z tym co drukuje mój program po zamianie funkcji sin na cos.
Podaje przykład dla bazy 1,cosx,cos(2x),... żebyście mogli sprawdzić sami:

Wejście:
2
4
0.31 -3.00
0.84 -1.00
1.36 3.00
1.88 -1.00
4
0.00
0.52
1.57
2.62
6
0.31 0.00
1.36 -5.00
2.41 -2.00
3.46 -2.00
3.98 1.00
5.03 0.00
6
0.00
1.05
1.57
2.09
2.62
3.40
Wyjście:
-3.12
-2.6
3.11
-29.12
-22.09
16.89
-5.47
6.08
-4.75
-0.87

Użytkownik w tamtym wątku także napisał, że jego program ma AC. Specjalnie założyłem konto, w którym jest baza 1,cosx,cos(2x),... żeby to sprawdzić i mój program dostaje WA.

Zatem śmiem twierdzić, że coś się popsuło ze sprawdzaniem tego zadania. W tej chwili mam prośbę do kogoś kto ma bazę 1,sinx,sin(2x),.... lub 1,cosx,cos(2x),... i jakieś stare zgłoszenie AC o przesłanie tego zgłoszenia jeszcze raz. Jeżeli mam rację, to takie zgłoszenie dostanie teraz WA, co będzie wystarczającym dowodem na to, że sędzia się myli.

Ale w takim razie jak wytłumaczyć fakt, że kod, który miał kiedyś AC teraz ma WA (i sam Piotr, to potwierdził)? Autor zmienił sprawdzanie zadania (po 2012 roku, gdzie jego ostatnia aktywność na SPOJu to chyba 2007), nie zrobił rejudge zgłoszeń oraz nie poinformował nas o niczym? Wydaje mi się to mało prawdopodobne, ale nie wykluczam. smile

Od początku wydawało mi się, że to zadanie jest skonstruowane w ten sposób, że autor wymyślił sobie jakiś złożony wzór funkcji, wziął z niej kilka punktów na węzły, i kilka na zapytania i te wartości są w przykładzie. Interpolacja taka jak u mnie produkuje niedokładne odpowiedzi, ale jest jakiś dopuszczalny margines błędu. Czy mógłbyś napisać czy Twoje rozwiązanie daje identyczne odpowiedzi jak w treści zadania, czy może przybliżone jak u mnie i w wypowiedziach wymienionych wcześniej użytkowników?

Dla bazy 1,x,x^2, ... mam zgodne wyjście, dla bazy 1,cosx,cos(2x),... mam już spore rozbieżności, więc chyba problem jest z tym zadaniem, skoro akceptuje coś czego nie powinien i odwrotnie. Gdyby ktoś kto zaliczył zadanie i ma inną bazę niż te dwie u góry, sprawdził jeszcze moim kodem czy dostanie AC, byłoby wiadomo więcej.

Poniżej załączam wejście i wyjście dla bazy 1,x,x^2, ... Być może jest to warunek wystarczający na zaliczenie tego zadania smile

Wejście
2
4
0.00 3.00
0.10 0.00
0.20 4.00
0.40 0.00
4
0.00
0.10
0.30
0.45
6
0.00 4.00
0.10 3.00
0.30 3.00
0.50 1.00
0.60 -5.00
0.80 2.00
6
0.00
0.10
0.25
0.30
0.45
0.65
Wyjście:
3
0
6.75
-9.52
4
3
2.42
3
2.78
-7.97

Ja mam bazę 1,sinx,cosx,sin(2x),cos(2x) i w swoim [starym] rozwiązaniu AC, mam w jednym pkt rozbieżność aż 0.13, ale być może autor ustawił tak dużą tolerancję, np z dokładnością do 0.1 ?

Nie rozumiem czemu masz assert(n>=4 && n<=6); - gdzieś [skąś] takie ograniczenia wynikają? Jednak gdyby to był błąd byłby sigabort, więc tak tylko z ciekawości.

Mario, jeżeli chcesz, mogę z przyjemnością przetestować twój kod, na moich danych, na mojej bazie.

może autor nie, ale nastąpiła wielka migracja i przy jej okazji coś może się stało.

PS
Spectral_ dostosowałem twój kod do mojej bazy i jest AC, chociaż też jest w stosunku do przykładu, max błąd 0.13

Szukałem ograniczeń na n (najpierw z nieskończoną pętlą, tzn if(n>ileś tam) while(1); - dlatego TLE w początkowych zgłoszeniach, a potem zmieniłem na assert, bo bardziej profesjonalnie i tak zostało smiley ). Okazuje się, że n przyjmuje wartości 4 lub 6 (nie ma n nieparzystych). Dlaczego to robiłem? Bo najpierw chciałem liczyć macierz odwrotną i wiedziałem, że dla dużych macierzy będą problemy z błędami numerycznymi, ale potem się kapnąłem, że to przecież układ równań liniowych - zadanie, które robiłem niedawno. I można wykorzystać sprawdzony algorytm. Ale to mało ważne.

Najpierw proponuje rozwiązać zagadkę dlaczego zgłoszenie AC z przeszłości ma teraz WA.

Nie mam wystarczających uprawnień, nie mam wglądu ani do zadania ani do testów, więc raczej nie dam rady.