| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Solution with probability | andreyDagger`~ | 1507. Трудное решение | 18 май 2022 17:24 | 1 |
Calculate matrix with modulo 10^9 + 7 |
| ideas of improving perfomance | arrammis | 1507. Трудное решение | 1 дек 2016 04:02 | 2 |
I have AC at 0.14 sec, but I can see there are lot of faster solutions.
So how did you optimize your solution so hard ?? hi, maybe the answer with powers from 2 to N+1 is always identical to given at this task(my AC is less than 0.14), also use some breaks like if (a[i][j] is already 1 then halt from cell computation etc.)
send at night )) |
| Help me! I try to solve and got WA#5 | Ont | 1507. Трудное решение | 29 ноя 2013 17:32 | 2 |
In any case, you have forgotten to sum up after powering matrices. |
| WA 33 | George_Aloyan[PTS_Obninsk][MIPT][IPG][ALIGN][YANDEX] | 1507. Трудное решение | 2 апр 2012 11:51 | 2 |
WA 33 George_Aloyan[PTS_Obninsk][MIPT][IPG][ALIGN][YANDEX] 1 апр 2012 19:32 Just "norm" matrix after every calculating (a[i][j] make 1 if it was positive) or you will have overflow Re: WA 33 Smilodon_am [Obninsk INPE] 2 апр 2012 11:51 You can only use matrix with boolean values, it looks more efficient and spectacular. |
| About WA42 | Sponge Bob | 1507. Трудное решение | 28 ноя 2011 02:39 | 3 |
I guess, the test42 is the following:
2
0 1
1 0 thank you, it helped) (WA 42) |
| Possibilty | Tigran Hakobyan | 1507. Трудное решение | 18 ноя 2010 00:32 | 1 |
Is it possible to solve this problem within 0.001 second? |
| This problem is quite funny. | 198808xc | 1507. Трудное решение | 11 окт 2010 00:34 | 5 |
Though I have realized there might be some math-method to solve the problem, I couldn't find them out. So, I just solve the problem "the way it tells me to do".
To prevent high-precision (Chinese name of long-arithmetic), I use this method: I choose many factors and calculate the power of the matrix with the module of the factors. So, if one cell is 0 under all the factors, we can ALMOST assert that the cell is indeed 0.
To prevent TLE, the factors could not be so many: I choose 10 factors first, that is 16384 (2^15), 19683 (3^9), 15625 (5^6), ... until 24389 (29^3). My program runs well but get TLE @ test 17.
So, I decrease the factors to only TWO: 16384 and 19683. This time my program get WA @ 9! I think I really appreciate the author for so good test-data.
After that I increase my factors to 4, adding 15625 and 16807. This time I got AC in 0.64s.
Funny problem, thx to the author.
Have fun and good luck. Hehe, you're CRAZY man...
I just used boolean matrix.
Edited by author 03.10.2010 02:10 Well, before I decided to use this CRAZY method, I have read all the topics on board, but I still can't understand the meaning of BOOLEAN MATRIX.
Could you or anyone explain it to me? Input: a[i][j] = readInt() > 0;
Then use && instead of * and || instead of +.
If result contains at least one false value, write "No".
P.S. I don't believe my eyes! You have 400+ problems solved and couldn't guess this simple approach!
Edited by author 06.10.2010 22:22 Well, just after reading your post, I read the problem statement again.
I found that I had ignored the fact that all the number is non-negative. (So stupid mistake)
Thank you. |
| WA#4 - answer! | ILMIG0 | 1507. Трудное решение | 6 окт 2010 18:49 | 1 |
Our mistake was following: we used wrong function of matrix multiplication. Our function had three parameters FUNC(a, b, c). We call FUNC(x, y, x) to calculate x = x * y; but there is mistake, because when we calculate resulting matrix we should use constant "x" and "y", but first source parameter "x" is the same as third resulting parameter "x". "X" is changing during calculation and so we change also source parameter.
Right decision is to use additional variable to store "x"
t = x;
FUNC(t, y, x);
That's all |
| Help me please | Romko [Lviv NU] | 1507. Трудное решение | 13 июл 2008 19:49 | 11 |
Help, here is my code, and I don't know why WA#4((
[deleted]
Edited by author 01.02.2007 03:06 When I made a quick look at your solution I've seen such mistakes:
1. Part of your code in function pow_matrix
for(int i = 0;i < p/2; i++)
sqr_matrix(a,b,n);
As I can guess this function has to put matrix A to the power of p. But the thing you do is - write the square of A into B many times. Your result is always square of A (not the power p)!!!
It seems, that you wanted to sleep when wrote this solution :-)
2. If you do all calculation like you do now you will get Type Overflow. That is because the numbers in A^50 can be as large as 10^100 - that does not fit in integer type (no even in Int64 ;-) ).
Correct 1. And think about 2. And you will get AC!
...if not TL :-) Try to use bool matrix.
You would get certanly overflow, so some unneeded 0 may occur duting addition.
Also you will certnaly get TLE. If you use bool matrix, then after some of multiplication, it won't chage more, so in most cases it is not even nessery to multiply till the end and add.
During the context we solved this problem without any pow, just with :
for(int i = 1; i < n*(n-1); ++i)
mult_matrix();
for(int i = n*(n-1); i < n*(n+1); ++i){
mult_matrix();
add_matrix();}
keeping in ming the chaging state of matrix. However, later some thicky test were added, so now it's ge TLE, so some more improvements are needed, but it can be passed also.
Edited by author 01.02.2007 02:40 Thank's to all. I'll try it) To Ostap: I had done some changes, but now WA5 :-(
[deleted]
Edited by author 05.02.2007 14:58 Are you sure 10^100 fits __int64 ? I think not. Read the previous post by Lomir - he explains everything pretty clearly.
Second. For example if p == 6 then you calculate ((A^2)^2)^2 == A^8 != A^6
Think about it.
Edited by author 02.02.2007 02:29 The same problem, I'm getting WA4. Please give some tests. I'm using boolean matrix, all seems to be pretty clear Got AC. Problem was in matrix multiplication, very stupid one! So when you're getting WA4, it's probably just multiplication problem Thank's to all. I had done it and got AC now:). My WA4 was about wrong identity matrix initialization (filled in 2x2 of ones instead of NxN :P) |
| To test makers | Miha Zimin | 1507. Трудное решение | 13 июл 2008 19:31 | 15 |
What is test 42?
please, give me some hint
10
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
In my WA 42 programm output "No" In test#42 n = 1 then print Yes Thanks, but I think you are wrong.
I checked it:
int n;
...
int main()
{
cin >> n;
if(n == 1)
{
double *f = new double[0xfffffff];
cout << "Yes";
return 0;
}
...
}
And this code has WA (on test 42), but not Crash or Memory limit. Therefore n is no 1 in test 42.
I need some hints as before :-)
please :-) I add this code to my last solution and got AC...
if (n * (n - 1) == 0) {
cur = e;
ok = 1; // Yes
} It's strange, but I have WA 42 as before.
:-(
Who was need rejudge?
It's so strange. My desicion was AC (2 day ago), but now I don't know what can I do with this problem.
WA 42
I got wrong answer at test 33. does it enough to use
long long as data type. Use 0 or 1 to present matrix value's Thank u very much Anton , I got accepted. I don't know why i didn't think about that Still i am quite a stupid.
Edited by author 03.11.2006 09:37
Edited by author 03.11.2006 09:37 Hello collegues ! :)
Can you tell me ... are you geting matrix B (with 0 1).
I tried that way and got TLE.
it comes about n*(n+1)*n^3 operatons.
Maybe there are more soft methods...
Try use express method (for example A^5 = (A^2)^2*A Thank you my Friend!
AC.
Ti daril mne RADOST' (I eto v jizni glavnoe)...:) But erection of a matrix in a square borrows n^3. => O(2n*(n^2)*n^3) and this had TL(((
Maybe erection of a matrix in a square can work more quickly?
Edited by author 16.09.2007 14:32 I add this code to my last solution and got AC...
if (n * (n - 1) == 0) {
cur = e;
ok = 1; // Yes
} It's strange becanse N>=2 according to problem statement |
| How did you solve it? | it4.kp | 1507. Трудное решение | 17 дек 2006 14:39 | 2 |
Is supposed solution "just do what you've been told to do",
or there is a nice idea?
In second case I'd like you to increase limit for N. Because my naive solution works for only 0.46 sec.
Edited by author 02.12.2006 05:44 I just did what it told me to do.
But I still got WA#1. |
| I got WA#1. Could anybody give me some test case? | Wei | 1507. Трудное решение | 24 ноя 2006 14:45 | 1 |
|
| After rejudge I had WA42 and Crash on #41. Hints are here (+) | The Ninjas Walk Alone!!!! | 1507. Трудное решение | 1 ноя 2006 14:25 | 6 |
I had crash because of trivial stack overflow, my recursion never ended. Check the recursion exit condition.
Hint for WA42:
Power 0 of M(nxn) matrix is a matrix
1 0 .. 0
0 1 .. 0
........
0 0 .. 1
Good luck and have fun :) As i can understand from changes i did to make my solution work, 42th test was
---------
1
0
---------
And it's considered that [0]^0 = [1]
But Power 0 of [0]-Matrix is undefined, isn't it? Sorry, there may be different definitions. But you may be sure that [0]^0 = [1] in this problem. I agree, that test
1
0
is not correct, because [0]^0 in not defined in problem statements.
New tests 41 and 42 have been modified. N >= 2 now for this problem. Submissions have been rejudged back. After second rejudge all my attempts (except one or two with silly mistakes) were accepted =) My program keeps getting WA in the test 42 but works fine for the input:
1
0
whose output is Yes
In fact my exponentation is ok when the exponent is 0.
Any possible explanation? |
