Search found 35 matches
- Wed Aug 09, 2006 1:22 pm
- Forum: Algorithms
- Topic: Need your help
- Replies: 2
- Views: 1240
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: 2145
- Sun Aug 06, 2006 11:33 am
- Forum: Volume 110 (11000-11099)
- Topic: 11059 - Maximum Product
- Replies: 96
- Views: 39426
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: 7193
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: 7193
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: 7193
- Wed Aug 02, 2006 12:28 pm
- Forum: Algorithms
- Topic: minimum edge for deletion
- Replies: 21
- Views: 7193
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: 1927
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: 7193
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: 7193
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: 1927
- Thu Apr 13, 2006 8:02 am
- Forum: Other words
- Topic: Who will be ACM ICPC 2006 World Final's Champion?
- Replies: 23
- Views: 9023
- Tue Jan 22, 2002 5:54 pm
- Forum: Volume 7 (700-799)
- Topic: 787 - Maximum Sub-sequence Product
- Replies: 39
- Views: 20607
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: 20607
- Thu Jan 10, 2002 4:08 pm
- Forum: Volume 7 (700-799)
- Topic: 787 - Maximum Sub-sequence Product
- Replies: 39
- Views: 20607