ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1507. Difficult Decision

Help me please
Posted by Roma Labish[Lviv NU] 31 Jan 2007 23:49
Help, here is my code, and I don't know why WA#4((
[deleted]

Edited by author 01.02.2007 03:06
Re: Help me please
Posted by Roma Labish[Lviv NU] 1 Feb 2007 02:20
Pls...
Re: Help me please
Posted by Ostap Korkuna (Lviv NU) 1 Feb 2007 02:32
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 :-)
Re: Help me please
Posted by Lomir 1 Feb 2007 02:33
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
Re: Help me please
Posted by Roma Labish[Lviv NU] 1 Feb 2007 02:47
Thank's to all.  I'll try it)
Re: Help me please
Posted by Roma Labish[Lviv NU] 1 Feb 2007 03:05
To Ostap: I had done some changes, but now WA5 :-(

[deleted]

Edited by author 05.02.2007 14:58
Re: Help me please
Posted by Ostap Korkuna (Lviv NU) 2 Feb 2007 02:24
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
Re: Help me please
Posted by Georgiy Savchenko 4 Feb 2007 06:46
The same problem, I'm getting WA4. Please give some tests. I'm using boolean matrix, all seems to be pretty clear
Re: Help me please
Posted by Georgiy Savchenko 4 Feb 2007 16:01
Got AC. Problem was in matrix multiplication, very stupid one! So when you're getting WA4, it's probably just multiplication problem
Re: Help me please
Posted by Roma Labish[Lviv NU] 5 Feb 2007 14:57
Thank's to all. I had done it and got AC now:).
Re: Help me please
Posted by Denis Koshman 13 Jul 2008 19:49
My WA4 was about wrong identity matrix initialization (filled in 2x2 of ones instead of NxN :P)