Decoding the message UVA solution 11220

This is an easy problem from uva judge http://uva.onlinejudge.org/external/112/11220.html

Ad hoc problem

How I did it

• Read the number of cases.
• Read a line at a time with getline.
• Filter the words using an sstream(stringstream) object and save each word in a vector<string>.
• Traverse the vector and develop the output word.
• Save the word in a output vector.
• When I find an empty line I print the output vector content.

Hints

• Cases T  (1 ≤ T ≤ 30). Total lines per case N (1 ≤ N ≤ 100 ). Each line has  M words (1 ≤ M ≤ 30).
• At least we will have one word in the output.
• Print a blank line BETWEEN cases. In the last case you must not print a blank line.

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <sstream>
using namespace std;
int main(){
int casos, index, flag = 0, answer = 1;
string cad, output,word, input;
stringstream ss;
scanf("%d",&casos);
getline(cin, cad);
getline(cin,cad);//Empty line
while(casos--){

    vector<string> result;
    while(getline(cin,cad))
    {
        vector<string> vec;
        if(cad.size() == 0)
           break;

        ss<<cad;
        while(ss>>input)
              vec.push_back(input);

        index = 0;
        output = "";

        for(int x=0; x<vec.size(); x++)
        {
            word = vec[x];
            if(index<word.size())
            {
             output += word[index];
             index++;
            }
        }
        result.push_back(output);
        ss.clear();
    }
    if(!flag)
       flag = 1;
    else
        printf("\n");
    printf("Case #%d:\n",answer++);
    for(int h=0; h<result.size(); h++)
        printf("%s\n", result[h].c_str());
}
return 0;
}

Pesky Palindromes uva Solution 353

This is an easy problem from uva judge http://uva.onlinejudge.org/external/3/353.html

How I did it

• Read the string.
• I generate all the possible words for the string.
• Check word by word if they are palindromes.
• If the word is a palindrome insert into a STL set. (We need to filter all diferet palindromes).
• Print the size of the STL set

Hints

• Find all the different subset. For example for “aba”, the diferent subset are a,b,ab,ba. And the output is 2. We only count the letter ‘a’ one time.
• The max input size need 3204 combinations. Really small
• This is general for all inputs. Check this example. Input : “Fabian”

f, a, b, i, a, n           Size 6

fa, ab, bi, ia, an     Size 5

fab, abi, bia, ian    Size 4

fabi, abia, bian      Size 3

fabia, abian           Size 2

fabian                     Size 1

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
string cad;
set<string>mySet;

bool isPalindrome(string str){
string tmp = str;
reverse(tmp.begin(),tmp.end());
if(str == tmp)
   return true;
return false;
}

void generateCombination(int strWord, int index){
string strTmp = ""; //cout<<index<<endl;
   for(int x=index; x<cad.size(); x++)
   {
        strTmp += cad[x];
        if(strTmp.size() == strWord)
        {
            if(isPalindrome(strTmp))
               mySet.insert(strTmp);
            strTmp = "";
            if(index<cad.size()-1)
               generateCombination(strWord,++index);

            return;

        }
        if(index == cad.size()-1 || x == cad.size()-1)
           return;
   }
}

void getLetter(){
string letter = "";
    for(int x=0; x<cad.size(); x++)
    {
        letter += cad[x];
        mySet.insert(letter);
        letter = "";
    }
}

int main(){
int wordSize;
int initPos;

while(cin>>cad){

    if(cad.size() == 1)
       printf("The string \'%s\' contains 1 palindromes.\n",cad.c_str());
    else{
         wordSize = 2;
         initPos = 0;         while(wordSize<=cad.size()){
            generateCombination(wordSize, initPos);
            wordSize++;
         }
         getLetter();
         printf("The string \'%s\' contains %d palindromes.\n",cad.c_str(), mySet.size());
         mySet.clear();
        }
}
return 0;
}

Graph representation and graph traversal

A graph is a data structure that represent a collection of vertices and edges, that store connectivity information,

I will show how to represent a graph in 2 ways, and two graph traversal algorithms dfs, bfs. Finally i will add the snippets to load a graph, and dfs, bfs algorithms in c++.

You can get more theory information here: http://en.wikipedia.org/wiki/Graph_theory

Representation

A Adjacency matrix: Is a connectivity table represented in a 2D matrix int AdjMat[v][v]. For an unweighted graph we can set AdjMat[i][j] = 1 if there is connectivity otherwise the weigth.

B Adjacency List: Is a vector of vector of pairs. Here we store the information of the nodes in pairs. Neighbor and weight.

