## Search found 35 matches

- Tue Sep 05, 2006 3:53 am
- Forum: Algorithms
- Topic: graph problems
- Replies:
**6** - Views:
**2536**

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

- Sat Sep 02, 2006 8:03 pm
- Forum: Volume 110 (11000-11099)
- Topic: 11081 - Strings
- Replies:
**35** - Views:
**19905**

- Fri Sep 01, 2006 7:13 pm
- Forum: Algorithms
- Topic: graph problems
- Replies:
**6** - Views:
**2536**

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

- Thu Aug 31, 2006 7:00 pm
- Forum: Algorithms
- Topic: problem from us open 2005
- Replies:
**1** - Views:
**1255**

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

- Thu Aug 31, 2006 2:54 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10011 - Where Can You Hide?
- Replies:
**58** - Views:
**13167**

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

- Wed Aug 30, 2006 6:21 pm
- Forum: Algorithms
- Topic: MinCost MaxFlow code
- Replies:
**20** - Views:
**15511**

(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) >= ...

- Tue Aug 29, 2006 6:11 am
- Forum: Volume 100 (10000-10099)
- Topic: 10011 - Where Can You Hide?
- Replies:
**58** - Views:
**13167**

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

- Mon Aug 28, 2006 10:45 am
- Forum: Volume 109 (10900-10999)
- Topic: 10949 - Kids in a Grid
- Replies:
**30** - Views:
**12177**

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

- Fri Aug 25, 2006 3:43 am
- Forum: Algorithms
- Topic: MinCost MaxFlow code
- Replies:
**20** - Views:
**15511**

(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),...

- Wed Aug 23, 2006 4:51 am
- Forum: Volume 100 (10000-10099)
- Topic: 10005 - Packing polygons
- Replies:
**49** - Views:
**15828**

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

- Wed Aug 23, 2006 4:43 am
- Forum: Volume 100 (10000-10099)
- Topic: 10040 - Ouroboros Snake
- Replies:
**20** - Views:
**4666**

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

- Mon Aug 14, 2006 9:03 pm
- Forum: Algorithms
- Topic: Coloring a Partially Colored Graph
- Replies:
**1** - Views:
**1268**

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

- Sun Aug 13, 2006 2:22 am
- Forum: Volume 110 (11000-11099)
- Topic: 11065 - A Gentlemen's Agreement
- Replies:
**19** - Views:
**8855**

- Sun Aug 13, 2006 2:11 am
- Forum: Volume 110 (11000-11099)
- Topic: 11065 - A Gentlemen's Agreement
- Replies:
**19** - Views:
**8855**

- Sat Aug 12, 2006 3:25 pm
- Forum: ACM ICPC Archive Board
- Topic: how to solve this problem?
- Replies:
**2** - Views:
**2132**