JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 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 contest has started. you can join now.
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 <cstring>
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
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 3
1 2
2 3
1 3

Whereas 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", see
http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs
or
http://mathworld.wolfram.com/Vertex-InducedSubgraph.html

P.S.: So I guess the clarification guy also didn't know this definition. Too bad :(
[ 1 2 ]    NEXT >

RSS