OJ Board

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...

Yes, due to Hu and Shing.

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

Its a long paper.

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...

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...

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...

Hmm. That's true.

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

thanks for the tip

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...

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...

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...

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...

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.

Official results:

1. Saratov State University
2. Jagiellonian University - Krakow
3. Altai State Technical University
4. University of Twente

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...

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.

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...