SOLUTION: Code Jam problem posted by Gu on students@LAC

By Hareesh Nagarajan

Slashdot? Solution in Haskell Solution in Haskell (description)

Click here to see the problem

Look at the solutions below

My C++ Solution (Example with Path = 56448)
My C++ Solution (Example with Path = 108)
Dave Hanley's (ctchrinthry AT gmail.com) SML solution (with comments)
Dave Hanley's (ctchrinthry AT gmail.com) SML solution

[MODIFICATION TO THE PROBLEM] My solution where we cannot reuse an element which we have already picked
Solution (Modified problem)

Sample run

hareesh: code-jam/ $ g++ cjam-aaaa.cc -ocjaaa
hareesh: code-jam/ $ ./cjaaa 
108

hareesh: code-jam/ $ g++ cjam.cc -ocjam         
hareesh: code-jam/ $ ./cjam 
56448

hareesh: code-jam/ $ g++ cjam-cannot-reuse.cc -ocjam-cannot
hareesh: code-jam/ $ ./cjam-cannot 
24

Solution with some micro optimizations and some compiler optimizations turned on
Optimized Solution (Example with Path = 56448)

g++ -DNDEBUG cjam-optimized.cc -O3 -fomit-frame-pointer -ocjam-opti

Timing

hareesh: code-jam/ $ time ./cjam-opti2
56448

real    0m0.012s
user    0m0.010s
sys     0m0.001s

hareesh: code-jam/ $ time ./cjam-opti2
56448

real    0m0.015s
user    0m0.010s
sys     0m0.001s

Inefficient Solution (Example with Path = -1)

g++ -DNDEBUG cjam-tirupati.cc -O3 -funroll-all-loops -fomit-frame-pointer -ocjam-tirupati

hareesh@ncdm153:~$ time ./cjam-tirupati 
-1

real    0m2.494s
user    0m2.491s
sys     0m0.001s
hareesh@ncdm153:~$ time ./cjam-tirupati 
-1

real    0m2.499s
user    0m2.492s
sys     0m0.003s