Problem that has been solved by the smallest number of people (31): http://projecteuler.net/problem=453
Any hints? Anyone?
Take advantage of symmetry, especially translation symmetry.
Project Euler
131–138 of 138 posts
Re: Project Euler
#132Earlier quoted context omitted.
When I was conducting quantitative interviews I ended up doing the same thing. One of my favorite problems to give was 267 ( http://projecteuler.net/problem=267 ). It has a few "aha" moments but also requires coding to get it done.
My solution would be: For one coint toss, I get: (previous winnings) x (1+f) if I win (previous winnings) x (1-f) if I lose Thus, w being the number of times I win, I get the total $$ we would have: (1+f)^w x (1-f)^(1000-w) But those cases are not equally likely, so we have to ponderate them with a normal law centered at 1000/2, variance at sqrt(1000/4): (1/(sqrt(2xPi)xsqrt(250))) x exp(-(500-w)^2/500) So, now we can…
It's actually 1+2f versus 1-f. (I agree that the wording is not very clear. I misinterpreted it too at first and was very confused at how my solution was being rejected. If you look at the short worked example they give, though, it's unambiguous.)
You're using the normal approximation to the binomial distribution. It may or may not be a good enough approximation. Better to do the binomial thing exactly. This requires arbitrary-precision integer arithmetic, but that's pretty easily available.
Re: Project Euler
#133Earlier quoted context omitted.
When I was conducting quantitative interviews I ended up doing the same thing. One of my favorite problems to give was 267 ( http://projecteuler.net/problem=267 ). It has a few "aha" moments but also requires coding to get it done.
Is there a list with Project Euler problems that focus less on number theory like this one?
I like Programming Praxis (http://programmingpraxis.com/), it has mostly algorithmic problems and the questions also include solutions.
Re: Project Euler
#134Earlier quoted context omitted.
When I was conducting quantitative interviews I ended up doing the same thing. One of my favorite problems to give was 267 ( http://projecteuler.net/problem=267 ). It has a few "aha" moments but also requires coding to get it done.
Is there a list with Project Euler problems that focus less on number theory like this one?
I really enjoy the types of problems on PuzzleNode[1]. My local coder meetup does one each month for code reviews. Their puzzles are just deep enough to where you need to think through how you'll design the system. They're really fun for exploring different programming techniques.
Re: Project Euler
#135Earlier quoted context omitted.
As a female math grad and CS postgrad, I would like to say firstly that you have successfully trolled me. I do hereby take your bait. Now for the points I would like to make, primarily for the benefit of the few who actually think as you claim to think: Women are actually similar to men in a number of novel ways. We have eyes, and those eyes are intricately connected to very powerful and compact organic computers—cap…
Seems like you're promoting some myths as well. Kids don't magically decide that math or science or computer programming is fun. They're heavily influenced by what they're exposed to and what they see other people they respect doing. Yes, that's "marketing" or perhaps better call it education. And no, giving a kid the "C programming language" isn't going to cut it unless they've previously had enough exposure to math…
>Kids don't magically decide that math or science or computer programming is fun
Yeah, they do. That's why it is so important to expose kids to lots of things. You never know what is going to capture their imagination.
Re: Project Euler
#136Earlier quoted context omitted.
When I was conducting quantitative interviews I ended up doing the same thing. One of my favorite problems to give was 267 ( http://projecteuler.net/problem=267 ). It has a few "aha" moments but also requires coding to get it done.
My solution would be: For one coint toss, I get: (previous winnings) x (1+f) if I win (previous winnings) x (1-f) if I lose Thus, w being the number of times I win, I get the total $$ we would have: (1+f)^w x (1-f)^(1000-w) But those cases are not equally likely, so we have to ponderate them with a normal law centered at 1000/2, variance at sqrt(1000/4): (1/(sqrt(2xPi)xsqrt(250))) x exp(-(500-w)^2/500) So, now we can…
I get 1/4 as the optimal value for f. Given a 500/500 win lose, then final money = (1-f)^500*(1+2f)^500 = (-2f^2+f+1)^500. To find the maximum, the ^500 is irrelevant. Differentiating and finding a gradient of 0 gives: -4f+1=0 or f=1/4. Just by checking values, it seems I need to lose more than 555 times before I finish with less then 1 billion. I'm not sure how to calculate the probability of that, your formula doesn't seem to work. In any case, the problem seems to be purely mathematical rather than requiring code to be written.
Re: Project Euler
#137Earlier quoted context omitted.
When I was conducting quantitative interviews I ended up doing the same thing. One of my favorite problems to give was 267 ( http://projecteuler.net/problem=267 ). It has a few "aha" moments but also requires coding to get it done.
Is there any danger that someone has seen the problem?
Yea - then we just walk through their answer to make sure they get the reason it works and ways to improve it. It's usually quicker and leaves time for another question that they hopefully haven't heard.
Re: Project Euler
#138Earlier quoted context omitted.
My solution would be: For one coint toss, I get: (previous winnings) x (1+f) if I win (previous winnings) x (1-f) if I lose Thus, w being the number of times I win, I get the total $$ we would have: (1+f)^w x (1-f)^(1000-w) But those cases are not equally likely, so we have to ponderate them with a normal law centered at 1000/2, variance at sqrt(1000/4): (1/(sqrt(2xPi)xsqrt(250))) x exp(-(500-w)^2/500) So, now we can…
I get 1/4 as the optimal value for f. Given a 500/500 win lose, then final money = (1-f)^500*(1+2f)^500 = (-2f^2+f+1)^500. To find the maximum, the ^500 is irrelevant. Differentiating and finding a gradient of 0 gives: -4f+1=0 or f=1/4. Just by checking values, it seems I need to lose more than 555 times before I finish with less then 1 billion. I'm not sure how to calculate the probability of that, your formula does…
I have a different f that can win with only 433 heads.