Discussion @ 1518. Jedi Riddle 3 @ Timus Online Judge

frost is operations of int64(pascal) slower than long long(c++)? [11] // Problem 1518. Jedi Riddle 3 16 Dec 2006 14:32

is operations of int64(pascal) slower than long long(c++)?

Dmitry 'Diman_YES' Kovalioff I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-) [10] // Problem 1518. Jedi Riddle 3 16 Dec 2006 14:38

EfremovAleksei Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-) [6] // Problem 1518. Jedi Riddle 3 17 Dec 2006 17:55

I really optimized my prog to got AC(I write at Pascal).

KIRILL(ArcSTU) Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-) [5] // Problem 1518. Jedi Riddle 3 17 Dec 2006 19:56

Please say how you did that on Pascal
my algo O(N^3*logX)
It work fast on my computer, but not on Timus :(

Nick J Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-) [4] // Problem 1518. Jedi Riddle 3 19 Dec 2006 18:39

Me and my friend had exactly the same algorithm and optomization but my program needs 1.7 and his needs 0.3secs (we both use C++)
It is very hard to solve it in Pascal, so use C++ :) or rewrite program several times.

Dmitry 'Diman_YES' Kovalioff The complaint is accepted (+) [3] // Problem 1518. Jedi Riddle 3 19 Dec 2006 21:40

It appeared, that FreePascal 2.0.4 compiler, which is used on Timus Online Judge, is extremely slow at arithmetical operations, especially on Int64-operands. "Mod" and "*" operations on Int64 are very slow. We did not expect such a thing, and we are sorry.

Anyway, the jury HAS correct Pascal solution, which passes the timelimit (2 seconds), so it is a question of justice only, not of jury mistakes, problem incorrectness and so on.

Now the timelimit is 3 seconds, and it is more than enough to solve this problem on Pascal without special optimization trick. My straightforward solution works exactly 2 second: http://acm.timus.ru/status.aspx?space=1&num=1518&pos=1383115

The problem will be rejudged soon.

The performance of FreePascal 2.0.4 compiler in comparison with Delphi 7 compiler (dcc32 15.0) is under inverstigation. If Delphi appears to be faster (and it seems to be true), it would be added on Timus Online Judge. If you know the fastest Pascal compiler, please, tell us. It will be fair for Pascal programmers, because the fastest Intel C++ Compiler is used for C++.

Edited by author 19.12.2006 21:43

KIRILL(ArcSTU) Re: The complaint is accepted (+) // Problem 1518. Jedi Riddle 3 19 Dec 2006 22:25

FreePascal generates very bad code for int64 multiplicatons.
I use Delphi 7.0 and on my computer (AthlonXP 2200)
my prog works 0.9 sec in worst case, but on Timus the
same prog works 2.093 sec.
I got AC in 1.261 sec with rewritng
multiplication on Assembler.

Vladimir Yakovlev (USU) Problem has been rejudged (+) [1] // Problem 1518. Jedi Riddle 3 20 Dec 2006 00:20

19 authors get AC instead of TLE. 7 of them increase their score by 1 problem!

m2m Re: Problem has been rejudged (+) // Problem 1518. Jedi Riddle 3 20 Dec 2006 01:10

My algo is also N^3*log(X), but not accepted in C++.
how to solve it?

Time limit in test case 13. anyone helps me ?

Edited by author 20.12.2006 01:17

asd Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-) [2] // Problem 1518. Jedi Riddle 3 8 Jan 2007 14:20

My solution is also O(logX*N^3) but my program written on Java works so slowly...

for example, It works about 6 seconds on test

100 268435455 268435455
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

I can't even imagine how to solve it without rewriting solution using another language...

Edited by author 08.01.2007 19:20

Dmitry 'Diman_YES' Kovalioff Ilya Grabnov's straightforward Java solution works 1.6 sec. (-) // Problem 1518. Jedi Riddle 3 8 Jan 2007 14:40

Denis Koshman Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-) // Problem 1518. Jedi Riddle 3 18 Jul 2008 17:36

Since the matrix consists of only zeroes and ones, you can perform half of multiplications using just +, - and >= via 32bit types. Perform only squaring via __int64 and %. This helped to make my 2.9 sec C++ solution running at 1.5 sec.

Discussion of Problem 1518. Jedi Riddle 3