Discussion @ 1627. Join @ Timus Online Judge

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)

Discussion of Problem 1627. Join