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?
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.
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....
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...
[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]
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 ??
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.
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?
