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

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;
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
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; int count = 1;
temp=original;
for(int i=0;i<size*2;i++) {
if(sequence[i]=='i') {
holder[holderlength]=temp;
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=='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
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
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)
else {
int count = size;
for(int i=0;i<=count;i++) {
if(b.back()==c)
if(i==count) return;
d.push_back('i');
b.push_back(a);
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) {
sequence.push_back('i');
vector<char> holder;
holder.push_back(original);
moveback(original);
int size = length-1;
int count = size;
for(int i=0;i<=count;i++) {
if(holder.back()==objective)
if(i!=count) {
sequence.push_back('i');
holder.push_back(original);
moveback(original);
size--;
}
}
}
}
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
I fixed the problem. AC.

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

732 TLE

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
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. LeoST
New poster
Posts: 7
Joined: Thu Dec 25, 2003 5:10 pm
Location: Russia

732 why time limit Exceeded

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;
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('[');
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 !!!

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 ??

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 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. helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
If you make all the permutations and then try to check, you will get TLE..

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
no. i do not generate permutations as soon as the first character of the permutation string is 'o'. Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
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? vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:

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
You don't do any pruning..
Just try what farsight and Donotalo said..