Problem 338

danielwallace · Post by **danielwallace** » Sun May 15, 2011 6:28 pm

I am confused about which rectangles to count...
for the example 9x4 i understand there are three.
but for the 9x8 example I also see three.
I see the 18x4 and the 12x6, but i also see a 6x12
by cutting it like the 3rd rectangle in the first example
but by going 4 down instead of 2.

Should i count the 12x6 and the 6x12 as just one rectangle?

Lord_Farin · Post by **Lord_Farin** » Sun May 15, 2011 7:49 pm

Problem 338 (View Problem)

Problem statement wrote: ...
Note that rectangles congruent to the initial one are not counted in F(w,h).
Note also that rectangles with dimensions w × h and dimensions h × w are not considered distinct.
...

Therefore, the answer to your question is yes. I hope this has clarified the problem for you.

sivakd · Post by **sivakd** » Sun May 15, 2011 11:56 pm

I get correct answer for G(10^5) but my final answer is still wrong. Not sure if it's due to integer overflow. Or are there special cases for higher values of N?

Edit: Never mind, it was just an overflow issue.

Hibernatus34 · Post by **Hibernatus34** » Mon May 16, 2011 7:07 am

Hello,

I'm sorry if this is a silly question, but is this problem really solvable in less than a minute on a modest computer ?
I have a correct algorithm which worked for the 3 given examples. Seemed optimized to me (i'm not talking about low level optimization of course), but it's way too long for 10^12.

Thanks.

hk · Post by hk » Mon May 16, 2011 9:13 am

Yes, it can be solved in about 10 to 20 seconds.

Hibernatus34 · Post by **Hibernatus34** » Mon May 16, 2011 9:53 pm

Thanks a lot.
Only 10-20 seconds sounds impressive.
But i got a new idea i will try soon, so there's hope

spanklord · Post by **spanklord** » Thu Jun 23, 2011 4:17 pm

Yes, it can be solved in about 10 to 20 seconds.

Been stuck on this problem now for quite some time.
I have the same problem as Hibernatus34 and i was just wondering if you actually use the functions F as it is specified or is there a more... compact way ?

thundre · Post by **thundre** » Wed Jun 29, 2011 1:24 pm

spanklord wrote:
Yes, it can be solved in about 10 to 20 seconds.
Been stuck on this problem now for quite some time.
I have the same problem as Hibernatus34 and i was just wondering if you actually use the functions F as it is specified or is there a more... compact way ?

If you implement G by summing F for all h <= w <= 1e12, that's about 5e24 add operations. No, I don't think he's doing that in 20 seconds. There must be a simpler way to calculate G.

Hibernatus34 · Post by **Hibernatus34** » Wed Jul 06, 2011 10:28 pm

Before i waste a whole day on this problem i have a question : does it require some math knowledge ?

Today i've started to study it again.
So far i've only rewritten the same code as my first attempt (had lost it), which calculates G(10^5) in 23 s (brute force obviously).
I'm not asking for a hint, just trying to know if i simply have a chance to solve this problem.

Francky · Post by **Francky** » Sun Jul 17, 2011 5:37 pm

I got G(10⁵) in 40ms and G(10⁹) in 3min (and I'm proud of this) ; brute force, even optimized, isn't able to catch G(10¹²).
It would take a week or more !!!
I can't optimize more my code, I have to use a totally new method, but wich ?
(PM me a chapter to study, please)
Thanks.

xiekaixuan · Post by **xiekaixuan** » Fri Sep 02, 2011 7:42 am

Hello,

Can this problem 338 be solved by Python with in several minutes?

Thank you.

Project Euler Forum

Problem 338

Problem 338

Re: Problem 338

Re: Problem 338

Re: Problem 338

Re: Problem 338

Re: Problem 338

Re: Problem 338

Re: Problem 338

Re: Problem 338

Re: Problem 338

Re: Problem 338