Page 1 of 2
732 - Anagrams by Stack
Posted: Mon Jun 30, 2003 3:18 pm
by kate
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;
}
Posted: Sun Jul 06, 2003 7:30 am
by kate
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;
}
Posted: Sun Jul 06, 2003 8:49 am
by Observer
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!
Posted: Mon Jul 07, 2003 1:08 am
by kate
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;
}
Posted: Mon Jul 07, 2003 3:27 am
by kate
I fixed the problem. AC.
732 TLE
Posted: Mon Aug 04, 2003 3:06 pm
by shamim
cut
Posted: Wed Aug 06, 2003 5:02 am
by farsight
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.
732 why time limit Exceeded
Posted: Sun Dec 28, 2003 2:59 pm
by LeoST
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]
732 TLE !!!
Posted: Tue Aug 16, 2005 10:15 am
by Chok
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.
Posted: Thu Nov 23, 2006 10:11 am
by Donotalo
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.
Posted: Thu Nov 23, 2006 10:44 am
by helloneo
If you make all the permutations and then try to check, you will get TLE..
Posted: Thu Nov 23, 2006 12:24 pm
by Donotalo
no. i do not generate permutations as soon as the first character of the permutation string is 'o'.
Posted: Thu Nov 23, 2006 8:12 pm
by Donotalo
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.
Posted: Mon Apr 02, 2007 1:52 pm
by vinit_iiita
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..?
Posted: Mon Apr 02, 2007 5:49 pm
by helloneo
You don't do any pruning..
Just try what farsight and Donotalo said..