[Pete_Aye]

Hi. I am new on this forum. I joined because I am preparing for a programming contest, and I tried to solve the fibonacci words ACM ICPC 2012 problem, but I was getting an OutOfMemoryError. Can anyone please help me? Here'e the code

import java.util.Scanner;


public class FibonacciWords {
	public static String fibSeq(int n){
		String s = "";
		if(n<=1){
			return s += n;
		}
		return fibSeq(n-1) + fibSeq(n-2);
	}

	public static void main(String[] args){
		Scanner s = new Scanner(fibSeq(40));
		int c=0;
		while(s.findInLine("10110101101101")!=null){
			c++;
		}
		System.out.println(c);
	}
}

[natecat]

Recursive methods like that take up lots of memory. It is better then to have a recursive method, have it call another method that calls the solving method in a loop, and store the last 2 numbers in global variables.

[sepp2k]

natecat, on 02 October 2012 - 01:09 AM, said:

Recursive methods like that take up lots of memory.

Recursive methods consume stack space, not heap space. If you run out of stack space, you get a stack overflow error, not an out of memory error.

Also a recursion depth of 40 is not nearly enough to run out of stack space.

@OP: Look closely at how the length of the string returned by fibseq grows compared to n. Now what will be the length of the string returned by fibseq(40)? Is it realistic to think that such a string would fit into memory?

Spoiler:

Spoiler

The length of the string returned by fibseq(n) is equal to the n+2nd Fibonacci number. So the string returned by fibseq(40) will be 165580141 characters long. That's probably already beyond the judge's memory limit (especially since Java strings don't use a single-byte encoding). Taking into account all the temporary strings you're creating, you're way beyond anything that would realistically fit into memory.

[Pete_Aye]

sep22k:
Thanks a lot for the useful reply. I understand this, but I don't know how to go about solving this problem in a better way. Please can you help me with a better way to solve it? Also, preparing for this contest has been tedious, and at the same time discouraging. Many of the sample problems are so difficult for me to figure out that they take me a lot of time to solve. Can you give me some tips on solving these problems, like some 'tricks' I need to know about? I have done some study on data structures, but the choice of when and where to apply them is what is also posing a challenge to me.

[macosxnerd101]

Do you have to use a recursive method here? An iterative Fibonacci method would be a lot more efficient here.

[sepp2k]

macosxnerd101, on 09 October 2012 - 07:20 PM, said:

Do you have to use a recursive method here? An iterative Fibonacci method would be a lot more efficient here.

Just rewriting the code to be iterative will hardly fix the problem. As I said already, the whole idea of trying to generate the entire string and then iterating over it to count the occurrences of the substring is hopeless since the string will exceed the memory limit.

@Pete I honestly don't know how to solve this. Note that these problem's are supposed to be hard. Any straight-forward solution that is obvious as soon as you read the problem description is almost guaranteed not to work for all but the easiest problem in the set (and for world finals sets probably not even for that one).

[rfs02]

I agree with sepp2k that there is no easy answer to this problem.

The way I would have attempted to do this would have been using a BitSet since the whole string is made up of 1s and 0s.

Would require some creativity in building the fibonacci sequence, and then you would have to decide how to count the number of times the "needle" BitSet appears in the fibonacci BitSet by shifting and comparing.

Good luck.

[sepp2k]

rfs02, on 09 October 2012 - 10:39 PM, said:

The way I would have attempted to do this would have been using a BitSet since the whole string is made up of 1s and 0s.

I've just googled for the original description of this problem. The maximum possible value for n is 100. That's a string of 573147844013817084101 1s and 0s - even using bitsets, that will never fit into memory.

[nick2price]

Written solution Problem D seems to be the one your doing, and it provides a written solution for you. It doesnt give you any code, which is good, but it explains how you can solve it.