[For ICPC] Links

Has some nice DP Problems : GitHUB
Has lots of links: Online Resources

[UVa] 574 - Sum It Up

Method: Backtracking
Possible optimizations: Used a map to check if a set was generated before, it takes more time than checking if the numbers were used more than they appeared in input

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

vector<int> nlist;
vector< vector<int> > finlist;
bool used[20];
map< vector<int>, bool > mp;
int btracking(int t, int sum, vector<int> temp, int k) {
    //if (!sum) solve[i].clear();

    if (sum == t) {
        if (!mp[temp]) {
            finlist.push_back(temp);
            mp[temp] = true;
        }
        return 0;
    }

    for (k ; k<nlist.size() ; k++) {
        if (!used[k]) {
            if (nlist[k]<=(t-sum)) {
                sum+=nlist[k];
                temp.push_back(nlist[k]);
                used[k] = true;
                btracking(t, sum, temp, k);
                used[k] = false;
                temp.pop_back();
                sum-=nlist[k];
            }
        }
    }

    return 0;
}

int main( void ) {

    int t, n, i, j, x;

    //freopen("574_in.txt","r+",stdin);

    while ( scanf("%d %d",&t,&n) == 2 ) {
        if (!n) break;

        printf("Sums of %d:\n",t);

        nlist.clear();
        for (i=0 ; i<n ; i++) {
            scanf("%d",&x);
            nlist.push_back(x);
            used[i] = false;
        }
        //cout << "-----> " << nlist.size() << endl;

        finlist.clear();
        vector<int> temp;
        temp.clear();
        mp.clear();
        btracking(t, 0, temp, 0);

        if (!finlist.size()) {
            printf("NONE\n");
        }

        //printf("--> %d\n",finlist.size());
        for (i=0 ; i<finlist.size() ; i++) {
            for (j=0 ; j<finlist[i].size() ; j++) {
                if (!j) printf("%d",finlist[i][j]);
                else printf("+%d",finlist[i][j]);
            }
            printf("\n");
        }

    }

    return 0;
}

[UVa] 796 - Critical Links

