import java.util.Scanner; public class FibonacciWords { public static String fibSeq(int n){ String s = ""; if(n<=1){ return s += n; } return fibSeq(n1) + fibSeq(n2); } 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); } }
Fibonacci Words ACM ICPC 2012 problem
Page 1 of 18 Replies  2290 Views  Last Post: 09 October 2012  02:10 PM
#1
Fibonacci Words ACM ICPC 2012 problem
Posted 01 October 2012  04:05 PM
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
Replies To: Fibonacci Words ACM ICPC 2012 problem
#2
Re: Fibonacci Words ACM ICPC 2012 problem
Posted 01 October 2012  04:09 PM
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.
#3
Re: Fibonacci Words ACM ICPC 2012 problem
Posted 02 October 2012  03:46 AM
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
#4
Re: Fibonacci Words ACM ICPC 2012 problem
Posted 09 October 2012  10:03 AM
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.
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.
#5
Re: Fibonacci Words ACM ICPC 2012 problem
Posted 09 October 2012  10:20 AM
Do you have to use a recursive method here? An iterative Fibonacci method would be a lot more efficient here.
#6
Re: Fibonacci Words ACM ICPC 2012 problem
Posted 09 October 2012  10:52 AM
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 straightforward 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).
#7
Re: Fibonacci Words ACM ICPC 2012 problem
Posted 09 October 2012  01:39 PM
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.
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.
#8
Re: Fibonacci Words ACM ICPC 2012 problem
Posted 09 October 2012  02:04 PM
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.
#9
Re: Fibonacci Words ACM ICPC 2012 problem
Posted 09 October 2012  02:10 PM
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.
Page 1 of 1
