Re: [algogeeks] string problem
no.. each ans[s] is stored before returning.. so there is no recalculation of any substring On Sun, Sep 18, 2011 at 4:12 AM, Marcelo Amorim Menegali mmeneg...@gmail.com wrote: *ans[s]=find(s+1,len-1);* if(s[0]'3's[1]'7') *ans[s] = ans[s]+find(s+2,len-2);* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] string problem
i'm trying out this problem www.spoj.pl/problems/ACODE
i'm getting TLE.. I donno y my recursion leads to tle
#includeiostream
#includemap
#includestdio.h
#includestring.h
using namespace std;
mapstring, long long ans;
mapstring, bool flags;
long long find(char *s, int len){
if(flags[s])
return ans[s];
if(s[0]=='0')
ans[s]=0;
else if(len==1)
ans[s]=1;
else if(len==2)
if(s[0]'3's[1]'7's[1]!='0')
ans[s]=2;
else
ans[s]=1;
else{
ans[s]=find(s+1,len-1);
if(s[0]'3's[1]'7')
ans[s] = ans[s]+find(s+2,len-2);
}
flags[s]=true;
return ans[s];
}
int main(){
char str[5001];
while(1){
scanf(%s,str);
if(str[0]=='0') break;
ans.clear();
flags.clear();
printf(%lld\n,find(str,strlen(str)));
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] string problem
I think you're getting TLE because your solution calculate the same stuff
over and over again.
Look at this part:
else{
*ans[s]=find(s+1,len-1);*
if(s[0]'3's[1]'7')
*ans[s] = ans[s]+find(s+2,len-2);*
}
Calculating find(s+1,len-1) imply that find(s+2,len-2) will be calculated
inside that call, but the code ignores that and calculates find(s+2,len-2)
again.
It's just like implementing Fibonacci recursively... you end up calling the
base cases a lot of times.
In my solution to this problem, I only used one for-loop (iterating through
the string backwards) and a bunch of if-else staments (four, actually)
inside this loop.
Also, I just ran your code with some input and, for the number consisting of
the digit '1' 5000 times, your code takes 4.5s and outputs the wrong answer
(a negative number), while the correct answer is 2020817954 and should be
obtainable in less than 0.01s.
I hope this will help.
Marcelo
On Sat, Sep 17, 2011 at 6:41 PM, cegprakash cegprak...@gmail.com wrote:
i'm trying out this problem www.spoj.pl/problems/ACODE
i'm getting TLE.. I donno y my recursion leads to tle
#includeiostream
#includemap
#includestdio.h
#includestring.h
using namespace std;
mapstring, long long ans;
mapstring, bool flags;
long long find(char *s, int len){
if(flags[s])
return ans[s];
if(s[0]=='0')
ans[s]=0;
else if(len==1)
ans[s]=1;
else if(len==2)
if(s[0]'3's[1]'7's[1]!='0')
ans[s]=2;
else
ans[s]=1;
else{
ans[s]=find(s+1,len-1);
if(s[0]'3's[1]'7')
ans[s] = ans[s]+find(s+2,len-2);
}
flags[s]=true;
return ans[s];
}
int main(){
char str[5001];
while(1){
scanf(%s,str);
if(str[0]=='0') break;
ans.clear();
flags.clear();
printf(%lld\n,find(str,strlen(str)));
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] String Problem
given a string find the number of distinct substrings of the string. ex: input- output- 4(a, aa, aaa, ) input-abcd output-10(a, b, c, d, ab, bc, cd, abc, bcd, abcd) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] String Problem
You r given a large string of characters lets call it Sbig. Then there is a small set of characters lets call it Ssmall. You have to find smallest substring of Sbig which contains all characters in Ssmall. For example you are given Sbig = hello what are you doing Ssmall= eo answer is ello 24 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] String Problem
http://codepad.org/NDAeIpxR http://codepad.org/NDAeIpxRHere is code for it On Sat, Jun 26, 2010 at 9:54 PM, Anand anandut2...@gmail.com wrote: you can use Longest common subsequence algorithm to solve it. On Sat, Jun 26, 2010 at 4:04 PM, amit amitjaspal...@gmail.com wrote: You r given a large string of characters lets call it Sbig. Then there is a small set of characters lets call it Ssmall. You have to find smallest substring of Sbig which contains all characters in Ssmall. For example you are given Sbig = hello what are you doing Ssmall= eo answer is ello 24 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
