Problem 353

[BostonBear]

I am a little confused about the new problem. This sphere has integer coordinates. Yet we are not given a specific size, so as far as I can tell , for a generic r, there are only 6 integer coordinates. (r,0,0), (0,r,0), (0,0,r) and its antipodals. Is there something I'm missing here? Does each trip to a station have to be a direct trip, or can you change directions before you get to the next station?

Edit, never mind, I figured out what I was not seeing right

[TripleM]

You are given a specific size - r is equal to 2^n - 1 for each value of n from 1 to 15.

[cyrillic]

Could I check with someone the value of M(r) for n=15 I'm getting, to validate my code? Cheers.

[thundre]

Could I check with someone the value of M(r) for n=15 I'm getting, to validate my code? Cheers.

PM it to me and I'll tell you whether it matches mine.

[Arthelais]

Could someone verify for me whether M(1000) is equal to 0.05174553024? I feel like I am facing a rounding error and I can't seem to figure it out.

[MuthuVeerappanR]

Is this problem prone to precision errors?? I tried a couple of methods and they all provide the same for value upto M(10). But somehow my answer is not getting accepted.

[sjhillier]

Well you certainly have to be precise, but no more so than many other problems. There are other possible error modes, but it would be wrong to say more.

[MuthuVeerappanR]

Thanks sjhillier. I solved it yesterday. Turns out one of my assumptions only fails for the k = 8 case.

[sjhillier]

Thanks sjhillier. I solved it yesterday. Turns out one of my assumptions only fails for the k = 8 case.

I'm sure I made the same mistake too.

[bleh0.5]

Are we supposed to calculate every single integer set of coordinates or are the only coordinates going to be (0,r,r) and stuff like that

[RobertStanforth]

Are we supposed to calculate every single integer set of coordinates or are the only coordinates going to be (0,r,r) and stuff like that

The admissible paths (from which you are asked to find the one with the lowest risk) are permitted to use any of the integer-coordinate points on the surface of $C$. The problem statement does not confine you to a special subset of them.

[ChicoTobi]

Uhm, so I hope i don't spoil anything... so if it's too much please feel free to delete...

So I started doing this problem, because I love those fancy geometry problems! And also I was thinking, that a lot of symmetry is going on here. After reproducing the solution for the small number example from the question (N=3, r=7), I tried scaling it up. And boy, was I wrong! Both the generation of the pythagorean tuples as well as the graph-matrix as well as the dijkstra algo only perform until N=11, N=12 within around a minute. But there's no way that I will reach N=15 within a minute.

I produced hashes for the smaller numbers. Can somebode check these plz? It's a simple md5 of the the utf-8 string in the form as in the problem "0.1784943998".

Hash for r= 1 : d310cb367d993fb6fb584b198a2fd72c
Hash for r= 3 : fca3319e19aa9137881ea13ea824edce
Hash for r= 7 : d0dfb92eb56f02b897654fe4652b2f1f
Hash for r= 15 : 5f9e89ed8d08fd895368256943196c5a
Hash for r= 31 : eb166b2e0288c93cccd7a4d47229b7a7
Hash for r= 63 : 0ba2dd95494dc35f356eb185dfcd5a9a
Hash for r= 127 : f7049ff1b5cb032b8c1fcee6acc1ffdc
Hash for r= 255 : 02aa0151cd3f7eb54469ab56dcf65f1f
Hash for r= 511 : d58bbfcfa5f91cd8b530109f45743000
Hash for r= 1023 : 6ccc1e655cdbf556ea1f9f63e152053b
Hash for r= 2047 : 846004309705e1a24389b67e2f298f7e

Then I would know if my implementation is wrong, or if it's only too slow/inefficient. I attached part of my shortest path for r=255.

Edit: Nevermind, I let it run, and it was correct in the end But still took like 30 minutes, sadly.