5 ms·

That was fun, good waste of time while my code was compiling. I just used C++ and hacked up a prime seive for #2 and for #3 used a combination generator I had p

by grogers 16y ago

That was fun, good waste of time while my code was compiling. I just used C++ and hacked up a prime seive for #2 and for #3 used a combination generator I had previously used before - http://photon.poly.edu/~hbr/boost/combinations.html http://photon.poly.edu/~hbr/boost/combinations.html

cperciva 16y ago
for #3 used a combination generator Congratulations, you just used an exponential-time algorithm for a polynomial-time problem.
- Deestan 16y ago
  Congratulations are in order, he sacrificed 400ms CPU time to save at least a few minutes of coding time.
  - cperciva 16y ago
    I wasn't being entirely sarcastic. It never occurred to me that you could use a non-polynomial-time algorithm.
    - util 16y ago
      All the solutions posted here seem to involve generating all subsequences. Could you say more about your approach?
- dsc 16y ago
  Not always is "exponential" a bad thing. For small sets, the expo algorithm is actually faster than the polynomial one. Although yeah, generally speaking, it's a bad idea.
  - ay 16y ago
    I tried on #3 the most inefficient algorithm I could come up with - blindly going through all possible combinations and checking if their biggest member is equal to the sum of the rest. Time of the execution: 0.6s I am not sure if this step of allowing the "shortcuts" was part of the game or not. All that would had to be done is to give 128 elements of the array to exclude at least the most blatant brute-forcing.