732 - Anagrams by Stack

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

kate
New poster
Posts: 11
Joined: Thu May 22, 2003 9:37 pm

732 - Anagrams by Stack

Post by kate » Mon Jun 30, 2003 3:18 pm

I start from "i i ......i" 2n n times where n is the length of the word and increase it one by one, i.e. "i i i i i i i" "i i i i i i o" "i i i i i o i" "i i i i i o o" to check to see if they are valid. Is there a faster way?

Code: Select all

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void print(vector<char> sequence, int size)
{
    for(int i=0;i<size-1;i++)
        cout << sequence[i] << " ";
    if(size!=0) cout << sequence[size-1] << endl; 
}
bool same(vector<char> first, vector<char> second, int size)
{
    for(int i=0;i<size;i++) 
		if(first[i]!=second[i]) return false; 
	return true;
}
bool isValid(vector<char> original, vector<char> objective, vector<char> sequence, int size)
{
    vector<char> temp, holder; int templength = size-1, holderlength = 0;
    temp.resize(size); holder.resize(size);
    for(int t=0;t<size;t++) temp[t]=original[t];
    for(int i=0;i<size*2;i++) {
        if(sequence[i]=='i') {
            if(templength==0) return false;
            holder[holderlength]=temp[0];
            if(templength>0)
                for(int x=0;x<templength;x++) temp[x]=temp[x+1];
            holderlength++; templength--;
        }
        else {
            if(holderlength==0) return false;
            temp[templength+1]=holder[holderlength-1];
            holderlength--; templength++;
        }
    }
    if(same(temp,objective,size)) return true;
    else return false;
}
int main()
{
    vector<char> original, objective, sequence; char ch; bool end = false; int length=0;
    while(cin.get(ch)) {
        length++;
        original.push_back(ch);
        cin.get(ch);
        while(ch!='\n') {
            length++;
            original.push_back(ch);
            cin.get(ch); 
        }
        length=0;
        cin.get(ch);
        while(ch!='\n') {
            objective.push_back(ch);
            length++;
            cin.get(ch);
        }
		    cout << "[" << endl;
        for(int i=0;i<length*2;i++) sequence.push_back('i');
        if(isValid(original,objective,sequence,length)) print(sequence,length*2); 
        while(!end) {
            bool stop = false; int i=length*2-1;
            while(!stop) {
                if(sequence[i]=='i') { sequence[i]='o'; stop=true; }
                else { sequence[i]='i'; i--; }
                if(i==0) { stop=true; end=true; }
            }
            if(isValid(original,objective,sequence,length)) print(sequence,length*2);
        }
		cout << "]" << endl;
        end = false; length=0; original.clear(); objective.clear(); sequence.clear();
    }
    return 0;
}

kate
New poster
Posts: 11
Joined: Thu May 22, 2003 9:37 pm

Post by kate » Sun Jul 06, 2003 7:30 am

I made a few alterations an it is faster but I still get Time Limit Exceeded.
If the lengths of the original and objective word is different it prints nothing, if the words do not contain the same letters it terminates, otherwise it goes through all the combinations of valid pushes and pops until there's an undesired pop and prints if there are none until the first command is a pop.

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

