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 <[email protected]> wrote:
> i'm trying out this problem www.spoj.pl/problems/ACODE
>
> i'm getting TLE.. I donno y my recursion leads to tle
>
> #include<iostream>
> #include<map>
> #include<stdio.h>
> #include<string.h>
> using namespace std;
>
> map<string, long long> ans;
> map<string, 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
