Carlos, Thanks a lot. I misread the problem and thought that the number of students was <=n.
Eric On Thu, Mar 3, 2011 at 2:46 AM, Carlos Guia <[email protected]> wrote: > I think the problem is due to index out of bounds, there is no reason to > think that the number of students will be less than or equal to 20. One way > to remove the problem is to not store all b's before calling them, i.e make > b unidimensional and merge the while and for loops you have like this: > int ..., b[20], ...; > while(scanf("%d",&read)!=EOF){ > b[read-1]=0; > for(i=1;i<n;i++){ > scanf("%d",&read); > b[read-1]=i; > } > printf("%d\n",solve(a,0,b,0,n)); > } > > With this structure you will see the RTE disappears, however, your solve > method is too slow and will get time limit exceeded. You need to use dynamic > programming (hereafter referred as DP) to solve it in time. You can read > this articles on DP: > http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg > http://www.topcoder.com/tc?module=Static&d1=features&d2=040104 > > The second one explains a technique known as memoization, which some people > consider an implementation of DP others consider it a different but similar > technique. Whatever is the case, memoization fits perfectly for this problem > (actually the second one uses longest common subsequence as the main > example) and changing your solution to use memoization is a 2 minutes task. > However, I recommend reading both articles and any other you can find, or in > any algorithm book since DP is one the most important things to know in > programming contests. > > Hope this helps and you find DP to be a powerful tool, > Carlos Guía > > > On Thu, Mar 3, 2011 at 1:12 AM, Eric Kulcyk <[email protected]> wrote: > >> Hello, >> >> I have written code from the uva problem located >> here<http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=47&mosmsg=Submission+received+with+ID+8619259>. >> Basically, its a longest common substring problem. It works fine on my >> computer, but I get a runtime error on UVA. However, I don't think it is an >> index out of bounds error or a case that I am not seeing. First here is the >> code: >> >> #include <stdio.h> >> >> int solve (int a[20], int aa, int b[20], int bb, int length); >> >> int main(){ >> >> int n; >> scanf("%d",&n); >> >> int a[20],i, b[20][20],length=0,read; >> for (i=0; i < n;i++){ >> scanf("%d",&read); >> a[read-1]=i; >> } >> while(scanf("%d",&read)!=EOF){ >> b[length][read-1]=0; >> for(i=1;i<n;i++){ >> scanf("%d",&read); >> b[length][read-1]=i; >> } >> length++; >> } >> for (i=0;i<length;i++) >> printf("%d\n",solve(a,0,b[i],0,n)); >> return 0; >> } >> int solve (int a[20], int aa, int b[20], int bb, int length){ >> int max=0; >> >> if(aa>=length||bb>=length) >> return 0; >> >> int l=solve(a,aa+1,b,bb,length); >> int r=solve(a,aa,b,bb+1,length); >> >> max=max>l?max:l; >> max=max>r?max:r; >> >> if(a[aa]==b[bb]) >> max++; >> >> return max; >> } >> >> Through commenting sections out, I found that the problem comes when at >> the call to solve(a,0,b[i],0,n). just to make sure, I put return values in >> the function solve and before the call to solve (separately) with a wrong >> answer result (no runtime error). I also changed the index from b[i] to >> b[0] just to make sure no out of bounds error was occurring, and I still got >> the runtime error. Am I doing something wrong? >> >> Thanks so much for the help, >> >> Eric >> >> -- >> >> >> :(){:|:&};: >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "google-codejam" 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/google-code?hl=en. >> > > -- :(){:|:&};: -- You received this message because you are subscribed to the Google Groups "google-codejam" 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/google-code?hl=en.
