OJ Board

Color every node using DFS as "black" or "white".

Color the root black, make it the current node, and do the following:


For every node connected to the current node
If node is uncolored
Color it with the opposite color of the current node
Recursively do a DFS on it
Else If node is colored ...

Well, my rather inefficient ACed solution (I mod 10007 everywhere, instead of just doing a mod where its needed) is O(n^3).

So yes, there is an O(n^3) solution... you just need to look for it

Checking if a graph is bipartite is basically checking if a graph can be 2-colored.

This can be done with DFS in linear time.

I'm not really sure what your second problem is, but it sounds like the Maximum Cut problem which is NP-hard.

A simple 2-approximation heuristic is simply to assign nodes ...

[ Edit ] Original Algorithm was incorrect.

This is a shortest path problem.

Basically you want to find the shortest path from yourself to yourself.

The only trick is the requirement that you must travel 360 deg around the world.

I assume that angle 0 is the starting position (you can adjust all ...

Still can't get AC on it.

Can I have an AC's solution output for:


21
3 4 5 10 1
3 4 5 10 -1
3 4 5 -5 1
0 5 5 6 1
1 4 2 5 5
1 4 2 6 5
1 4 2 4 5
4 4 4 3 3
4 4 4 5 5
4 4 4 6 4
-1 -1 0.01 0 0
5 5 5 0 0
5 0 5 0 0
3 4 5 6 8
3 4 5 6 9
3 4 5 7 8
10 10 14.13 20 20
10 10 14.13 0.1 0.1
10 10 14.13 60 60
10 ...

(1) Assuming no negative cycle, the following inequality ALWAYS holds:

d(s,v) <= d(s,u) + c(u,v) --- (1)

for all u,v where s is the starting vertex, d(s,u) and d(s,v) minimum distances to vertices u and v and c(u,v) the cost of the edge between u and v.

Rearranging gives c(u,v) + d(s,u) - d(s,v ...

I'm still getting a WA on this, unfortunately...

The following code segment causes an RE, leading me to suspect that the input does not follow the descriptions:



scanf ( " %Lf %Lf %Lf %Lf %Lf", &mid.x, &mid.y, &r, &b.x, &b.y );

if ( dist ( mid, b ) < r ) {
assert ( 0 );
printf ( "0.000\n ...

The min(m,n-p) bound comes from the fact that there are most min(m,n-p) dominant matches per contour.

Unfortunately, most papers I have found don't mention how to get min(m,n-p) time per contour - they just state it as fact. (Getting O(m) is really easy, though). And I don't know where you can find ...

(1) Finding the negative cycle is a very short extension of Bellman-Ford. This isn't really efficient, though.

(2) I haven't seen Igor's code yet, but I'm suspecting he is using the Cheapest Augmenting Path algorithm. The basic idea is to weight each node with a "potential", and for each edge (u,v ...

And over a year later...

I assume below that all circles have 3 points on the boundary, thus ignoring > 3 points and the case where there are 2 points on the minimal circle's boundary (in this case the 2 points are on the diameter).

To find minimal R, O(n^3) is hard to beat. Simply take all ...

Read up on de bruijn sequences.

The simple way to think about it as an Eulerian circuit is for an n-bit number, think of all 2^(n-1) bit numbers as nodes and each node has two edges to represent the next bit - 0 and 1.

So, for example, for n = 3, we have four nodes:

00 01 10 11

00 has edge 0 to ...

So you have n colors?

Since the maximum degree of a vertex is n-1, this is always possible. (Actually, if you have n vertices, you can just color all of them a different color).

If you're asking about the case where n is just the number of colors, and not the number of vertices in the graph, the ...

Yes, although there are max matching algorithms in general graphs (blossom shrinking and the like), the theorem

Maximum Independent Set = n - MaxMatch

only works in bipartite graphs.

Max matching only works for bipartite graphs.

I think there's a simple cubic time solution.

Just think