void print(vector<char> sequence, int size)
{
    for(int i=0;i<size-1;i++)
        cout << sequence[i] << " ";
    if(size!=0) cout << sequence[size-1] << endl; 
}
bool isValid(vector<char> original, vector<char> objective, vector<char> sequence, int size)
{
    vector<char> temp, holder; int templength = size-1, holderlength = 0;
    temp.resize(size); holder.resize(size); char des = objective[0]; int count = 1;
    temp=original;
    for(int i=0;i<size*2;i++) {
        if(sequence[i]=='i') {
            holder[holderlength]=temp[0];
            for(int x=0;x<templength;x++) temp[x]=temp[x+1];
            holderlength++; templength--;
        }
        else {
			if(holder[holderlength-1]!=des) return false;
			des = objective[count]; count++;
            holderlength--; templength++;
        }
    }
    return true;
}
bool missing(vector<char> original, vector<char> objective)
{
	string temp;
	for(int a=0;a<original.size();a++)
		temp+=original[a];
	for(int i=0;i<objective.size();i++) {
		int loc = temp.find(objective[i]);
		if(loc==string::npos)
			return true;
	}
	return false;
}
int main()
{
    vector<char> original, objective, sequence; char ch; bool end = false; int length=0;
	int length2=0;
    while(cin.get(ch)) {
        length++;
        original.push_back(ch);
        cin.get(ch);
        while(ch!='\n') {
            length++;
            original.push_back(ch);
            cin.get(ch); 
        }
        cin.get(ch);
        while(ch!='\n') {
            objective.push_back(ch);
            length2++;
            cin.get(ch);
        }
		cout << "[" << endl;
		if(length!=length2) end=true;
		if(missing(original,objective)) end=true;
        for(int i=0;i<length;i++) sequence.push_back('i');
		for(int p=length;p<length*2;p++) sequence.push_back('o');
        if(isValid(original,objective,sequence,length)) print(sequence,length*2); 
        while(!end) {
            int i=length*2-1;
            next_permutation(sequence.begin(),sequence.end());
			if(sequence[0]=='o') end=true;
			else
				if(isValid(original,objective,sequence,length)) print(sequence,length*2);
        }
		cout << "]" << endl;
        end = false; length=0; length2=0; original.clear(); objective.clear(); sequence.clear();
    }
    return 0;
}

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Jul 06, 2003 8:49 am

Try to add some Branch and Bound.

Check: whenever an "o" command is called, if the output character doesn't match with the target string, skip this case!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

kate
New poster
Posts: 11
Joined: Thu May 22, 2003 9:37 pm

Post by kate » Mon Jul 07, 2003 1:08 am

Okay I changed it once again using a recursive function. It runs much faster, fast enough I believe but I get a "Runtime Error (SIGSEGV)" for some reason I can't think of....

Code: Select all

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void print(vector<char> & sequence)
{
    for(int i=0;i<sequence.size()-1;i++)
        cout << sequence[i] << " ";
    if(sequence.size()!=0) cout << sequence[sequence.size()-1] << endl; 
}
void moveback(vector<char> & word)
{
	if(word.size()>0) {
		for(int i=0;i<word.size()-1;i++)
			word[i]=word[i+1];
		word.pop_back();
	}
}
void find(const vector<char> original, vector<char> holder, vector<char> objective, 
		  vector<char> sequence, int size, vector<vector<char> > & answers)
{
	vector<char> a = original, b = holder, c = objective, d = sequence;
	d.push_back('o');
	b.pop_back(); moveback(c);
	if(c.size()==0)
		answers.push_back(d);
	else {
		int count = size;
		for(int i=0;i<=count;i++) {
			if(b.back()==c[0])
				find(a,b,c,d,size,answers);
			if(i==count) return;
			d.push_back('i');
			b.push_back(a[0]);
			moveback(a);
			size--;
		}
	}
}
bool missing(vector<char> original, vector<char> objective)
{
	string temp;
	for(int a=0;a<original.size();a++)
		temp+=original[a];
	for(int i=0;i<objective.size();i++) {
		int loc = temp.find(objective[i]);
		if(loc==string::npos)
			return true;
	}
	return false;
}
int main()
{
    vector<char> original, objective, sequence; char ch; int length=0;
	int length2=0;
    while(cin.get(ch)) {
        length++;
        original.push_back(ch);
        cin.get(ch);
        while(ch!='\n') {
            length++;
            original.push_back(ch);
            cin.get(ch); 
        }
        cin.get(ch);
        while(ch!='\n') {
            objective.push_back(ch);
            length2++;
            cin.get(ch);
        }
		cout << "[" << endl;
		if(!missing(original,objective) && length==length2) {
			vector<vector<char> > answers;
			sequence.push_back('i');
			vector<char> holder;
			holder.push_back(original[0]);
			moveback(original);
			int size = length-1;
			int count = size;
			for(int i=0;i<=count;i++) {
				if(holder.back()==objective[0])
					find(original,holder,objective,sequence,size,answers);
				if(i!=count) {
					sequence.push_back('i');
					holder.push_back(original[0]);
					moveback(original);
					size--;
				}
			}
			if(answers.size()>0)
				for(int j=answers.size()-1;j>=0;j--) {
					print(answers[j]);
					answers[j].clear();
				}
			answers.resize(0);
		}
		cout << "]" << endl;
        length=0; length2=0; objective.clear(); sequence.clear(); original.clear();
    }
    return 0;
}

