Project Euler Forum

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?

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.

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.

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.

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

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

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 ?

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.

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.

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.

Hello,

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

Thank you.