Обсуждение @ 1507. Трудное решение @ Timus Online Judge

andreyDagger Solution with probability // Задача 1507. Трудное решение 18 май 2022 17:24

arrammis ideas of improving perfomance [1] // Задача 1507. Трудное решение 5 мар 2015 01:54

George_Aloyan[PTS Obninsk] WA 33 [1] // Задача 1507. Трудное решение 1 апр 2012 19:32

Tigran92[RAU_902] Possibilty // Задача 1507. Трудное решение 18 ноя 2010 00:32

Ilmir Tazetdinov [IATE] WA#4 - answer! // Задача 1507. Трудное решение 6 окт 2010 18:49

198808xc This problem is quite funny. [4] // Задача 1507. Трудное решение 2 окт 2010 18:32

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.

Moonstone [Samara SAU] Re: This problem is quite funny. [3] // Задача 1507. Трудное решение 3 окт 2010 02:08

Hehe, you're CRAZY man...
I just used boolean matrix.

Edited by author 03.10.2010 02:10

198808xc What does boolean matrix mean? [2] // Задача 1507. Трудное решение 6 окт 2010 22:08

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?

Moonstone [Samara SAU] Re: What does boolean matrix mean? [1] // Задача 1507. Трудное решение 6 окт 2010 22:18

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

198808xc Re: What does boolean matrix mean? // Задача 1507. Трудное решение 11 окт 2010 00:34

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.

SomethingWild About WA42 [2] // Задача 1507. Трудное решение 9 май 2007 13:55

Roma Labish[Lviv NU] Help me please [10] // Задача 1507. Трудное решение 31 янв 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

Roma Labish[Lviv NU] Re: Help me please [9] // Задача 1507. Трудное решение 1 фев 2007 02:20

Pls...

Ostap Korkuna (Lviv NU) Re: Help me please // Задача 1507. Трудное решение 1 фев 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 :-)

Lomir Re: Help me please [7] // Задача 1507. Трудное решение 1 фев 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

Roma Labish[Lviv NU] Re: Help me please [6] // Задача 1507. Трудное решение 1 фев 2007 02:47

Thank's to all. I'll try it)

Roma Labish[Lviv NU] Re: Help me please [5] // Задача 1507. Трудное решение 1 фев 2007 03:05

To Ostap: I had done some changes, but now WA5 :-(

[deleted]

Edited by author 05.02.2007 14:58

Ostap Korkuna (Lviv NU) Re: Help me please [4] // Задача 1507. Трудное решение 2 фев 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

Georgiy Savchenko Re: Help me please [3] // Задача 1507. Трудное решение 4 фев 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

Georgiy Savchenko Re: Help me please [2] // Задача 1507. Трудное решение 4 фев 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

Roma Labish[Lviv NU] Re: Help me please // Задача 1507. Трудное решение 5 фев 2007 14:57

Thank's to all. I had done it and got AC now:).

Denis Koshman Re: Help me please // Задача 1507. Трудное решение 13 июл 2008 19:49

My WA4 was about wrong identity matrix initialization (filled in 2x2 of ones instead of NxN :P)

it4.kp How did you solve it? [1] // Задача 1507. Трудное решение 2 дек 2006 05:43

Ont Help me! I try to solve and got WA#5 [1] // Задача 1507. Трудное решение 1 дек 2006 20:09

Kingway Jin I got WA#1. Could anybody give me some test case? // Задача 1507. Трудное решение 24 ноя 2006 14:45

Miha Zimin To test makers [14] // Задача 1507. Трудное решение 1 ноя 2006 14:35

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"

Anton [SUrSU] Re: To test makers [13] // Задача 1507. Трудное решение 1 ноя 2006 17:28

In test#42 n = 1 then print Yes

Miha Zimin Re: To test makers [12] // Задача 1507. Трудное решение 1 ноя 2006 21:37

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 :-)

Anton [SUrSU] Re: To test makers [11] // Задача 1507. Трудное решение 1 ноя 2006 22:14

I add this code to my last solution and got AC...
if (n * (n - 1) == 0) {
cur = e;
ok = 1; // Yes
}

Miha Zimin Re: To test makers // Задача 1507. Трудное решение 1 ноя 2006 22:46

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

Vladimir Yakovlev (USU) N=2 in test 42 (-) [8] // Задача 1507. Трудное решение 2 ноя 2006 01:47

Beautiful Mind Re: N=2 in test 42 (-) [7] // Задача 1507. Трудное решение 2 ноя 2006 20:40

I got wrong answer at test 33. does it enough to use
long long as data type.

Anton [SUrSU] Re: N=2 in test 42 (-) [6] // Задача 1507. Трудное решение 2 ноя 2006 21:52

Use 0 or 1 to present matrix value's

Beautiful Mind Re: N=2 in test 42 (-) // Задача 1507. Трудное решение 3 ноя 2006 09:36

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

SPIRiT And perhaps it's also good to use & for multiplying and | for summing...(-) [4] // Задача 1507. Трудное решение 3 ноя 2006 16:18

Hayk Time Lmit Exceeded [3] // Задача 1507. Трудное решение 4 ноя 2006 02:10

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...

Olecksandr[LNU] Re: Time Lmit Exceeded [2] // Задача 1507. Трудное решение 7 ноя 2006 00:18

Try use express method (for example A^5 = (A^2)^2*A

Hayk THANK YOU // Задача 1507. Трудное решение 12 ноя 2006 22:57

Thank you my Friend!
AC.

Ti daril mne RADOST' (I eto v jizni glavnoe)...:)

Neizvestnii Re: Time Lmit Exceeded // Задача 1507. Трудное решение 22 июн 2007 21:09

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

Denis Koshman Re: To test makers // Задача 1507. Трудное решение 13 июл 2008 19:31

Anton [SUrSU] писал(a) 1 ноября 2006 22:14

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

Tbilisi SU: Andrew Lutsenko After rejudge I had WA42 and Crash on #41. Hints are here (+) [5] // Задача 1507. Трудное решение 31 окт 2006 13:55

Обсуждение задачи 1507. Трудное решение