Problem 210
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.

 Posts: 17
 Joined: Wed Apr 02, 2008 7:14 pm
Problem 210
I must be crazy but I get a lot more for N(4). Don't know how to show it without giving away too much...
 daniel.is.fischer
 Posts: 2400
 Joined: Sun Sep 02, 2007 11:15 pm
 Location: Bremen, Germany
Re: Problem 210
Count again. I get 24, too for r = 4.
Il faut respecter la montagne  c'est pourquoi les gypaètes sont là.

 Posts: 17
 Joined: Wed Apr 02, 2008 7:14 pm
Re: Problem 210
Yes, I was going crazy. Sanity restored, somewhat...
Re: Problem 210
I got a right number for 4 and 8:
4 24
8 100
12 226
100 15648
1000000000 ?
But for 1000000000 it's wrong.
Can somebody tell me if 12 and 100 are right?
Thanks
4 24
8 100
12 226
100 15648
1000000000 ?
But for 1000000000 it's wrong.
Can somebody tell me if 12 and 100 are right?
Thanks
 daniel.is.fischer
 Posts: 2400
 Joined: Sun Sep 02, 2007 11:15 pm
 Location: Bremen, Germany
Re: Problem 210
The number for r = 12 is correct, the one for r = 100 not.
Il faut respecter la montagne  c'est pourquoi les gypaètes sont là.
Re: Problem 210
Bah, I came out with the same formula as you... looks like I'm gonna have to do r==24 by hand before I can figure this one out.Taifu wrote:I got a right number for 4 and 8:
4 24
8 100
12 226
100 15648
1000000000 ?
But for 1000000000 it's wrong.
Can somebody tell me if 12 and 100 are right?
Thanks
ex ~100%'er... until the gf came along.
Re: Problem 210
i got the same formula ___quilan wrote:Bah, I came out with the same formula as you... looks like I'm gonna have to do r==24 by hand before I can figure this one out.Taifu wrote:I got a right number for 4 and 8:
4 24
8 100
12 226
100 15648
1000000000 ?
But for 1000000000 it's wrong.
Can somebody tell me if 12 and 100 are right?
Thanks
Re: Problem 210
Me also. This is a little tedious...
Re: Problem 210
Ha! Found my mistake... Hopefully won't be long now.
Re: Problem 210
Yeah, it's a pretty sneaky bit of subtlety... now to finally work a method for solving that missing amount...lster wrote:Ha! Found my mistake... Hopefully won't be long now.
ex ~100%'er... until the gf came along.
Re: Problem 210
It is funny how so many of us have fallen into that trap...
Re: Problem 210
Ok, this is annoying. So, apparently my algorithm is juuuust subtly off from correctness. I've done a manual check on up to 1000 but it becomes far too slow to calculate further. Is there any chance anyone can confirm/deny these values?
[snip values, not to give too much info to others]
[snip values, not to give too much info to others]
ex ~100%'er... until the gf came along.
 daniel.is.fischer
 Posts: 2400
 Joined: Sun Sep 02, 2007 11:15 pm
 Location: Bremen, Germany
Re: Problem 210
I didn't check your value for 100, the others are correct. So if your answer for 10^{9} isn't accepted, you could PM me.
Il faut respecter la montagne  c'est pourquoi les gypaètes sont là.
Re: Problem 210
I have 2 algos for this problem  first one is O(N), second is bruteforce (for checking first algo on little values of N). I have tested both algos on many values of N (max tested  10000) and they gived me equal results, but with N=1000000000 I got WA. Here are my results:
4 24
8 100
12 226
100 15944
10000 159814790
500000000 406249999821471154
Can somebody tell me if 500000000 is right?
4 24
8 100
12 226
100 15944
10000 159814790
500000000 406249999821471154
Can somebody tell me if 500000000 is right?
Re: Problem 210
I got the same formula too.Taifu wrote:I got a right number for 4 and 8:
4 24
8 100
12 226
100 15648
1000000000 ?
But for 1000000000 it's wrong.
Can somebody tell me if 12 and 100 are right?
Thanks
Re: Problem 210
It maybe should be mentioned in this thread that in most computer languages a floating point type with 64 bits (e.g. a 'double') will only have essentially 53 bits to hold an integer value. It is therefore not accurate for integers above 2^{53}, or about 9*10^{15}.
_{Jaap's Puzzle Page}
Re: Problem 210
I read this thread a few days ago (so I knew there was a trap) and just now analyzed the probleme with pen&paper... I walked right into the trap and I've got no idea how to get out of it
Edit: Ahh.. I think I found the missing parts
Edit: Ahh.. I think I found the missing parts
Re: Problem 210
Yeah, I should put it out there, that there seems to be many people (myself included) that have run into floating point rounding errors with the very large values in this problem. That being said, there are integer methods to solve this.
Last edited by quilan on Tue Sep 30, 2008 9:57 pm, edited 1 time in total.
ex ~100%'er... until the gf came along.
 daniel.is.fischer
 Posts: 2400
 Joined: Sun Sep 02, 2007 11:15 pm
 Location: Bremen, Germany
Re: Problem 210
Unfortunately, it's wrongJarlax wrote:I have 2 algos for this problem  first one is O(N), second is bruteforce (for checking first algo on little values of N). I have tested both algos on many values of N (max tested  10000) and they gived me equal results, but with N=1000000000 I got WA. Here are my results:
4 24
8 100
12 226
100 15944
10000 159814790
500000000 406249999821471154
Can somebody tell me if 500000000 is right?
Il faut respecter la montagne  c'est pourquoi les gypaètes sont là.
Re: Problem 210
Yeah, I've got it.... finally