Method: The core idea is behind the DFS. It uses the d[u] data. low[u] contains the index of the topmost and leftmost vertex in the tree that u resides in. It is updated in two conditions. They are
1. If a vertex that is connected with u was visited earlier has a lower d[v] (d[v] is checked because u is part of v's tree then it's low[v] is still not reliable but d[v] is it's most reliable data)
2. If a fresh vertex is visited through u, then u can use that low[v] data and update itself in case v has a higher hierarchy access.
3. If low[v] > d[u], the explanation of this is that low[v] was generated during a traversal from v. During that traversal v could not find any other edge to reach u or any of it's preceding nodes. So, to reach the tree that u resides in, v must use the edge [u,v] which makes it a bridge essentially.

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
bool visited[200];
int d[200], low[200], brcount, br[200][200];
vector<int> g[200];
int dfs(int u, int parent, int depth) {
    visited[u] = true;
    d[u] = low[u] = depth;

    for (int i=0 ; i<g[u].size() ; i++) {
        int v = g[u][i];

        if (visited[v] && v!=parent) {
            low[u] = (low[u]<d[v]?low[u]:d[v]);
        }
        if (!visited[v]) {
            dfs(v, u, depth+1);
            low[u] = (low[u]<low[v]?low[u]:low[v]);
            if (low[v]>d[u]) {
                brcount++;
                br[u][v] = br[v][u] = true;
            }
        }
    }

}


int main( void ) {

    //freopen("brg.txt","r+",stdin);

    int n, v, x, e;

    while (~scanf("%d",&n)) {

        for (int i=0 ; i<200 ; i++) {
            g[i].clear();
            visited[i] = false;
            for (int j=0 ; j<200 ; j++) {
                br[i][j] = false;
            }
        }

        for (int i=0 ; i<n ; i++) {
            scanf("%d (%d)",&v,&e);
            for (int j=0 ; j<e ; j++) {
                scanf("%d",&x);
                g[v].push_back(x);
                g[x].push_back(v);
            }
        }

        brcount = 0;

        for (int i=0 ; i<n ; i++) {
            if (!visited[i]) {
                dfs(i, 0, 0);
            }
        }

        printf("%d critical links\n",brcount);
        for (int i=0 ; i<n ; i++) {
            for (int j=i+1 ; j<n ; j++) {
                if (br[i][j]) {
                    printf("%d - %d\n",i,j);
                    br[i][j] = br[j][i] = false;
                }
            }
        }
        printf("\n");
    }

    return 0;
}

[UVa] 10199 - Tourist Guide

The problem uses the concept of Articulation Points. One critical case is when the graph is already disconnected.
Method: For each vertex, I first counted it's child count (dfscount, dfsnum). Then I counted them again after disconnecting that vertex. If both of them aren't same, I incremented the Articulation Point count, because that vertex is an articulation point.

6
sugarloaf
maracana
copacabana
ipanema
corcovado
lapa
7
ipanema copacabana
copacabana sugarloaf
ipanema sugarloaf
maracana lapa
sugarloaf maracana
corcovado sugarloaf
lapa corcovado
5
guanabarabay
downtown
botanicgarden
colombo
sambodromo
4
guanabarabay sambodromo
downtown sambodromo
sambodromo botanicgarden
colombo sambodromo
6
a
b
d
c
e
f
7
a b
a d
d c
b d
c e
c f
e f
7
g
f
e
d
c
b
a
6
a b
b c
c d
d e
e f
f g
7
g
f
e
d
c
b
a
7
a b
b c
c d
d e
e f
f g
g a
7
g
f
e
d
c
b
a
6
a b
b c
c d
d e
e f
f a
6
a
b
c
d
e
f
5
a b
a f
c d
c e
d e
3
a
b
c
2
a b
b c
0

#include <cstdio>
#include <iostream>
#include <string>
#include <map>
#include <vector>


using namespace std;


bool visited[200], con[200][200];
int dfscounter;
int dfs(int v, int n) {
    visited[v] = true;
    dfscounter++;
    for (int i=1 ; i<=n ; i++) {
        if (!visited[i] && con[v][i]) {
            dfs(i, n);
        }
    }
}
map<string, int> cmap;
vector<string> lst;
int artP;
int main( ) {
    int n, e, kase=1;

    //freopen("tourist.txt","r+",stdin);
    //freopen("output.txt","w+",stdout);

    while ( cin >> n ) {

        if (!n) break;

        if (kase>1) cout << endl;

        cmap.clear();
        lst.clear();
        artP = 0;
        for (int i=1 ; i<=n ; i++) {
            string a;
            cin >> a;
            cmap[a] = i;
        }
        cin >> e;
        for (int i=1 ; i<=n ; i++) for (int j=1 ; j<=n ; j++) con[i][j] = false;
        for (int i=1 ; i<=e ; i++) {
            string a, b;
            cin >> a >> b;
            con[ cmap[a] ][ cmap[b] ] = con[ cmap[b] ][ cmap[a] ] = true;
        }
        for (map<string, int>::iterator it=cmap.begin() ; it!=cmap.end() ; it++) {
            int rcount;
            dfscounter=0;
            for (int i=1 ; i<=n ; i++) visited[i] = false;
            dfs(it->second, n);
            rcount = dfscounter;
            for (int i=1 ; i<=n ; i++) visited[i] = false;
            visited[it->second] = true;
            dfscounter=0;
            for (int i=1 ; i<=n ; i++) {
                if (con[ it->second ][i]) {
                    dfs(i, n);
                    break;
                }
            }
            if (rcount>1 && dfscounter!=rcount-1) {
                artP++;
                lst.push_back(it->first);
            }
        }

        printf("City map #%d: %d camera(s) found\n",kase++,lst.size());
        for (int i=0 ; i<lst.size() ; i++) {
            cout << lst[i] << endl;
        }

    }

}

[UVa] 315 - Network

#Articulation Points #Graph #DFS #BFS
Method:
Turn off each node and see if all the other nodes except that are visited or not using DFS
Sample I/O:

5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
5
1 2
2 3 4
4 5
0
0

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool con[200][200];
vector< pair<int, int> > edges;
bool visit[200];

void init_con(int n) {
    for (int i=0 ; i<=n ; i++)
        for (int j=0 ; j<=n ; j++)
            con[i][j] = false;
}

int dfs_visit(int s, int n) {

    int vCount = 1;

    if (visit[s]) return 0;
    visit[s] = true;

    for (int i=1 ; i<=n ; i++) {
        if (!visit[i] && con[s][i]) {
            vCount += (dfs_visit(i,n));
        }
    }
    return vCount;
}

int dfs(int s, int n) {

    int vCount = 0;

    for (int i=1 ; i<=n ; i++) {
        visit[i] = false;
    }
    visit[s] = true;

    for (int i=1 ; i<=n ; i++) {
        if (!visit[i]) {
            vCount = dfs_visit(i,n);

            return vCount;
        }
    }
    return vCount;
}

int find_bridges(int n) {
    int aps = 0, i, j;


    for (int i=1  ; i<=n ; i++) {
        if (dfs(i,n) != (n-1)) aps++;
    }


    return aps;
}
char buf[10000];
int main( void ) {


    //freopen("inp.dat","r+",stdin);

    int n, result, vtx, plc;
    char *p;

    while (scanf("%d",&n)==1 && n!=0) {
        getchar();

        init_con(n);
        edges.clear();

        while (gets(buf)) {
            if (!strcmp(buf,"0")) break;
            p = strtok(buf," ");
            sscanf(p,"%d",&plc);

            while ((p=strtok(NULL," "))) {
                sscanf(p,"%d",&vtx);

                con[plc][vtx] = con[vtx][plc] = true;
                edges.push_back(make_pair(plc,vtx));
            }
        }

        result = find_bridges(n);

        cout << result << endl;
    }


    return 0;
}

[Ubuntu Linux] Installing a program and making it accessible through CLI and Unity

So, today, I wanted to install a famous text editor called "Sublime Text 2" in my Ubuntu installation. I downloaded the tar file provided by them. Like many programs, I found no installer package or program but just the executables. Yes it was usable but I wanted more. I wanted to call the program with it's name not always navigate to the directory where I downloaded it just to use it. So I found this tutorial here and made it accessible via both Unity Dash and CLI (Terminal). I realized I often fall into this kind of problem when I'm using Ubuntu / Linux in general. So, I decided to write down the things I have to know when I'm doing such a thing.
First of all, you need to move your executables folder to the /usr/lib directory. Suppose you're too installing Sublime Text. You extract it via the tar tool like this.

tar xf Sublime\ Text\ 2\ Build\ 2181\ x64.tar.bz2

Then you get the folder "Sublime Text 2". You move it to the /usr/lib directory using this command.

sudo mv Sublime\ Text\ 2 /usr/lib/

Now you create a Symbolic Link, more like a Command to call the application via command line interface (CLI) using this

sudo ln -s /usr/lib/Sublime\ Text\ 2/sublime_text /usr/bin/sublime

Now create a launcher (icon you search for using HUD)

sudo sublime /usr/share/applications/sublime.desktop

Edit that .desktop file (specify what it does) and configure it to run Sublime Text when it's clicked on, paste all this in it, you can even spend time trying to understand it (for future applications)

[Desktop Entry]
Version=1.0
Name=Sublime Text 2
# Only KDE 4 seems to use GenericName, so we reuse the KDE strings.
# From Ubuntu's language-pack-kde-XX-base packages, version 9.04-20090413.
GenericName=Text Editor

Exec=sublime #The symbolic link
Terminal=false #Don't run it using terminal
Icon=/usr/lib/Sublime Text 2/Icon/48x48/sublime_text.png #Which icon to use
Type=Application #Type type type :P
Categories=TextEditor;IDE;Development #More info
X-Ayatana-Desktop-Shortcuts=NewWindow

[NewWindow Shortcut Group]
Name=New Window
Exec=sublime -n
TargetEnvironment=Unity

That's it, now you can run the program using terminal (without pointing to where it's stored) and click on a launcher to run it. :)

Segment Tree [ On the run ]

I'm trying to implement Segment Tree and maybe will solve some problems using it, prior to ICPC. Here's some resource that I'm using

• http://codeforces.com/blog/entry/3327
• http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
• http://apps.topcoder.com/forums/;jsessionid=2DA32E9BC12C8C331BCC8441B68E278E?module=Thread&threadID=754366&start=0&mc=4#1572259
• http://ronzii.wordpress.com/2011/07/08/segment-tree-tutorial/
• http://en.wikipedia.org/wiki/Segment_tree