Search found 35 matches

by chrismoh
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...
by chrismoh
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.
by chrismoh
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...
by chrismoh
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...
by chrismoh
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...
by chrismoh
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 :)
by chrismoh
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...
by chrismoh
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...
by chrismoh
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...
by chrismoh
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...
by chrismoh
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.
by chrismoh
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
by chrismoh
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...
by chrismoh
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.
by chrismoh
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...

Go to advanced search