ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1627. Join

How to solve this problem?
Posted by Genesis 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.
Re: How to solve this problem?
Posted by [SPbSU ITMO] WiNGeR 19 Aug 2008 00:41
There is another way to solve this problem
Re: How to solve this problem?
Posted by Genesis 19 Aug 2008 06:25
I have AC now, but can you E-mail me your method please
ykt836@gmail.com, thanks
Re: How to solve this problem?
Posted by emotional blind 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
Re: How to solve this problem?
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!
Re: How to solve this problem?
Posted by Genesis 19 Aug 2008 16:59
I used JAVA's BigInteger, I can mod the determinant just before I print it
Re: How to solve this problem?
One can use extended euclid to do all calculations modulo 10^9 straightforwardly
Re: How to solve this problem?
Posted by Al.Cash 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 ?
Re: How to solve this problem?
Posted by Crusader 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?
Re: How to solve this problem?
Posted by Genesis 29 Aug 2008 08:22
multiply their LCM
Re: How to solve this problem?
Posted by Crusader 29 Aug 2008 15:03
yumen , can not pass test 5.
Re: How to solve this problem?
Posted by svr 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.
Re: How to solve this problem?
Posted by Cat36 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
Re: How to solve this problem?
Posted by svr 5 Feb 2009 22:18
I used article in wiki
with key words  Kirgoff theorem
Re: How to solve this problem?
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 =)))
Re: How to solve this problem?
Posted by Cat36 23 Feb 2009 18:57
Sorry, 3 weeks offline((
if it's still interest you, icq 4n7;8h8h8;0/3'3'5 (only digits)