| ENG RUS | Timus Online Judge |
Discussion of Problem 1518. Jedi Riddle 3tob Help~~How to solve it? [4] // Problem 1518. Jedi Riddle 3 17 Dec 2006 18:43 Can anybody help? svr Re: Help~~How to solve it? [3] // Problem 1518. Jedi Riddle 3 27 Feb 2007 23:15 Easy solution without optimization efforts. Use Matrix A= [0 1 0 0 0 0] [0 0 1 0 0 0] [0 0 0 0 1 0] [0 0 0 0 0 1] [c1 c2 c3 c4 c5 c6] Answer=[[A^(X-N)]*K][N] Thus we must calculate pow A^(X-N) Use famous O(lg) pow in groop of matrix __int64 in inner calculations and int (rez)%Y as result Denis Koshman Re: Help~~How to solve it? [2] // Problem 1518. Jedi Riddle 3 18 Jul 2008 17:33 My such solution ran for 2.9 seconds with 3 for TL. So it's still not enogh for stable solution. I had to differentiate between M^2 and M*A matrix multiplications (the latter can be implemeted via int, +, - and >=), then it ran for 1.5 sec :) Chmel_Tolstiy Re: Help~~How to solve it? [1] // Problem 1518. Jedi Riddle 3 18 Jul 2008 18:43 My such realisation works in 0.609. Harkonnen Re: Help~~How to solve it? // Problem 1518. Jedi Riddle 3 17 Aug 2022 11:13 This time even without optimizations on +- for fast modulus, and not using fact that matrix is sparse in those cases (so multiplication can be done at O(N^2)) - it's 0.078 sec. With these optimizations - 0.046 sec. Edited by author 17.08.2022 11:56 198808xc Anyone WA @ 2. [1] // Problem 1518. Jedi Riddle 3 2 Oct 2010 21:17 Make sure that: Ki (the second input line) is given in reverse order: eg. Kn, K(n-1), ... K2, K1. But, Ci (the third input line) is not: eg. C1, C2, ..., Cn. In the sample test, this will not make you sence... This is not declared in statement. Admin: will you add this? Edited by author 02.10.2010 21:20 Edited by author 02.10.2010 21:20 Yury_Semenov Re: Anyone WA @ 2. // Problem 1518. Jedi Riddle 3 8 Jun 2017 12:41 No, Ki are given in the correct order. partisan AC 0.14 sec // Problem 1518. Jedi Riddle 3 11 Jun 2009 01:06 Avoiding taking modulo in each addition during matrix multiplication by storing value of res[i][j] in long long (int64) and taking modulo after calculating reduced time from 1.265 to 0.14! 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. Alias (Alexander Prudaev) WA3 please help(+) [1] // Problem 1518. Jedi Riddle 3 15 Mar 2007 00:03 i can prove my solution by math ans_vect = A^(x-n)*[K] answer is last digit of ans_vect vector. A[i-1][i] = 1, i = 1..n; A[n][i] = C[i], i = 1..n; Howl of Despair Re: WA3 please help(+) // Problem 1518. Jedi Riddle 3 10 Nov 2007 18:18 I don't know what the 3rd test is, but I've passed it having "int" replaced with "__int64" :) FLY_IN_SKY Who can tell me test 3 T_T // Problem 1518. Jedi Riddle 3 25 Apr 2007 11:43
|