gavinksong

My sincerest apologies to Perhaps check it again for offending his fragile sensibilities. My colon-D resulted in a goofier-looking grin than I had intended. In the future, I will make a better effort to contain my raging inner narcissist. As a token of apology, I'd like to share some of my ointment with Perhaps check it again as he has no doubt developed some of his own abrasions after making that devastatingly witty comment of his.

This is another problem from Google Code Jam that blew my mind. It is still blowing my mind. It just so happens to be from the same round as the problem I posted earlier. Like before, there is a small input and a large input for this problem. For the large input, n can reach up to 2 billion. Thus, in order to calculate the answer in a reasonable amount of time (and precision*), some key mathematical insights are required. What are they? *for non-coders: since computers cannot store real numbers with infinite precision, most operations on "floating point numbers" cause a gradual loss in precision. In our case, it would almost definitely result in an incorrect answer.

I'm getting quite a collection of bonanova stars.

I agree. That would have been a much harder problem. I probably wouldn't have been able to solve it. I didn't realize this was an original puzzle. Good job!

The explanation is a bit longer and awkward than it needs to be, but it is correct. As sharp as ever, Rainman.

Here's a fairly easy one for you thinkers. It's very possible that the coders among you have seen the coding version of this challenge before. It is from the Google CodeJam Round 1A 2008 and is listed as a practice problem on their homepage. Each round there is a small input file and a large input file. The method of testing every possible permutation will work on the small input file, but it is impractical to use the same method for the large input. Solving the large input requires a key mathematical insight (or perhaps just a good hunch). What is this insight? Prove it.

There is a surprisingly elegant solution to this problem. Start by reexamining your assumptions.

Impressive results from everybody. I especially applaud Rainman on his thorough analysis - although it is incorrect. One of your assumptions is false.

That's very good and quite close to the optimal number of expected rolls, but you can do even better. Edit -- After reading DejMar's post, I realized that he is right. plasmid's method wouldn't produce any primes above 59, for example.

Edit -- Sorry, I kept messing up.

Edit: I guess I ought to attach that figure I was talking about ^.^ But I thought the triangle is not equilateral. And yet your reasoning for it seems solid enough. Edit -- that must be the OR that bonanova is talking about.

No. It is too hard. Perhaps you could give us a hint.

My apologies to everybody. I meant to say four points in a closed hemisphere. BMAD still got it.

This starts to be a question of morals.

Prove that given any five points on a sphere, three of them lie on a hemisphere.