## Search found 35 matches

Wed Aug 09, 2006 1:22 pm
Forum: Algorithms
Topic: Need your help
Replies: 2
Views: 1170
After factorization you have s = p1^x1 * p2^x2 * p3^x3 * ... * pn^xn where pn are all distinct primes. Then the number of unique factors is (x1+1)*(x2+1)*(x3+1)*...*(xn+1) Your example is actually 2^2*3^2 so the answer is (2+1)*(2+1) = 9 and there are 9 divisors (you forgot 1, which is also a diviso...
Tue Aug 08, 2006 1:28 pm
Forum: Algorithms
Topic: Matrix Multiplication O(nlgn) problems
Replies: 5
Views: 1950
Yes, due to Hu and Shing.

http://historical.ncstrl.org/litesite-d ... 81-875.pdf

Its a long paper.
Sun Aug 06, 2006 11:33 am
Forum: Volume 110 (11000-11099)
Topic: 11059 - Maximum Product
Replies: 96
Views: 37347
Consider the list as being a sequence of shorter lists that are simply separated by zeros. We can compute the maximal product of each list in linear time by simply going through all numbers sequentially and storing the maximum (in terms of absolute value) positive and negative products that can be o...
Sat Aug 05, 2006 8:33 am
Forum: Algorithms
Topic: minimum edge for deletion
Replies: 21
Views: 6681
Hi Dimitar, it solves the problem because (1) Do a DFS traversal, generate the DFS tree. The initial number of edges you start with is equal to the number of edges in the tree, which is equal to the number of vertices - 1, if the graph is connected. Since the algorithm only decreases the number of e...
Sat Aug 05, 2006 5:35 am
Forum: Algorithms
Topic: minimum edge for deletion
Replies: 21
Views: 6681
since the graph is connected and so there must be an odd number of odd vertices A graph *never* has an odd number of odd vertices, since that would imply that total degree is odd. I think what you are saying is that since the total degree of a graph is even, hence for every vertex to have odd degre...
Wed Aug 02, 2006 8:37 pm
Forum: Algorithms
Topic: minimum edge for deletion
Replies: 21
Views: 6681
Hmm. That's true.

So you can indeed solve this with a minimum cost matching.

thanks for the tip
Wed Aug 02, 2006 12:28 pm
Forum: Algorithms
Topic: minimum edge for deletion
Replies: 21
Views: 6681
asif_rahman0: I coded a simple BFS with an adjacency matrix (which isn't the most efficient) and got Accepted in about 0.2s. Hopefully you aren't having an infinite loop or something. DJWS: I don't think you can transform the problem directly to a chinese postman. Chinese postman is when you want to...
Wed Aug 02, 2006 12:22 pm
Forum: Volume 10 (1000-1099)
Topic: 1049 - Remember the A La Mode!
Replies: 3
Views: 1788
Well, a simple min/max cost max flow formulation is this: Have a super-source s. From s to every pie have an edge with cost 0 and capacity the number of pies. Have a super-sink t. From every ice-cream to t have an edge with cost 0 and capacity the number of ice-creams. For every (pie, ice-cream) com...
Tue Aug 01, 2006 3:59 am
Forum: Algorithms
Topic: minimum edge for deletion
Replies: 21
Views: 6681
10968 is different. Note that 10968 has at most 2 cities that have odd degree. So: If 0 cities have odd degree, we're done. If 1 city has odd degree, there is no solution. If 2 cities have odd degree, find the shortest path between the two cities and burn all the roads in this shortest path. To ensu...
Mon Jul 31, 2006 9:39 pm
Forum: Algorithms
Topic: minimum edge for deletion
Replies: 21
Views: 6681
I haven't really thought about the original problem, but there could be a simple solution to it. For the IOI 2006 practice, here's a simple algorithm that solves it: (1) Do a DFS traversal, generate the DFS tree. (2) If all nodes in the tree have odd degree, stop (3) Choose the node with greatest he...
Mon Jul 31, 2006 1:37 pm
Forum: Volume 10 (1000-1099)
Topic: 1049 - Remember the A La Mode!
Replies: 3
Views: 1788
Why is the number of vertices too large?

If you use hungarian, maybe, because you might have to expand each vertex into many vertices.

But not if you use min-cost max-flow.

My team in the 2006 world finals got accepted with a direct min-cost max-flow implementation.
Thu Apr 13, 2006 8:02 am
Forum: Other words
Topic: Who will be ACM ICPC 2006 World Final's Champion?
Replies: 23
Views: 8528
Official results:

1. Saratov State University
2. Jagiellonian University - Krakow
3. Altai State Technical University
4. University of Twente
Tue Jan 22, 2002 5:54 pm
Forum: Volume 7 (700-799)
Topic: 787 - Maximum Sub-sequence Product
Replies: 39
Views: 19273
Ok, let's see... we know that other than at zeroes, the absolute value of the multiple always increases. So we can store the maximal (absolute value) negative and positive product for that current subsequence (a subsequence started and ended by zeroes, for convenience it is always correct to place a...
Fri Jan 11, 2002 11:47 am
Forum: Volume 7 (700-799)
Topic: 787 - Maximum Sub-sequence Product
Replies: 39
Views: 19273
Storing P[1],P[2],...P[n] is unnecessary. That algorithm still runs in O(n^2) time.

Linear time solution uses a sorta "greedy" method.
Thu Jan 10, 2002 4:08 pm
Forum: Volume 7 (700-799)
Topic: 787 - Maximum Sub-sequence Product
Replies: 39
Views: 19273
I haven't solved it yet, but I have thought of an O(n) algorithm which I am sure is correct.

Its just very irritating to implement big numbers...