Problem 390

[mdean]

Probably a stupid question. I'm assuming either b or c are allowed to be zero? And the triangle with (b,c)=(0,2) would be the same as the triangle with (b,c)=(2,0)?

[aruff]

I would agree that the problem seems to allow for b or c to be 0 (0 is an integer after all)
This seems inconsistent with the sample result given though.
This doesn't feel like a spoiler to me, but to be safe:

Expand

If we set c to zero and b>0, we get sqrt(1+b**2), sqrt(1), sqrt(b**2) => 1, b, sqrt(1+b**2) this is a right triangle with 1 and b as legs so the area is (1*b)/2 this means we could get any area, A, with b = 2*A
This puts a lower bound on the solution of n*(n+1)/2 but if n = 10**6, n*(n+1)/2 >> S(n)=18018206

So to summarize I think the problem only uses non-zero b and c, but I do not see anything in the problem's wording to justify this.

[albert]

So to summarize I think the problem only uses non-zero b and c, but I do not see anything in the problem's wording to justify this.

The title of the problem sites "non-rational" sides.
There are two problems with this:
- it is extremely bad style, if the problem name is part of the problem statement.
- you can't see the title if you're looking at the problem anyway.
In fact I myself went straight to the problem, without seeing its title.

So I definitely think non-rational should be repeated in the body of the problem.

Groetjes Albert

[mpiotte]

It is not clear from the problem statement if b or c are allowed to be zero. However, the test value for S(10^6) shows that the correct solution excludes any triangle with b=0 or c=0.

Martin

[hk]

It is not clear from the problem statement if b or c are allowed to be zero. However, the test value for S(10^6) shows that the correct solution excludes any triangle with b=0 or c=0.

Martin

It is now.

[jerryhe26]

Did you mistook sqrt(a^2+b^2) to sqrt(a^2*b^2)??

I would agree that the problem seems to allow for b or c to be 0 (0 is an integer after all)
This seems inconsistent with the sample result given though.
This doesn't feel like a spoiler to me, but to be safe:

Expand

If we set c to zero and b>0, we get sqrt(1+b**2), sqrt(1), sqrt(b**2) => 1, b, sqrt(1+b**2) this is a right triangle with 1 and b as legs so the area is (1*b)/2 this means we could get any area, A, with b = 2*A
This puts a lower bound on the solution of n*(n+1)/2 but if n = 10**6, n*(n+1)/2 >> S(n)=18018206

So to summarize I think the problem only uses non-zero b and c, but I do not see anything in the problem's wording to justify this.

[Mr_Nobody]

To those who solved this one, how long did it take to compute for n=10^6?

[Pavgran]

To those who solved this one, how long did it take to compute for n=10^6?

Less than a second even with some kind of bruteforce.

[mdean]

To those who solved this one, how long did it take to compute for n=10^6?

Well, I had a program that did 10^6 correctly in about 2 seconds which ran into problems for 10^10 besides being too slow. I fixed the problem, which brought the running speed up to 8 seconds. Didn't bother trying that with 10^10.

Now I have a program that does 10^6 incorrectly in 156 ms...

My latest answer is slightly too high. I must be counting something twice or something...

Update: I found and fixed the overcount. While it still ran quite fast for 10^6, looks like it's going to be another flagrant 1 minute rule violation for 10^10.

[mdean]

And now it looks like overflow is going to be a problem. 10^9 runs in about 3 minutes. 10^10 ran overnight and never finished...

[mdean]

Well, I think the overflow is fixed, but I seem to be getting an incorrect value for 10^10. Can I pm someone my results for 10^7,10^8, and 10^9?

[Marcus_Andrews]

Feel free to shoot me a PM.

[sharyari]

Hi, I'm not sure if I understand this problem. Is it correct that I am to sum the area of all the triangles with sides (a,b,c) with the given property AND have an even-numbered area?

If that is the correct interpretation, I am kind of stuck and would appreciate it if someone could nudge me in the right direction.

As it is, I am able to find a subset of these triangles rather easily, but a brute-force approach is able to find more such triangles. What am I missing here?

Thank you in advance

[thundre]

Hi, I'm not sure if I understand this problem. Is it correct that I am to sum the area of all the triangles with sides (a,b,c) with the given property AND have an even-numbered area?

There is no mention of a variable a in the problem statement. The sides depend on variables b and c.

And there is no requirement that the area be an even number, only that it be an integer in the specified range.

It's possible that you understand correctly and have reassigned variables for your own purposes. Yes, the range is too large to do with brute force alone. My successful approach was a hybrid of brute force searching and something else.

[sharyari]

Then I believe I have understood it correctly, but obviously too lazy to explain myself well enough.

My successful approach was a hybrid of brute force searching and something else.

I believe that I have the "something else" pinned down. Do you think some amount of bruteforce is needed, or is it just the simple way? And if the former, am I right that I should try to figure out which areas of the problem to bruteforce?

[thundre]

I believe that I have the "something else" pinned down. Do you think some amount of bruteforce is needed, or is it just the simple way? And if the former, am I right that I should try to figure out which areas of the problem to bruteforce?

My solution took 5 minutes to run -- in Java. It might fit in the 1-minute parameter if converted to C++. So yes, the algorithm I used does require a significant amount of computation to catch all of the triangles.

I don't think I can elaborate without spoiling the problem. My best suggestion, which you seem to be doing already, would be to look for triangles which your brute-force search finds but your advanced algorithm does not.

[Marcus_Andrews]

sharyari: I just want to point out that brute force isn't technically required to solve this problem. However, with that being said, it may still be the best approach if your goal is just to get the answer as soon as possible. The answer can be calculated in just a couple milliseconds, but figuring out the algorithm may take more time overall.