Question.
Can you tell me an algorithm wich gives the minimum number of vertices that need to be deleted to make vertices v & u disconnected.
Let's see how good you are in algorithms
A Question about graphs
Moderator: Board moderators
-
Alessandro
- New poster
- Posts: 27
- Joined: Mon Jun 14, 2004 10:33 pm
- Location: Latina, Italy
Maybe I'm completely wrong, now I write my first ideas...
1. Assign edges the weight INFINITY
2. Double the nodes and connect them with a ghost-edge of weight 1
3. Find minimum cut (running maximum flow)
Don't bother me if I'm saying a stupid thing, now I'm tired!
1. Assign edges the weight INFINITY
2. Double the nodes and connect them with a ghost-edge of weight 1
3. Find minimum cut (running maximum flow)
Don't bother me if I'm saying a stupid thing, now I'm tired!
Alessandro Piva, Member of the Italian Team at the International Olimpiad in Informatics 2004
Email: alex.ander@infinito.it
Email: alex.ander@infinito.it
-
Alessandro
- New poster
- Posts: 27
- Joined: Mon Jun 14, 2004 10:33 pm
- Location: Latina, Italy
Wow, I got it right!
Just see the "Network Flow" text at the USACO training program... Near the end you can find the "sample problems", and there is Telecowmunication, with the method I described!
Can you do me a favor, for gratitude ?
How can I solve "All Latin Squares", section 5.1 ? You're at 5.4, you've already done it.
Ciao
Alessandro
Just see the "Network Flow" text at the USACO training program... Near the end you can find the "sample problems", and there is Telecowmunication, with the method I described!
Can you do me a favor, for gratitude ?
How can I solve "All Latin Squares", section 5.1 ? You're at 5.4, you've already done it.
Ciao
Alessandro
Alessandro Piva, Member of the Italian Team at the International Olimpiad in Informatics 2004
Email: alex.ander@infinito.it
Email: alex.ander@infinito.it
Hi.
I was at training camp for IOI so I couldn't answer your message earlier.
I send analysis from USACO.
Leonhard Euler introduced latin squares in 1783 as a "nouveau espece de carres magiques", a new kind of magic squares. Combinatorists calculated the numbers of latin squares (up to 7x7) on paper for, apparently, mental challenges, before the invention of computer.
In this problem, we must count the number of Latin square whose first row is {1, 2, 3 ... N}. One approach is a recursive brute-force search: place every appropriate number in a position and "re-curse" on the next position; when a complete latin square is formed, increment our total number. This algorithm would work fine for N<=6 but would be too slow for N=7. Therefore some prunings/optimizations are required:
1. A latin square whose first row and column are both {1, 2, 3 ... N} is called a reduced (or normalized) latin square. It is useful because for any latin square, permutating its rows and columns will produce many different latin squares. Let L(K) represent the number of KxK reduced latin square and N(K) represent the total number of KxK latin square, it is obvious that
N(K) = L(K) * N! * (N-1)!
since for any reduced latin square, you can permute its rows (N!) and columns ((N-1)!) and get N!*(N-1)! different latin squares. Likewise, M(K) = L(K) * (N-1)! where M(K) is the number of KxK latin square of our interest. Therefore, we only need to search and count the reduced latin square.
2. For the second row (the first row is {1, 2, 3 ... N}): the number of latin square (reduced or not reduced) whose row 2 column 2 is 3 is same with number of latin square whose row 2 column 2 is 4, 5, or ... N. We can take advantage of this fact; the idea is better illustrated in the code below.
3. When we filled the kth row of a latin square (k<N), we know for a fact that the (k+1)th row could be filled. Therefore, we only need to search until N-1 row.
I was at training camp for IOI so I couldn't answer your message earlier.
I send analysis from USACO.
Leonhard Euler introduced latin squares in 1783 as a "nouveau espece de carres magiques", a new kind of magic squares. Combinatorists calculated the numbers of latin squares (up to 7x7) on paper for, apparently, mental challenges, before the invention of computer.
In this problem, we must count the number of Latin square whose first row is {1, 2, 3 ... N}. One approach is a recursive brute-force search: place every appropriate number in a position and "re-curse" on the next position; when a complete latin square is formed, increment our total number. This algorithm would work fine for N<=6 but would be too slow for N=7. Therefore some prunings/optimizations are required:
1. A latin square whose first row and column are both {1, 2, 3 ... N} is called a reduced (or normalized) latin square. It is useful because for any latin square, permutating its rows and columns will produce many different latin squares. Let L(K) represent the number of KxK reduced latin square and N(K) represent the total number of KxK latin square, it is obvious that
N(K) = L(K) * N! * (N-1)!
since for any reduced latin square, you can permute its rows (N!) and columns ((N-1)!) and get N!*(N-1)! different latin squares. Likewise, M(K) = L(K) * (N-1)! where M(K) is the number of KxK latin square of our interest. Therefore, we only need to search and count the reduced latin square.
2. For the second row (the first row is {1, 2, 3 ... N}): the number of latin square (reduced or not reduced) whose row 2 column 2 is 3 is same with number of latin square whose row 2 column 2 is 4, 5, or ... N. We can take advantage of this fact; the idea is better illustrated in the code below.
3. When we filled the kth row of a latin square (k<N), we know for a fact that the (k+1)th row could be filled. Therefore, we only need to search until N-1 row.