| ENG RUS | Timus Online Judge |
Обсуждение задачи 1627. JoinGeekmen Can anybody email me the dp solution? // Задача 1627. Join 1 апр 2025 14:37 I've used dp solution accepted. But I think my approach is a bit awful. So, I'd like to see some nice dp approaches. Thank you! Email: shiyuyang032421@gmail.com Mahilewets I am really poor [7] // Задача 1627. Join 8 май 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] // Задача 1627. Join 8 май 2017 16:08 Lol FINALLY understand I should just made M[row] [col] =LCM Mahilewets Re: I am really poor [5] // Задача 1627. Join 8 май 2017 17:14 Mahilewets Re: I am really poor [4] // Задача 1627. Join 8 май 2017 17:19 Yeah! I tried this: 3 3 *** *.* *** And got zero, not one! Should correct... Mahilewets Re: I am really poor [3] // Задача 1627. Join 8 май 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] // Задача 1627. Join 8 май 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] // Задача 1627. Join 8 май 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 // Задача 1627. Join 8 май 2017 19:38 Alexandru Valeanu Hint Test #5 // Задача 1627. Join 30 янв 2014 12:38 The Laplacian matrix does not have always N * M lines/columns. ApriCot{TNU} WA1 (help please) [1] // Задача 1627. Join 29 дек 2011 05:26 оффтоп Edited by author 29.12.2011 05:41 Sasha Bar [TNU] Re: WA1 (help please) // Задача 1627. Join 29 дек 2011 05:40 *WALL* kiko Who can tell me the answer to this test? [1] // Задача 1627. Join 10 апр 2011 16:01 input 9 9 ......... ......... ......... ......... ......... ......... ......... ......... ......... bsu.mmf.team Re: Who can tell me the answer to this test? // Задача 1627. Join 11 апр 2011 03:26 900397056 xkszltl Wa on Test#5,who can tell me why? // Задача 1627. Join 20 фев 2011 18:41 Pasky new test should be added [1] // Задача 1627. Join 16 авг 2010 06:13 My AC solution crashes on this test 2 2 ** ** Sandro (USU) Re: new test should be added // Задача 1627. Join 16 авг 2010 11:08 Problem statement is updated. Read "Site news". Zayakin Andrey[PermSU] hint about TL // Задача 1627. Join 5 авг 2010 04:07 Random shuffle of matrix`s rows help me to avoid TLE Зане I know how to do it now! // Задача 1627. Join 10 ноя 2009 12:58 We can use Matrix-Tree theoremd(生成树计数) to solve it! O(N^3) MSDN How to solve it with dp profile? // Задача 1627. Join 14 авг 2009 13:11 Genesis How to solve this problem? [15] // Задача 1627. Join 18 авг 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] // Задача 1627. Join 19 авг 2008 00:41 There is another way to solve this problem Genesis Re: How to solve this problem? [9] // Задача 1627. Join 19 авг 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] // Задача 1627. Join 19 авг 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? // Задача 1627. Join 19 авг 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] // Задача 1627. Join 19 авг 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] // Задача 1627. Join 19 авг 2008 18:05 One can use extended euclid to do all calculations modulo 10^9 straightforwardly Al.Cash Re: How to solve this problem? // Задача 1627. Join 21 авг 2008 14:36 Vedernikoff Sergey (HSE: EconomicsForever!) писал(a) 19 августа 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? // Задача 1627. Join 23 окт 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] // Задача 1627. Join 27 авг 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] // Задача 1627. Join 29 авг 2008 08:22 multiply their LCM Crusader Re: How to solve this problem? // Задача 1627. Join 29 авг 2008 15:03 yumen , can not pass test 5. Cat36 Re: How to solve this problem? [3] // Задача 1627. Join 5 фев 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? // Задача 1627. Join 5 фев 2009 22:18 I used article in wiki with key words Kirgoff theorem Vedernikoff Sergey (HSE: EconomicsForever!) Re: How to solve this problem? [1] // Задача 1627. Join 5 фев 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? // Задача 1627. Join 23 фев 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] // Задача 1627. Join 17 авг 2008 20:10 I use double...How to output the answer modulo 10^9? Denis Koshman Re: JJ // Задача 1627. Join 9 сен 2008 03:54 you can try fmod() function Skam Why TLE? [2] // Задача 1627. Join 8 сен 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] // Задача 1627. Join 8 сен 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? // Задача 1627. Join 8 сен 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 // Задача 1627. Join 29 авг 2008 17:17 How to calculate Determinant without BigInteger ? Tjrac_MysTic J [1] // Задача 1627. Join 17 авг 2008 14:13 like 1 1 . when there is one room,output what? Yermak Re: J // Задача 1627. Join 17 авг 2008 19:27 There is one way to join all bedrooms! :) So you must output 1.
|