JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Round Tables External Competitions CodeSprint - 48 hour programming contest [ 1 2 ]    NEXT >
 CodeSprint - 48 hour programming contest | Reply Hey, there's an exciting programming contest, CodeSprint (codesprint.interviewstreet.com) happening on Jan 6. It's an interesting concept where the best performers are spotted by companies like facebook, etc.FYI: One of the organizers is my school senior :)Edit: Link is fixed now, thank you for letting us know
 Re: CodeSprint - 48 hour programming contest (response to post by chakradarraju) | Reply The link is not working.
 Re: CodeSprint - 48 hour programming contest (response to post by victor.juquila) | Reply It's working perfectly for me.
 Re: CodeSprint - 48 hour programming contest (response to post by Phoenix.) | Reply The link was broken then, I fixed it.
 Re: CodeSprint - 48 hour programming contest (response to post by chakradarraju) | Reply The problems were awesome. Thanks for a contest with both algorithms and real world problems . Can you explain the solution for Count Strings and Polygons ?
 Re: CodeSprint - 48 hour programming contest (response to post by innocentboy2) | Reply Polygon in pseudocode:`For each polygon: ret = 0 For each horizontal edge of the polygon (X1, Y) -> (X2, Y): if (X1 < X2): ret -= number of points that lies above this edge else: ret += number of points that lies above this edge print ret`The "number of points that lies above this edge" can be computed efficiently. I used 2d fenwick tree.===Could anyone describe solution for Crab Graphs?
 Re: CodeSprint - 48 hour programming contest (response to post by dolphinigle) | Reply Set the vertices and edges in a graph according to the constraints of crab graph and then apply any flow algo.
 Re: CodeSprint - 48 hour programming contest (response to post by dolphinigle) | Reply I was also thinking about using a 2d fenwick tree, but i thought this would require a datastructure with 200.000*200.000 values, because coordinates can go until 200.000.What is the size of your used tree?
 Re: CodeSprint - 48 hour programming contest (response to post by Kornacker) | Reply O(N log N). You can precompute the size of each fenwick tree before and use a suitable mapping (map<> in C++ since it supports upper_bound). Each point will be included in at most log N fenwick trees.
 Re: CodeSprint - 48 hour programming contest (response to post by chakradarraju) | Reply So, the subgraph we pick is not the subgraph induced by the vertices of the subgraph, but instead we're allowed to add the edges to the subgraph as we please?P.S. / Rant: The clarification guy in the #irc chat room told me that it's induced
 Re: CodeSprint - 48 hour programming contest (response to post by dolphinigle) | Reply Can you paste your code here . I stuck in compressing 2D matrices . Thanks in advance.
 Re: CodeSprint - 48 hour programming contest (response to post by dolphinigle) | Reply Yes, the sub graph was induced by the vertices you had to build the flow graph accordingly..Edit:induced by vertices and edges(the person who clarified might had confused your question/had a typo,)
 Re: CodeSprint - 48 hour programming contest (response to post by dolphinigle) | Reply ```#include #include #include #include #include using namespace std;   // the maximum number of vertices #define NN 300 #define INF 10000000   // adjacency matrix (fill this up) int cap[NN][NN];   // flow network int fnet[NN][NN];   // BFS int q[NN], qf, qb, prv[NN];   int fordFulkerson( int n, int s, int t ) { // init the flow network memset( fnet, 0, sizeof( fnet ) );   int flow = 0;   while( true ) { // find an augmenting path memset( prv, -1, sizeof( prv ) ); qf = qb = 0; prv[q[qb++] = s] = -2; while( qb > qf && prv[t] == -1 ) for( int u = q[qf++], v = 0; v < n; v++ ) if( prv[v] == -1 && fnet[u][v] - fnet[v][u] < cap[u][v] ) prv[q[qb++] = v] = u;   // see if we're done if( prv[t] == -1 ) break;   // get the bottleneck capacity int bot = 0x7FFFFFFF; for( int v = t, u = prv[v]; u >= 0; v = u, u = prv[v] ) bot = min(bot, cap[u][v] - fnet[u][v] + fnet[v][u]);   // update the flow network for( int v = t, u = prv[v]; u >= 0; v = u, u = prv[v] ) fnet[u][v] += bot;   flow += bot; }   return flow; }   #define A(x) ((x) * 2 + 2) #define B(x) ((x) * 2 + 3) #define source 0 #define target 1   int c, n, m, t, a, b;   int main() { for(cin >> c; c--; ) { cin >> n >> t >> m; //cerr << n << " " << t << " " << m << endl; memset(cap, 0, sizeof cap); for(int i = 0; i < m; i ++) { cin >> a >> b; a--; b--; cap[A(a)][B(b)] = INF; cap[A(b)][B(a)] = INF; } for(int i = 0; i < n; i ++) { cap[source][A(i)] = t; cap[B(i)][target] = 1; } int result = fordFulkerson(2 * n + 2, source, target); cout << result << endl; } return 0; } ```
 Re: CodeSprint - 48 hour programming contest (response to post by chakradarraju) | Reply Thanks, your algorithm clarifies that the subgraph is not induced by the vertex set, since it outputs 3 for this case:3 2 31 22 31 3Whereas the subgraph induced by all three nodes should consist of all the edges, which forms a triangle, which is not a crab.For definition of "subgraph induced by a set of vertices / vertex set", seehttp://en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphsorhttp://mathworld.wolfram.com/Vertex-InducedSubgraph.htmlP.S.: So I guess the clarification guy also didn't know this definition. Too bad :(
 Forums Round Tables External Competitions CodeSprint - 48 hour programming contest Previous Thread  |  Next Thread [ 1 2 ]    NEXT >