| ENG RUS | Timus Online Judge |
Discussion of Problem 1507. Difficult DecisionandreyDagger`~ Solution with probability // Problem 1507. Difficult Decision 18 May 2022 17:24 Calculate matrix with modulo 10^9 + 7 arrammis ideas of improving perfomance [1] // Problem 1507. Difficult Decision 5 Mar 2015 01:54 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 ?? Михаил Аршинов Re: ideas of improving perfomance // Problem 1507. Difficult Decision 1 Dec 2016 04:02 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 )) Ont Help me! I try to solve and got WA#5 [1] // Problem 1507. Difficult Decision 1 Dec 2006 20:09 What may be in test #5? gautamvs Re: Help me! I try to solve and got WA#5 // Problem 1507. Difficult Decision 29 Nov 2013 17:32 In any case, you have forgotten to sum up after powering matrices. George_Aloyan[PTS_Obninsk][MIPT][IPG][ALIGN][YANDEX] WA 33 [1] // Problem 1507. Difficult Decision 1 Apr 2012 19:32 Just "norm" matrix after every calculating (a[i][j] make 1 if it was positive) or you will have overflow Smilodon_am [Obninsk INPE] Re: WA 33 // Problem 1507. Difficult Decision 2 Apr 2012 11:51 You can only use matrix with boolean values, it looks more efficient and spectacular. Sponge Bob About WA42 [2] // Problem 1507. Difficult Decision 9 May 2007 13:55 I guess, the test42 is the following: 2 0 1 1 0 Vit Demidenko Re: About WA42 // Problem 1507. Difficult Decision 11 Jan 2010 15:23 It is test 41 malinovyi_ponchik Re: About WA42 // Problem 1507. Difficult Decision 28 Nov 2011 02:39 thank you, it helped) (WA 42) Tigran Hakobyan Possibilty // Problem 1507. Difficult Decision 18 Nov 2010 00:32 Is it possible to solve this problem within 0.001 second? 198808xc This problem is quite funny. [4] // Problem 1507. Difficult Decision 2 Oct 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. Alexey Dergunov [Samara SAU] Re: This problem is quite funny. [3] // Problem 1507. Difficult Decision 3 Oct 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] // Problem 1507. Difficult Decision 6 Oct 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? Alexey Dergunov [Samara SAU] Re: What does boolean matrix mean? [1] // Problem 1507. Difficult Decision 6 Oct 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? // Problem 1507. Difficult Decision 11 Oct 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. ILMIG0 WA#4 - answer! // Problem 1507. Difficult Decision 6 Oct 2010 18:49 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 Romko [Lviv NU] Help me please [10] // Problem 1507. Difficult Decision 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 Romko [Lviv NU] Re: Help me please [9] // Problem 1507. Difficult Decision 1 Feb 2007 02:20 Pls... Ostap Korkuna (Lviv NU) Re: Help me please // Problem 1507. Difficult Decision 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 :-) Lomir Re: Help me please [7] // Problem 1507. Difficult Decision 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 Romko [Lviv NU] Re: Help me please [6] // Problem 1507. Difficult Decision 1 Feb 2007 02:47 Thank's to all. I'll try it) Romko [Lviv NU] Re: Help me please [5] // Problem 1507. Difficult Decision 1 Feb 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] // Problem 1507. Difficult Decision 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 Georgiy Savchenko Re: Help me please [3] // Problem 1507. Difficult Decision 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 Georgiy Savchenko Re: Help me please [2] // Problem 1507. Difficult Decision 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 Romko [Lviv NU] Re: Help me please // Problem 1507. Difficult Decision 5 Feb 2007 14:57 Thank's to all. I had done it and got AC now:). Denis Koshman Re: Help me please // Problem 1507. Difficult Decision 13 Jul 2008 19:49 My WA4 was about wrong identity matrix initialization (filled in 2x2 of ones instead of NxN :P) Miha Zimin To test makers [14] // Problem 1507. Difficult Decision 1 Nov 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 juver++ Postnikov Re: To test makers [13] // Problem 1507. Difficult Decision 1 Nov 2006 17:28 In test#42 n = 1 then print Yes Miha Zimin Re: To test makers [12] // Problem 1507. Difficult Decision 1 Nov 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 juver++ Postnikov Re: To test makers [11] // Problem 1507. Difficult Decision 1 Nov 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 // Problem 1507. Difficult Decision 1 Nov 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] // Problem 1507. Difficult Decision 2 Nov 2006 01:47 Beautiful Mind Re: N=2 in test 42 (-) [7] // Problem 1507. Difficult Decision 2 Nov 2006 20:40 I got wrong answer at test 33. does it enough to use long long as data type. Anton juver++ Postnikov Re: N=2 in test 42 (-) [6] // Problem 1507. Difficult Decision 2 Nov 2006 21:52 Use 0 or 1 to present matrix value's Beautiful Mind Re: N=2 in test 42 (-) // Problem 1507. Difficult Decision 3 Nov 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] // Problem 1507. Difficult Decision 3 Nov 2006 16:18 Qyom Time Lmit Exceeded [3] // Problem 1507. Difficult Decision 4 Nov 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... Oleksandr Voietsa [Lviv NU] Re: Time Lmit Exceeded [2] // Problem 1507. Difficult Decision 7 Nov 2006 00:18 Try use express method (for example A^5 = (A^2)^2*A Qyom THANK YOU // Problem 1507. Difficult Decision 12 Nov 2006 22:57 Thank you my Friend! AC. Ti daril mne RADOST' (I eto v jizni glavnoe)...:) Neizvestnii Re: Time Lmit Exceeded // Problem 1507. Difficult Decision 22 Jun 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 // Problem 1507. Difficult Decision 13 Jul 2008 19:31 Anton juver++ Postnikov wrote 1 November 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 it4.kp How did you solve it? [1] // Problem 1507. Difficult Decision 2 Dec 2006 05:43 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 Wei Re: How did you solve it? // Problem 1507. Difficult Decision 17 Dec 2006 14:39 I just did what it told me to do. But I still got WA#1. Wei I got WA#1. Could anybody give me some test case? // Problem 1507. Difficult Decision 24 Nov 2006 14:45 The Ninjas Walk Alone!!!! After rejudge I had WA42 and Crash on #41. Hints are here (+) [5] // Problem 1507. Difficult Decision 31 Oct 2006 13:55 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 :) Fantast Re: After rejudge I had WA42 and Crash on #41. Hints are here (+) [4] // Problem 1507. Difficult Decision 31 Oct 2006 15:21 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? Sandro (USU) Re: But Power 0 of [0]-Matrix is undefined, isn't it? [2] // Problem 1507. Difficult Decision 31 Oct 2006 15:44 Sorry, there may be different definitions. But you may be sure that [0]^0 = [1] in this problem. Vladimir Yakovlev (USU) N >= 2 now (+) [1] // Problem 1507. Difficult Decision 31 Oct 2006 21:57 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. The Ninjas Walk Alone!!!! Re: N >= 2 now (+) // Problem 1507. Difficult Decision 1 Nov 2006 14:25 After second rejudge all my attempts (except one or two with silly mistakes) were accepted =) ucmcauchy Re: After rejudge I had WA42 and Crash on #41. Hints are here (+) // Problem 1507. Difficult Decision 31 Oct 2006 19:49 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?
|