Search found 35 matches

by chrismoh
Tue Sep 05, 2006 3:53 am
Forum: Algorithms
Topic: graph problems
Replies: 6
Views: 2454

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 the same c...
by chrismoh
Sat Sep 02, 2006 8:03 pm
Forum: Volume 110 (11000-11099)
Topic: 11081 - Strings
Replies: 35
Views: 19521

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 :wink:
by chrismoh
Fri Sep 01, 2006 7:13 pm
Forum: Algorithms
Topic: graph problems
Replies: 6
Views: 2454

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 in ...
by chrismoh
Thu Aug 31, 2006 7:00 pm
Forum: Algorithms
Topic: problem from us open 2005
Replies: 1
Views: 1210

[ 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 angl...
by chrismoh
Thu Aug 31, 2006 2:54 pm
Forum: Volume 100 (10000-10099)
Topic: 10011 - Where Can You Hide?
Replies: 58
Views: 12674

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 10 ...
by chrismoh
Wed Aug 30, 2006 6:21 pm
Forum: Algorithms
Topic: MinCost MaxFlow code
Replies: 20
Views: 15181

(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) >= ...
by chrismoh
Tue Aug 29, 2006 6:11 am
Forum: Volume 100 (10000-10099)
Topic: 10011 - Where Can You Hide?
Replies: 58
Views: 12674

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" ); continue...
by chrismoh
Mon Aug 28, 2006 10:45 am
Forum: Volume 109 (10900-10999)
Topic: 10949 - Kids in a Grid
Replies: 30
Views: 11831

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 ...
by chrismoh
Fri Aug 25, 2006 3:43 am
Forum: Algorithms
Topic: MinCost MaxFlow code
Replies: 20
Views: 15181

(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),...
by chrismoh
Wed Aug 23, 2006 4:51 am
Forum: Volume 100 (10000-10099)
Topic: 10005 - Packing polygons
Replies: 49
Views: 15276

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 possible...
by chrismoh
Wed Aug 23, 2006 4:43 am
Forum: Volume 100 (10000-10099)
Topic: 10040 - Ouroboros Snake
Replies: 20
Views: 4467

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 itse...
by chrismoh
Mon Aug 14, 2006 9:03 pm
Forum: Algorithms
Topic: Coloring a Partially Colored Graph
Replies: 1
Views: 1236

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 pro...
by chrismoh
Sun Aug 13, 2006 2:22 am
Forum: Volume 110 (11000-11099)
Topic: 11065 - A Gentlemen's Agreement
Replies: 19
Views: 8726

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.
by chrismoh
Sun Aug 13, 2006 2:11 am
Forum: Volume 110 (11000-11099)
Topic: 11065 - A Gentlemen's Agreement
Replies: 19
Views: 8726

Max matching only works for bipartite graphs.
by chrismoh
Sat Aug 12, 2006 3:25 pm
Forum: ACM ICPC Archive Board
Topic: how to solve this problem?
Replies: 2
Views: 2044

I think there's a simple cubic time solution.

Just think :)

Go to advanced search