Thursday, August 30, 2012

Topcoder SRM 552 Div 2 250 Problem



#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
class FoxAndFlowerShopDivTwo {
public:
        int theMaxFlowers(vector <string>, int, int);
};
 
int get_flower_count(vector <string>& flowers,int x1,int y1,int x2,int y2)
{
        int count = 0;
        for(int i=x1;i<=x2;++i)
        {
                for(int j=y1;j<=y2;++j)
                {
                        if(flowers[i][j] == 'F')
                                count++;
                }
        }
        return count;
}
int FoxAndFlowerShopDivTwo::theMaxFlowers(vector <string> flowers, int r, int c) {
        
        int max_row = flowers.size()-1;
        int max_col = flowers[0].size()-1;
        
        int temp,max_flower = 0;
        if( c-1>=0)
        {
                temp = get_flower_count(flowers,0,0,max_row,c-1);
                if(temp > max_flower)
                        max_flower = temp;
        }
        if(r-1 >= 0)
        {
                temp = get_flower_count(flowers,0,0,r-1,max_col);
                if(temp > max_flower)
                        max_flower = temp;
        }
        if(r+1 <= max_row)
        {
                temp = get_flower_count(flowers,r+1,0,max_row,max_col);
                if(temp > max_flower)
                        max_flower = temp;
        }
        if(c+1 <= max_col)
        {
                temp = get_flower_count(flowers,0,c+1,max_row,max_col);
                if(temp > max_flower)
                        max_flower = temp;
        }
        return max_flower;      
}

Friday, August 3, 2012

TOPCODER SRM 144 Div 1



#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
class BinaryCode {
public:
        vector <string> decode(string);
};
int get_int(char x)
{
    return x-'0';
}
string get_string(string message,char assump)
{
    string first;
    int s = message.size();
    first.push_back(assump);
        first.push_back(get_int(message[0]) - get_int(assump) + '0');
        for(int i=1;i<s-1;++i)
        {
            if(first[i] < '0' || first[i] >'3')
            {
            first.clear();
            first = "NONE";
            break;
            }
            else
            {
                char v = get_int(message[i]) - (get_int(first[i-1]) + get_int(first[i])) +'0';
                first.push_back(v);
            }
        }
        if(s>1)
        if(message[s-1] != (get_int(first[s-1])+get_int(first[s-2]) + '0'))
            return "NONE";
    return first;
}
vector<string> BinaryCode::decode(string message) {
        string first="";
        string None[2] = {"NONE","NONE"};
        int s = message.size();
        if(s ==0 || message[0] >'2' || message[s-1] > '2')
        {
            vector<string> v(None,None+2);
            //v.push_back("NONE");
            //v.push_back("NONE");
            return v;
        }
 
        vector<string> v;
        v.push_back(get_string(message,'0'));
        v.push_back(get_string(message,'1'));
 
        return v;
}
 
//<%:testing-code%>
//Powered by [KawigiEdit] 2.0!
int main()
{
 
    BinaryCode b;
    vector<string> x = b.decode("3");
    cout<<x[0]<<" "<<x[1]<<endl;
}


Wednesday, August 1, 2012

Create a singly linked list from the Leaf nodes from a binary tree. Tree may be balanced or not. Linked List should be created in place (tree nodes should be used)

Code: O(n) time, O(log n) space complexity.

#include<iostream>
#include<stack>
using namespace std;
 
class Node
{
public:
        int data;
        Node *left,*right;
        Node(int d,Node *l=NULL,Node *r=NULL):data(d),left(l),right(r){}
};
void insert_after(Node *h,Node *temp)
{
    temp->right = h->right;
    h->right = temp;
}
Node *make_links(Node *head)
{
    if(head == NULL)
        return NULL;
 
    stack<Node *> st;
    Node *list = new Node(-1);
    Node *temp = head;
    Node *temp_list=list;
    while(true)
    {
        for(;temp;temp=temp->left)
            st.push(temp);
        if(st.empty())
            break;
        else{
            temp = st.top();
            st.pop();
            Node *l = temp->right;
            if(temp->left==NULL && temp->right==NULL)
            {
                insert_after(temp_list,temp);
                temp_list=temp_list->right;
            }
            temp = l;
        }
    }
    Node *l = list;
    list = list->right;
    delete l;
    return list;
}
void preorder_print(Node *head)
{
    if(head == NULL)
        return;
    cout<<head->data<<" ";
    preorder_print(head->left);
    preorder_print(head->right);
}
void inorder_print(Node *head)
{
    if(head == NULL)
        return;
    inorder_print(head->left);
    cout<<head->data<<" ";
    inorder_print(head->right);
}
int main()
{
        Node *head = new Node(10,new Node(5,new Node(2),new Node(7)),new Node(13,new Node(11),new Node(14)));
        preorder_print(head);cout<<endl;
        inorder_print(head);
        Node *ll = make_links(head);
        cout<<endl;
        for(;ll;ll=ll->right)
        cout<<(ll->data)<<" ";
}

Wednesday, July 25, 2012

Counting Maximum Apples

A table composed of N*M cells,each having a certain quantity of apples, is given. you start from the upper-left corner. At each step you can go down or right one cell.Design an algorithm to find the maximum number of apples you can collect ,if you are moving from upper-left corner to bottom-right corner.

Code (O(m*n) time, O(m*n) space):
#include<iostream>
#include<stack>
using namespace std;
 
int path(int (*array)[4],int row)
{
        int **aux = new int *[row];
        for(int i=0;i<row;++i)
                aux[i]=new int[4]();
        
        aux[0][0] = array[0][0];
        for(int i=0,j=1;j<4;++j)
                aux[i][j] = aux[i][j-1] + array[i][j];
        
        for(int i=1,j=0;i<row;++i)
                aux[i][j] = aux[i-1][j] + array[i][j];
        
        for(int i=1;i<row;++i)
        {
                for(int j=1;j<4;++j)
                {
                        aux[i][j] = array[i][j] + std::max(aux[i-1][j],aux[i][j-1]);
                }
        }
        
        stack<string> st;
        
        st.push("At Destination");
        int i,j;
        for(i=row-1,j=3;i>0 && j>0;)
        {
                if(aux[i][j] - array[i][j] == aux[i-1][j])
                {
                        st.push("go down");
                        i--;
                }
                else
                {
                        st.push("go right");
                        j--;
                }
        }
        if(i==0)
                while(j--)
                        st.push("go right");
        if(j==0)
                while(i--)
                        st.push("go down");
        
        cout<<"At Source, now..\n";
        while(!st.empty())
        {
                cout<<st.top()<<"\n";
                st.pop();
        }
        return aux[row-1][3];
        
}
int main()
{
        int array[3][4]={{1,2,3,4},
                                         {1,1,1,1}, 
                                         {9,9,9,9}
                                        };
                
        int total = path(array,3);
        cout<<"Total:"<<total<<endl;
        return 0;
}