| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| I am really poor | Mahilewets | 1627. Join | 8 май 2017 19:38 | 8 |
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. Lol
FINALLY understand
I should just made M[row] [col] =LCM Yeah!
I tried this:
3 3
***
*.*
***
And got zero, not one!
Should correct... 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:47I realized I need not determinant of a whole matrix but just a minor. http://ideone.com/5H6ARHSubmitted corrected solution with Fractions. Buuut!! WA #8 still... |
| Hint Test #5 | Alexandru Valeanu | 1627. Join | 30 янв 2014 12:38 | 1 |
The Laplacian matrix does not have always N * M lines/columns. |
| WA1 (help please) | ApriCot{TNU} | 1627. Join | 29 дек 2011 05:40 | 2 |
оффтоп
Edited by author 29.12.2011 05:41 |
| Who can tell me the answer to this test? | kiko | 1627. Join | 11 апр 2011 03:26 | 2 |
input
9 9
.........
.........
.........
.........
.........
.........
.........
.........
......... |
| Wa on Test#5,who can tell me why? | xkszltl | 1627. Join | 20 фев 2011 18:41 | 1 |
|
| new test should be added | Pasky | 1627. Join | 16 авг 2010 11:08 | 2 |
My AC solution crashes on this test
2 2
**
** Problem statement is updated. Read "Site news". |
| hint about TL | Zayakin Andrey[PermSU] | 1627. Join | 5 авг 2010 04:07 | 1 |
Random shuffle of matrix`s rows help me to avoid TLE |
| I know how to do it now! | Зане | 1627. Join | 10 ноя 2009 12:58 | 1 |
We can use Matrix-Tree theoremd(生成树计数) to solve it!
O(N^3) |
| How to solve it with dp profile? | MSDN | 1627. Join | 14 авг 2009 13:11 | 1 |
|
| How to solve this problem? | Genesis | 1627. Join | 23 фев 2009 18:57 | 16 |
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. There is another way to solve this problem I have AC now, but can you E-mail me your method please
ykt836@gmail.com, thanks 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 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! I used JAVA's BigInteger, I can mod the determinant just before I print it One can use extended euclid to do all calculations modulo 10^9 straightforwardly 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 ? I used BigInteger and Kirgoff determinant theorem.
Dp or divide and concur approach seems unimplementing.
Interesting who used nondeterminant approach. 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? yumen , can not pass test 5. 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 I used article in wiki
with key words Kirgoff theorem 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 =))) Sorry, 3 weeks offline((
if it's still interest you, icq 4n7;8h8h8;0/3'3'5 (only digits) |
| JJ | zeroh | 1627. Join | 9 сен 2008 03:54 | 2 |
JJ zeroh 17 авг 2008 20:10 I use double...How to output the answer modulo 10^9? Re: JJ Denis Koshman 9 сен 2008 03:54 you can try fmod() function |
| Why TLE? | Skam | 1627. Join | 8 сен 2008 16:19 | 3 |
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??? 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 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 |
| determinant | Alias aka Alexander Prudaev | 1627. Join | 29 авг 2008 17:17 | 1 |
determinant Alias aka Alexander Prudaev 29 авг 2008 17:17 How to calculate Determinant without BigInteger ? |
| J | Tjrac_MysTic | 1627. Join | 17 авг 2008 19:27 | 2 |
J Tjrac_MysTic 17 авг 2008 14:13 like
1 1
.
when there is one room,output what? Re: J Yermak 17 авг 2008 19:27 There is one way to join all bedrooms! :) So you must output 1. |
