Hi All,

I am a beginner to this site and tried to solve the problem . I am using DP but time limit is exceeded on test  # 5 . what algorithm shud I use or wat improvements can I do to my code.
///////////////////////////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <fstream>
#include <vector>
using namespace std;

map <char, char> guide;
void initialise()
{
     guide['i'] = '1';guide['j'] = '1';guide['a'] = '2';guide['b'] = '2';guide['c'] = '2';guide['d'] = '3';
     guide['e'] = '3';guide['f'] = '3';guide['g'] = '4';
     guide['h'] = '4';guide['k'] = '5';guide['l'] = '5';guide['m'] = '6';guide['n'] = '6';guide['p'] = '7';
     guide['r'] = '7';guide['s'] = '7';guide['t'] = '8';guide['u'] = '8';guide['v'] = '8';guide['w'] = '9';
     guide['x'] = '9';guide['y'] = '9';guide['o'] = '0';guide['q'] = '0';guide['z'] = '0';
}
string getcode(string& str)
{
     string::iterator it;
     string s;
     for(it = str.begin();it!=str.end();it++)
     {
            s.push_back(guide[(*it)]);
     }
     return s;
}
/*void solve(map <string,vector<string> > m1,string& call)
{
       string ret;
       typedef string::iterator iter;
       iter it;
       vector < <string> :: iterator > pos;
       typedef map <string,vector <string> > :: iterator t;
       for(it=call.begin();it!=call.end();it++)
       {
        for(iter i = it;i!=call.end();++i)
        {
                 t mt = m1.find(string(it,i));
                 if(mt != m1.end())
                 {//we found the 1st word
                 //must note the position and store in vector
                 // keep erasing the last one if it is not found
                 pos.push_back(i);

                       ret.append(mt->second[0]);
                       it = i;
                       it++;
                       //need to find more
                 }
        }
       }
       if(ret.length()!=call.length())
         cout<<"No Solution";
       else
           cout<<ret;
}*/

string select(vector < vector<string::iterator> > &book,map <string , vector <string> > &m1,string &str)
{
    string ret;
    int best = book[0].size();
    int pos = 0;
    for(int i=1;i<book.size();i++)
    {
        if(book[i].size()<best)
        {
            pos = i;
            best = book[i].size();
        }
    }
    for(int j = 0;j<best-1;j++)
    {
        ret.append(m1[string(book[pos][j],book[pos][j+1])][0]);
        ret.append(" ");
    }
    return ret;
}
string solve(map <string , vector <string> > &m1,string &str)
{
    int best = 9000000000;
    bool no_soln = true;
     bool found = false;
     typedef string :: iterator iter;
     typedef map <string, vector <string> >::iterator it;
     vector <string :: iterator> sp;
     vector < vector<string::iterator> > db;
     sp.push_back(str.begin());
     int c = 0;
     iter j = sp[c];
     while(!(found) && c!=-1)
     {
        do
        {
            if (c>best || c==best-1)
                break;
            j++;
            it h = m1.find(string(sp[c],j));
            if (h!=m1.end())
            {
                //we found one word so push it
                //cout<<h->second[0]<<" ";
                sp.push_back(j);
                c++;
            }
        }while(j!=str.end());
        //cout<<c<<" ";
        //check whether found or not
        if(sp[c] == str.end())
        {
            if (best>c)
                best = c;
            cout<<best<<" ";
            no_soln = false;
            db.push_back(sp);
            sp.pop_back();c--;
            j = sp[c];
            sp.pop_back();c--;

        }
        else
                 {j = sp[c];sp.pop_back();c--;}
     }
    if (!(no_soln))
        return select(db,m1,str);
    else
        return "No solution.";
}
void printing(map <string, vector <string> > &m1)
{
     map<string,vector <string> > :: iterator it;
     it = m1.begin();
     while(it != m1.end())
     {
      cout<<(*it).first<<" "<<it->second[0]<<"\n";
      it++;
     }
}
vector <string> readinput(istream &in)
{
    vector <string> ret;
     string call;
     getline(in,call);
     while((call.compare("-1"))!=0)
     {
        map <string , vector<string> > dict;
         int words=0;
         //getline(in,call);
         in>>words;
         in.ignore(255,'\n');
         string line;
         while(words>0)
         {
          getline(in,line);
          dict[getcode(line)].push_back(line);
          words--;
          }
          //printing(dict);
         ret.push_back(solve(dict,call));
         getline(in,call);
     }
     return ret;
}

int main()
{
    ifstream infile;
    infile.open("DATA.in");
    ofstream outfile;
    outfile.open("DATA.out");
    initialise();
    vector <string> ans;
    ans  = readinput(infile);
    for(int i=0;i<ans.size();i++)
        outfile<<ans[i]<<endl;
    /*string m;
    getline(cin,m);
    cout<<getcode(m);
    */
    //getch();
    infile.close();
    outfile.close();
    return 0;
}

Cud u give me a hint !!!

Thanks

1. When you write:
     something::iterator iter;
     for(iter = container.begin(); iter != container.end(); ++iter)
         ...

   container.end() is called each iteration.

     something::iterator iter, iter_end;
     for(iter = container.begin(), iter_end = container.end(); iter != iter_end; ++iter)
         ...

is better.

2. When you write:
     while(...)
     {
       int i;
       ...
     }

   i is allocated from stack each iteration.

    int i;
    while(...)
    {...}

   is better.

3. vector<smth>::push_back() is a very slow operation.
   It allocates a new piece of memory, copies copies all previous values and a new one to it, and frees the old piece of memory.
   Performance of push_back() is better in deque and list.

4. printf() and scanf() are better than cin, cout, ifstream, ofstream, fstream in performance.

Edited by author 31.03.2009 15:38