HHC 2017 RPL Programming contest information and results thread
|
09-18-2017, 08:51 PM
(This post was last modified: 09-19-2017 03:10 AM by Claudio L..)
Post: #25
|
|||
|
|||
RE: HHC 2017 RPL Programming contest information and results thread
(09-18-2017 07:44 PM)pdo Wrote:(09-18-2017 06:34 PM)Claudio L. Wrote: Yes and no. I actually came up with an algorithm that minimizes the denominators but still guarantees 1e-12 accuracy to avoid all penalty from error. Once I got to that point, my "pseudo-score" (using 0.6,0.99 and 0.71828 only) dropped from 6900 to 519. Nothing fancy, really. The basic algorithm takes each denominator as A=CEIL(1/x) as others mentioned. This is the closest 1/A fraction to x, which leaves the smallest residual x'=x-1/A for the next step. The next step does the same on this small number B=CEIL(1/x') , therefore giving you a large denominator, but optimal convergence. My algorithm tries to work with 2 steps at once: x=1/A+1/B The idea is to choose a pair of A and B that minimizes A+B. A=CEIL(1/x) is the smallest number for A. B=CEIL(1/x') is the largest possible B. So the algorithm loops from A to (A+B)/2, computing a B' for each A', and chooses the A that minimizes A+B. Doesn't choose B, as that's for the next iteration. Of course, for large numbers this became ridiculously slow, so I decided to skip values, so it doesn't find the best A and B combination, just something better. It does stop early if: x<1e-12, if A-1/x is <1e-12. I'll post the code later, as I need my desktop to get it from the calc, also it's newRPL so uses LSTO, I need to modify it for classic userRPL but no big deal. On Gene's list it produced the following results: 0.4488: { 4 9 21 55 88 186 399 687 1592 1793 3249804 } with error*1e12 = 0.025 Sum = 3254638, it clearly messed up in that case, as it did worse than the basic algo. 0.422618262: { 4 10 26 54 140 216 472 1108 1185 1503201 } with error*1e12=0.28 Sum = 1506416, now it starts to shine! compare with the last term of the classic algorithm 0.41421356: { 5 9 19 38 81 177 327 681 1161 1296 4549516 } with error*1e12=0.033 Sum = 4553310 0.853: { 2 5 12 28 58 129 211 3384 633 825 1797 1737 7658074 } with error*1e12=0.011 Sum = 7666895 0.5: { 2} with error 0 Total code size is 604 bytes on newRPL (should be around 450 bytes on classicRPL but let's ignore that for now and use 604 bytes). The total sum of the denominators for all 5 numbers is 16981261 16981261/1e7*604 = 1025.7, so that's the first term of the score. the sum of error*1e12 multiplied by 100 only adds 35 points to the score. Final score: 1061 Here's the code: Code:
Code:
|
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 5 Guest(s)