kate
New poster
Posts: 11
Joined: Thu May 22, 2003 9:37 pm

Post by kate » Mon Jul 07, 2003 3:27 am

I fixed the problem. AC.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

732 TLE

Post by shamim » Mon Aug 04, 2003 3:06 pm

cut
Last edited by shamim on Wed Aug 06, 2003 8:29 am, edited 1 time in total.

farsight
New poster
Posts: 7
Joined: Wed Aug 06, 2003 4:51 am

Post by farsight » Wed Aug 06, 2003 5:02 am

Hi shamim,

TLE usually means that the way you are solving the problem is too slow and that you'll need to scrap it and find another way of doing things... (unless you did a silly typo which is causing the TLE).
I solved this problem using brute force recursion. In your recursion branch out trying to do an 'i' and then an 'o'. Keep track of how your two strings mutate after each 'i' or 'o' operation as well as your stack and the current possible solution. Once you find a solution add it to a collection. The key is not to follow branches in the recursion that can not possibly lead to a correct answer...
ex:
poping off an 'a' when you actually needed to match a 'b'... since that step could not possibly be in a solution kill that branch of the recursion... if you need a working example, I could post my java solution...

Have fun. :D

LeoST
New poster
Posts: 7
Joined: Thu Dec 25, 2003 5:10 pm
Location: Russia

732 why time limit Exceeded

Post by LeoST » Sun Dec 28, 2003 2:59 pm

this is my source

Code: Select all

[pascal]program n732;
var
  comand : string;
  i,j : integer;
  n : integer;
  s1,s2 : string;
  comands : array[1..100000] of string;
  qual : integer;
procedure getnext;
var
  i,j,sc : integer;
begin
  i := n*2;
  while (i > 1) and (comand[i-1]+comand[i] <>'oi') do dec(i);
  comand[i-1] := 'i';comand[i] := 'o';
  comand := copy(comand,1,i);
  sc := 0;
  for j := 1 to i do if comand[j] = 'i' then inc(sc)
                                        else dec(sc);
  while sc <> 0 do
    begin
      comand := comand + 'o';
      dec(sc);
    end;
  while length(comand) <> 2*n do comand := comand + 'io';
end;

function last : boolean;
var
  i : integer;
begin
  last := true;
  for i := 1 to n do
    if comand[i] = 'o' then
      begin
        last := false;
        exit;
       end;
end;
function stkstr : string;
var
  i,j : integer;
  temp : string;
  stk : string;
  pointer : integer;
begin
  temp := s1;
  pointer := 1;
  for i:= 1 to 2*n do
    begin
      case comand[i] of
        'i' :
          begin
            stk := stk + temp[1];
            inc(pointer);
            delete(temp,1,1);
          end;
        'o' :
          begin
            dec(pointer);
            temp := temp + stk[pointer];
            delete(stk,pointer,1);
          end;
      end;
    end;
  stkstr := temp;
end;
function lex(s : string) : string;
var i,j : integer;
    ch : char;
begin
  for i := length(s) downto 1 do
    begin
      j := i;
      while ord(s[j]) < ord(s[J+1]) do
       begin
         ch := s[j];
         s[J] := s[j+1];
         s[J+1] := ch;
         inc(j);
       end;
    end;
  lex := s;
end;


begin
  {assign(input,'input.txt');
  assign(output,'output.txt');
  reset(input);
  rewrite(output);}
  while not eof do
    begin
      qual := 0;
      writeln('[');
      readln(s1);
      readln(s2);
      if (length(s1) <> length(s2))
        or (lex(s1) <> lex(s2))
         then
        begin
          writeln(']');
          continue;
        end;
      n := length(s1);
      comand := '';
      for i := 1 to n do comand := comand + 'io';
      while not last do
        begin
          if stkstr = s2 then
            begin
              inc(qual);
              comands[qual] := comand;
            end;
          getnext;
        end;
      if stkstr = s2 then
        begin
          inc(qual);
          comands[qual] := comand;
        end;
      for i := qual downto 1 do writeln(comands[i]);
      writeln(']')
    end;





