4 ms·
At the risk of looking like a complete idiot, I think your solution to problem #2 is incorrect. Update: I was wrong. It's kind of scary how sure I was of my
by jah 16y ago
At the risk of looking like a complete idiot, I think your solution to problem #2 is incorrect.
Update: I was wrong. It's kind of scary how sure I was of my incorrect solution.
- igoros 16y agoI got their answer. Note that there is a wrong "solution" to this problem that looks like it might be right. It is a very standard problem, by the way. Most books on algorithms will have the solution.
- georgieporgie 16y ago> Most books on algorithms will have the solution. What would you call this algorithm? I solved the second problem, but my solution is brute-force, and I'd like to see a better way to do it.
- igoros 16y agoAnswer in rot13: Gur grpuavdhr vf pnyyrq "qlanzvp cebtenzzvat". Naq, guvf cnegvphyne ceboyrz vf pnyyrq gur "pbva punatr ceboyrz".
- georgieporgie 16y agoGreat, thanks!
- leif 16y agolbh pna whfg guvax bs vg nf onpxgenpxvat naq zrzbvmr lbhe shapgvba yngre qnfu guvf fubhyq or rdhvinyrag gb gur qc bcra cnera ohg v unirag pbzcyrgryl jbexrq bhg gur qc fb znlor abg dhrfgvba znex pybfr cnera
- deleted 16y ago[deleted]
- rflrob 16y agoI'm not convinced that brute force is such a bad approach, as long as a) you start with the greedy approximation, and b) stop once you know you're doing worse than the greedy approximation. My python brute-force solution runs in .035 s.
- georgieporgie 16y agoMy brute force algorithm runs in about two minutes... It's C++. I'm sure you can see why I'm so interested in better solutions. :-)
- mdonahoe 16y agodo you say this because your greedy algorithm solution of 450225 didnt work?
- dexen 16y agoThanks for the ``greedy algorithm'' hint ;-)
- yaroslavvb 16y agoI think it's right because I got through using Mathematica's MIP solver http://bit.ly/fr7YXu http://bit.ly/fr7YXu
- polo 16y agoNice to see others using Mathematica. Here are my solutions: http://bit.ly/gghd5K http://bit.ly/gghd5K
- Confusion 16y agoIf you find that a useful learning experience, you may want to try http://projecteuler.net/ http://projecteuler.net/ I've thought "How can my solution possible be wrong" numerous times while doing those problems. Makes you realize how often mistakes slip through in real code, 'that can't possibly be wrong'. Even when you have tests, because for complex behavior, your test case solution may easily be wrong (or worse: derived from your algorithm... I'm guilty of that mistake)