Fibonacci Words ACM ICPC 2012 problem

Page 1 of 1

8 Replies - 3085 Views - Last Post: 09 October 2012 - 02:10 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=293888&amp;s=7bd3ce87d9df62b0203b53743b506fd9&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 Pete_Aye

Reputation: 0
• Posts: 3
• Joined: 01-October 12

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

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);
}
}

Is This A Good Question/Topic? 0

Replies To: Fibonacci Words ACM ICPC 2012 problem

#2 natecat

Reputation: 56
• Posts: 233
• Joined: 19-December 11

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 sepp2k

• D.I.C Lover

Reputation: 2296
• Posts: 3,550
• Joined: 21-June 11

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 Pete_Aye

Reputation: 0
• Posts: 3
• Joined: 01-October 12

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.

#5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11755
• Posts: 44,166
• Joined: 27-December 08

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 sepp2k

• D.I.C Lover

Reputation: 2296
• Posts: 3,550
• Joined: 21-June 11

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 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).

#7 rfs02

Reputation: 26
• Posts: 70
• Joined: 30-September 12

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.

#8 sepp2k

• D.I.C Lover

Reputation: 2296
• Posts: 3,550
• Joined: 21-June 11

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 nick2price

• D.I.C Lover

Reputation: 565
• Posts: 2,826
• Joined: 23-November 07

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.