end.
[/pascal]
Best reguards

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

732 TLE !!!

Post by Chok » Tue Aug 16, 2005 10:15 am

Hi all,
I'm getting tle for this problem. Here is my approach --

1. First i check whether the frequencey of each character for two given inputs are same or not. If not same then directly print []

2. If same, then generate all of the permutation of i's and o's. where the number of i's=o's=len of the first string.

3. Then check each permutation. When popping char from stack i check it with our target string. If any pop char is not match the target character then stop, else print.

So, whats wrong with me ? How long will be the given string length ?? more than 10? or 20 ??

Thanks in advance.

User avatar
Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

Post by Donotalo » Thu Nov 23, 2006 10:11 am

i'm constantly getting TLE in this problem. i've done the following:

1) if current permutation begins with an 'o', stop checking, since all the of the next permutations will begin with this pop command and popping something from an empty stack is an invalid command.

2) if an 'o' command is found in the middle of the checking and there is nothing in the stack, skip that case.

3) if an 'i' command is found and there is nothing in the input string, skip that case.

4) if an 'o' command is found and currently expected character is not the character just popped out, then skip that case, since this will never reach to the target string.

5) don't search if the input and target strings have different lengths.


what else can i do to avoid TLE? please help. thanks in advance.
Image

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Thu Nov 23, 2006 10:44 am

If you make all the permutations and then try to check, you will get TLE..

User avatar
Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

Post by Donotalo » Thu Nov 23, 2006 12:24 pm

no. i do not generate permutations as soon as the first character of the permutation string is 'o'.
Image

User avatar
Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

Post by Donotalo » Thu Nov 23, 2006 8:12 pm

i've done too many optimizations for this program i think. but i'm still getting TLE. can anyone tell me what is the maximum word length and how many pairs of word may be in the input file? or can anyone send me a reasonably large input for this program?

thanks in advance.
Image

vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:

Post by vinit_iiita » Mon Apr 02, 2007 1:52 pm

Code: Select all

//nth combination of 0 and 1's 
#include<iostream>
#include<string>
#include<vector>
using namespace std;
string s1,s2;
vector<char> v;
void backtrack(int n,int i)
{
     if(i==2*n)
     {
     vector<char> vi,vi1;
     int j=0;
     for (int k=0;k<v.size();k++)
     {
        // cout<<v[k];
         if (v[k]=='i')
         {
                       vi.push_back(s1[j]);
                       j++;
                       }
                       else if (v[k]=='o' && vi.size()!=0)
                       {
                           vi1.push_back(vi[vi.size()-1]);
                           vi.pop_back( );
                           }
                           else
                           break;
                           }
                           if (j==n)
                           {
                              bool flg=true;
                              for (int k=0;k<n;k++)
                              if(vi1[k]!=s2[k])
                              {
                                flg=false;
                                break;
                                }
                                if(flg)
                                {
                                       for (int t=0;t<2*n-1;t++)
                                       cout<<v[t]<<" ";
                                       cout<<v[2*n-1]<<endl;
                                       }
                                       }
                           
                       
                           
         
    // cout<<endl;
     return;
     }
     else
     {
       v.push_back('i');
       backtrack(n,i+1);
       v.pop_back( );
       v.push_back('o');
       backtrack(n,i+1);
       v.pop_back( );
     
       
       }
}
int main()
{
    vector<string> vin;
    string str1,str2;
    while (cin>>str1 && cin>>str2)
    {
          vin.push_back(str1);
           vin.push_back(str2);
           }
          for (int i=0;i<vin.size();i+=2)
          { 
          s1=vin[i];
          s2=vin[i+1];
          int n;
          n=s1.size();
          if (n!=s2.size())
          {
             cout<<"[\n]\n";
                                        // return 0;
                                         }
             else
             {
                   cout<<"[\n";
                   backtrack(n,0);
                   cout<<"]\n";
                   }            
                   }      
                   
    return 0;
}

i am getting TLE can some one help me out..?
win

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Mon Apr 02, 2007 5:49 pm

You don't do any pruning..
Just try what farsight and Donotalo said..

Post Reply

Return to “Volume 7 (700-799)”