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.
