| ENG RUS | Timus Online Judge |
Discussion of Problem 1627. JoinMahilewets I am really poor [7] // Problem 1627. Join 8 May 2017 14:30 So, I just wrote solution with C long double and got WA #5 (Laplacian). Then I just rewrote it in Python with decimal.py and got WA...#3! Then I started to add more precision to decimal and got TLE #3. Yeah, I use some epsilon constant and add it to determinant before convert determinant to integer and get its modulo 10**9. Mahilewets Re: I am really poor [6] // Problem 1627. Join 8 May 2017 16:08 Lol FINALLY understand I should just made M[row] [col] =LCM Mahilewets Re: I am really poor [5] // Problem 1627. Join 8 May 2017 17:14 Mahilewets Re: I am really poor [4] // Problem 1627. Join 8 May 2017 17:19 Yeah! I tried this: 3 3 *** *.* *** And got zero, not one! Should correct... Mahilewets Re: I am really poor [3] // Problem 1627. Join 8 May 2017 17:42 Corrected that input for 3 3. But WA#6 still!!! http://ideone.com/KGeDMM Edited by author 08.05.2017 17:42 Mahilewets Re: I am really poor [2] // Problem 1627. Join 8 May 2017 18:46 WA #8. I am really frustrated. http://ideone.com/7nPKN0 That time without fractions. Used decimal with 1450 digits after point. Edited by author 08.05.2017 18:47 Mahilewets Re: I am really poor [1] // Problem 1627. Join 8 May 2017 19:12 I realized I need not determinant of a whole matrix but just a minor. http://ideone.com/5H6ARH Submitted corrected solution with Fractions. Buuut!! WA #8 still... Mahilewets Re: I am really poor // Problem 1627. Join 8 May 2017 19:38 Alexandru Valeanu Hint Test #5 // Problem 1627. Join 30 Jan 2014 12:38 The Laplacian matrix does not have always N * M lines/columns. ApriCot{TNU} WA1 (help please) [1] // Problem 1627. Join 29 Dec 2011 05:26 оффтоп Edited by author 29.12.2011 05:41 Sasha Bar [TNU] Re: WA1 (help please) // Problem 1627. Join 29 Dec 2011 05:40 *WALL* kiko Who can tell me the answer to this test? [1] // Problem 1627. Join 10 Apr 2011 16:01 input 9 9 ......... ......... ......... ......... ......... ......... ......... ......... ......... bsu.mmf.team Re: Who can tell me the answer to this test? // Problem 1627. Join 11 Apr 2011 03:26 900397056 xkszltl Wa on Test#5,who can tell me why? // Problem 1627. Join 20 Feb 2011 18:41 Pasky new test should be added [1] // Problem 1627. Join 16 Aug 2010 06:13 My AC solution crashes on this test 2 2 ** ** Sandro (USU) Re: new test should be added // Problem 1627. Join 16 Aug 2010 11:08 Problem statement is updated. Read "Site news". Zayakin Andrey[PermSU] hint about TL // Problem 1627. Join 5 Aug 2010 04:07 Random shuffle of matrix`s rows help me to avoid TLE Зане I know how to do it now! // Problem 1627. Join 10 Nov 2009 12:58 We can use Matrix-Tree theoremd(生成树计数) to solve it! O(N^3) MSDN How to solve it with dp profile? // Problem 1627. Join 14 Aug 2009 13:11 Genesis How to solve this problem? [15] // Problem 1627. Join 18 Aug 2008 21:40 I already found a way to convert the graph to a matrix, and the ans is the determinant of this matrix. But it seems so hard to get it. [SPbSU ITMO] WiNGeR Re: How to solve this problem? [10] // Problem 1627. Join 19 Aug 2008 00:41 There is another way to solve this problem Genesis Re: How to solve this problem? [9] // Problem 1627. Join 19 Aug 2008 06:25 I have AC now, but can you E-mail me your method please ykt836@gmail.com, thanks emotional blind Re: How to solve this problem? [8] // Problem 1627. Join 19 Aug 2008 09:39 Hi Genesis, Can You give me hint how did you to mod the determinant. I am having problem with it. Edited by author 19.08.2008 09:39 Vedernikoff Sergey (HSE: EconomicsForever!) Re: How to solve this problem? // Problem 1627. Join 19 Aug 2008 15:45 Of course, the usual way of solving such problems is DP by profile. But method of Genesis is much more easier to implement. Thank you for idea! Genesis Re: How to solve this problem? [6] // Problem 1627. Join 19 Aug 2008 16:59 I used JAVA's BigInteger, I can mod the determinant just before I print it Vedernikoff Sergey (HSE: EconomicsForever!) Re: How to solve this problem? [2] // Problem 1627. Join 19 Aug 2008 18:05 One can use extended euclid to do all calculations modulo 10^9 straightforwardly Al.Cash Re: How to solve this problem? // Problem 1627. Join 21 Aug 2008 14:36 Vedernikoff Sergey (HSE: EconomicsForever!) wrote 19 August 2008 18:05 One can use extended euclid to do all calculations modulo 10^9 straightforwardly 10^9 isn't a prime number! How will you find for example ( 1/10 ) mod 10^9 ? svr Re: How to solve this problem? // Problem 1627. Join 23 Oct 2008 00:10 I used BigInteger and Kirgoff determinant theorem. Dp or divide and concur approach seems unimplementing. Interesting who used nondeterminant approach. Crusader Re: How to solve this problem? [2] // Problem 1627. Join 27 Aug 2008 12:36 i can't understand. when i solve the determinant of the matrix, there are decimal fraction indeed. how can you avoid it? can you tell me in detail? Genesis Re: How to solve this problem? [1] // Problem 1627. Join 29 Aug 2008 08:22 multiply their LCM Crusader Re: How to solve this problem? // Problem 1627. Join 29 Aug 2008 15:03 yumen , can not pass test 5. Cat36 Re: How to solve this problem? [3] // Problem 1627. Join 5 Feb 2009 22:06 I know simple and fast way to calculate the determinant of matrix by the integer modulo... But I don't understand, how convert graph to a matrix((( test 1 - 0110 1001 1001 0110 - det =0 svr Re: How to solve this problem? // Problem 1627. Join 5 Feb 2009 22:18 I used article in wiki with key words Kirgoff theorem Vedernikoff Sergey (HSE: EconomicsForever!) Re: How to solve this problem? [1] // Problem 1627. Join 5 Feb 2009 22:24 2 Cat36: Mail to nick@inbox.ru using goryinyich as nick and I'll explain to you what you want, and you'll explain to me what I want =))) Cat36 Re: How to solve this problem? // Problem 1627. Join 23 Feb 2009 18:57 Sorry, 3 weeks offline(( if it's still interest you, icq 4n7;8h8h8;0/3'3'5 (only digits) zeroh JJ [1] // Problem 1627. Join 17 Aug 2008 20:10 I use double...How to output the answer modulo 10^9? Denis Koshman Re: JJ // Problem 1627. Join 9 Sep 2008 03:54 you can try fmod() function Skam Why TLE? [2] // Problem 1627. Join 8 Sep 2008 02:27 I have a solution which runs for not more than about 2 seconds on my machine even for a test where n = m = 9 and ALL rooms are bedrooms. I can't understand why it's TLE in here! I can't say that my machine is so good (I use MSVS 2005 under WinXP on a Sempron 2400 with 256MB RAM). I can't find anywhere what are the characteristics of the judge server machine (except for the compiler), but somewhy I'm sure that they can't be so weak... And it seems that there can't be a test case worse than 81 bedrooms. So what's wrong??? Skam Re: Why TLE? [1] // Problem 1627. Join 8 Sep 2008 02:36 Well a couple of minutes after the post got it accepted... :))) Strange things... I optimized my solution just a very little bit (runs faster for just some milliseconds in the worst case). Still on my machine it runs for 2 seconds (exactly) while here it gives 3.812. But wait... I have an idea! :) I guess that the time is measured for ALL test cases together, right? :) A shame I didn't realize that earlier! :-[ :) But still it would be very interesting to know what are the characteristics of the judge server machine (for the future :)). Edited by author 08.09.2008 02:37 [SPbSU ITMO] WiNGeR Re: Why TLE? // Problem 1627. Join 8 Sep 2008 16:19 You are wrong. Time is measured for each test separately. I think the problem is in different compiler. Try to compile it with Intel C++ compiler on your machine Alias aka Alexander Prudaev determinant // Problem 1627. Join 29 Aug 2008 17:17 How to calculate Determinant without BigInteger ? Tjrac_MysTic J [1] // Problem 1627. Join 17 Aug 2008 14:13 like 1 1 . when there is one room,output what? Yermak Re: J // Problem 1627. Join 17 Aug 2008 19:27 There is one way to join all bedrooms! :) So you must output 1.
|