Graph Traversal

This is a video that explains in a clearly way two graph traversal algorithms, Deep First Search, Breadth First Search.

Snippets

BFS

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define MAXN    500

using namespace std;

vector < vector <int> > graph(MAXN);
bool discovered[MAXN];//keeps track if a node has been reached
int parent[MAXN];//stores the nodes ancestor that discovered it for the first time
int distances[MAXN];//stores the distance to reach each node from the source

void init_graph(int vertices)
{
    int i;
    for(i = 0; i < vertices; i++)
    {
        discovered[i] = false;
        graph[i].clear();
        distances[i] = parent[i] = -1;
    }
}

void read_graph(int edges)
{
    int vertex1,  vertex2;
    int i;
    for(i = 0; i < edges; i++)
    {
        scanf("%d %d", &vertex1, &vertex2);
        graph[vertex1].push_back(vertex2);
        graph[vertex2].push_back(vertex1);
    }
}

void bfs(int start)
{
    int current;//current node being processed
    int next;//reached node by current
    unsigned int i;
    queue<int> vertices;//vertices to process
    distances[start] = 0;
    discovered[start] = true;
    vertices.push(start);
    while(!vertices.empty())
    {
        current = vertices.front();
        vertices.pop();
        for(i = 0; i < graph[current].size(); i++)//for each node connected to current
        {
            next = graph[current][i];
            if(!discovered[next])//if it hasn't been reached
            {
                discovered[next] = true;//mark it as reached
                parent[next] = current;//store its parent
                distances[next] = distances[current]+1;//save the distance
                vertices.push(next);//push it to the queue for further analysis
            }
        }
    }
}

void find_path(int vertex)//recursive procedure to find the path
{
    if(vertex == -1)
        return;
    find_path(parent[vertex]);
    printf("%d ", vertex);
}

int main()
{
    int vertices;
    int edges;
    int start;
    int dest_path;
    int i;
    scanf("%d %d", &vertices,  &edges);
    init_graph(vertices);
    read_graph(edges);
    scanf("%d", &start);
    bfs(start);
    for(i = 0; i < vertices; i++)
        printf("%d ",distances[i]);
    printf("\n");
    scanf("%d", &dest_path);
    find_path(dest_path);
    return 0;
}

DFS

 

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

typedef pair<int, int> ii;      // In this chapter, we will frequently use these
typedef vector<ii> vii;      // three data type shortcuts. They may look cryptic
typedef vector<int> vi;   // but shortcuts are useful in competitive programming

#define DFS_WHITE -1 // normal DFS, do not change this with other values (other than 0), because we usually use memset with conjunction with DFS_WHITE
#define DFS_BLACK 1

vector<vii> AdjList;

void printThis(char* message) {
  printf("==================================\n");
  printf("%s\n", message);
  printf("==================================\n");
}

vi dfs_num;     // this variable has to be global, we cannot put it in recursion
int numCC;

void dfs(int u) {          // DFS for normal usage: as graph traversal algorithm
  printf(" %d", u);                                    // this vertex is visited
  dfs_num[u] = DFS_BLACK;      // important step: we mark this vertex as visited
  for (int j = 0; j < (int)AdjList[u].size(); j++) {
    ii v = AdjList[u][j];                      // v is a (neighbor, weight) pair
    if (dfs_num[v.first] == DFS_WHITE)         // important check to avoid cycle
      dfs(v.first);      // recursively visits unvisited neighbors v of vertex u
} }

int main() {
  int V, total_neighbors, id, weight;

  /*
  // Use the following input:
  // Graph in Figure 4.1

  */

  //freopen("in_01.txt", "r", stdin);

  scanf("%d", &V);
  AdjList.assign(V, vii()); // assign blank vectors of pair<int, int>s to AdjList
  for (int i = 0; i < V; i++) {
    scanf("%d", &total_neighbors);
    for (int j = 0; j < total_neighbors; j++) {
      scanf("%d %d", &id, &weight);
      AdjList[i].push_back(ii(id, weight));
    }
  }

  printThis("Standard DFS Demo (the input graph must be UNDIRECTED)");
  numCC = 0;
  dfs_num.assign(V, DFS_WHITE);    // this sets all vertices' state to DFS_WHITE
  for (int i = 0; i < V; i++)                   // for each vertex i in [0..V-1]
    if (dfs_num[i] == DFS_WHITE)            // if that vertex is not visited yet
      printf("Component %d:", ++numCC), dfs(i), printf("\n");   // 3 lines here!

  return 0;
}