|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | Help~~How to solve it? | tob | 1518. Джедайский ребус 3 | 17 авг 2022 11:13 | 5 | 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 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 :) My such realisation works in 0.609. 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 | | Anyone WA @ 2. | 198808xc | 1518. Джедайский ребус 3 | 8 июн 2017 12:41 | 2 | 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 No, Ki are given in the correct order. | | AC 0.14 sec | partisan | 1518. Джедайский ребус 3 | 11 июн 2009 01:06 | 1 | 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! | | is operations of int64(pascal) slower than long long(c++)? | frost | 1518. Джедайский ребус 3 | 18 июл 2008 17:36 | 12 | is operations of int64(pascal) slower than long long(c++)? I really optimized my prog to got AC(I write at Pascal). Please say how you did that on Pascal
my algo O(N^3*logX)
It work fast on my computer, but not on Timus :( 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.
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:43FreePascal 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. 19 authors get AC instead of TLE. 7 of them increase their score by 1 problem! 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 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 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. | | WA3 please help(+) | Alias (Alexander Prudaev) | 1518. Джедайский ребус 3 | 10 ноя 2007 18:18 | 2 | 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; I don't know what the 3rd test is, but I've passed it having "int" replaced with "__int64" :) | | Who can tell me test 3 T_T | FLY_IN_SKY | 1518. Джедайский ребус 3 | 25 апр 2007 11:43 | 1 | |
|
|
|
