10766 - Organising the Organisation

[Cho]

The input of the three integers should be n, k, m instead of n, m, k, right?
And I can't get 8 possible hierarchies for the second input:

Code: Select all

4 1 1
1 4

All the 6 possible hierarchies I can get are as follow:

Code: Select all

1-2-3-4

1-2-4-3

1-3-2-4

1-3-4-2

1-2-4
|
3

1-3-4
|
2

Which two hierarchies do I miss?

[Per]

The input of the three integers should be n, k, m instead of n, m, k, right?

Yup, there was a clarification about this in the contest. I'll mail Carlos and ask him to fix it.

Which two hierarchies do I miss?

Assuming I understood your notation correctly, they are:

Code: Select all

1-2-3
  |
  4

1-3-2
  |
  4

[Cho]

I realize that I can ignore the Central Management division. I just need to count the number of the spanning tree of a graph. I use matrix tree theorem to count it. But I got WA. Is my approach correct?

[Cho]

Can somebody post some input/output for this problem?
Or briefly describe the idea to solve this problem?

[Per]

Sounds like you have the right approach.
Here's a test case:

Code: Select all

10 17 6
9 6
8 10
10 2
3 6
10 7
2 6
7 3
5 3
3 10
9 8
5 1
8 7
2 3
7 6
5 8
4 10
2 4

[Edit: Answer is 819224.]

There is one slightly dirty trick in the problem, which I semi-regret that I put there. Be sure you handle test cases like this one correctly:

Code: Select all

4 3 1
1 4
4 1
1 4

Answer is 8.
Also, depending on how you compute the answer, make sure you don't get precision issues.

[Cho]

Here's a test case:

Code: Select all

10 17 6
9 6
8 10
10 2
3 6
10 7
2 6
7 3
5 3
3 10
9 8
5 1
8 7
2 3
7 6
5 8
4 10
2 4

Answer is 1147243.

My code output 819224 instead of 1147243. I've printed out the matrix and compute the determinant by Maple. The result is also 819224. What's the tricky part in this test case?

[Per]

Ooops, sorry, the answer should be 819224, you are correct. My input generation program outputted a number to standard err and I thought it was the answer, but I remembered incorrectly.

[Cho]

In order to handle the precision, I compute the determinant modulo five different primes which are all between 1000 and 1100. Then the answer is constructed using chinese remainder theorem.

hmm... then I must be fallen into your "slightly dirty trick".
Can you give some more hint on that?

[Per]

It was illustrated by the second case I posted, where the same pair occured many times. If you want, you can send me your solution and I'll try to see what's wrong with it.

[Krzysztof Duleba]

I use long doubles to compute the determinant and it was enough to get AC (doubles were not, though).

[Cho]

I use long doubles to compute the determinant and it was enough to get AC (doubles were not, though).

I wonder if the determinant of a fairly large matrix can be computed by using just long double. Even the final answer is less than 10^15, the intermediate values during the computation could be very large.

For example, the determinant of the following 2x2 matrix is just 1:
10^12+1 10^12
10^12+2 10^12+1

[Krzysztof Duleba]

I wonder if the determinant of a fairly large matrix can be computed by using just long double.

But earlier:

I've printed out the matrix and compute the determinant by Maple.

Maple is likely to use just doubles, like most math packages, you know. It's obvious that many things can't be done right with limited precision of [long] doubles, but usually they are just good enough.

[Cho]

Maple is likely to use just doubles, like most math packages, you know.

I know most math packages compute numerically. However Maple computes "Symbolically". According to the reference I'm reading, "Maple never changes spontaneously arithmetic expressions into decimal numbers... Maple can handle big integer with maximum number of digits up to 2^28-8 = 268435448". To verify this, I've just used Maple to compute the determinant of a 100x100 diagonal matrix with 1 to 100 as the entries in the diagonal. It can output the exact value of 100! which is a number of 158 digits.

It's obvious that many things can't be done right with limited precision of [long] doubles, but usually they are just good enough.

True. But for this problem, how could you guarantee all the intermediate values during computing the determinant could be stored in long double?

[Krzysztof Duleba]

But for this problem, how could you guarantee all the intermediate values during computing the determinant could be stored in long double?

I can't. But I gave it a try and it passed. If it didn't, I would switch to BigInts.

[..]

Hi all, I also get AC using long double.
My method is to use long double to compute the determinant for many times, and then take the average of them. As in the original n*n matrix, you have n^2 ways to make a (n-1)*(n-1) to compute determinant.

This trick (luckily) helps me to overcome the precision error