1
\$\begingroup\$

Continued from the previous post - a brute-force approach to calculating all the vectors from 0 to n.

I've come up with yet another solution, after I've realized that the vector takes up too much memory. But it is still not satisfactory, and is quite slow to the point that it is noticeable even on my local machine. I know that this code can be made in such a way that it only requires one for-loop, but I am not sure on how to implement that.

#include <math.h>
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
    uint64_t number, leastMultipleOf2, powerOfTwo, maxFusc;
    std::vector<uint64_t> saveVector = {1, 2, 1};
    std::cin >> number;
    if (number==0 || number==1) {
        maxFusc = number;
    } else {
        powerOfTwo = floor(log2(number));
        leastMultipleOf2 = pow(2.0, powerOfTwo)/2;
        saveVector.reserve(leastMultipleOf2+1);
        for(int i=1; i<powerOfTwo; i++) {
            maxFusc = *max_element(saveVector.begin(), saveVector.end());
            for(int j=1; j <= (2*pow(2.0, i))-1; j+=2) {
                saveVector.insert(saveVector.begin() + j, saveVector[j-1] + saveVector[j]);
            }
        }
        maxFusc = std::max(maxFusc, *max_element(saveVector.begin(), saveVector.begin()+(number-(2*leastMultipleOf2)+1)));
    }
    std::cout << maxFusc << std::endl;
}

What improvements can be done on this snippet of code?

\$\endgroup\$
1
1
\$\begingroup\$

Prefer the C++ header <cmath>. This puts the relevant functions into the std namespace.

Talking of namespace, several other identifiers are used without the necessary qualification (std::uint64_t, std::max_element).

We use >> streaming without any checking for successful conversion.

We use std::endl when a plain newline would be sufficient.

std::uint64 isn't a required type - prefer one of the guaranteed types unless you need exactly 64 bits.

Don't declare all the variables up front. Prefer to minimise scope, and if possible, declare and initialise in one.

Prefer integer << to std::pow(2.0, x). It's more exact, and faster.

Create a function instead of cramming everything into main().

Why are we examining the entire array with std::max_element() every time around the loop? Do it just once at the end, or update maxFusc as we go.

Whilst we can reason about this particular sequence to come up with a faster method, I got several hundred times speedup simply using the obvious approach of computing each value from its previously-calculated dependent values:

#include <cstdlib>
#include <iostream>
#include <vector>

using Number = std::int_fast64_t;

Number max_fusc(Number n)
{
    if (n <= 1) {
        return n;
    }

    std::vector<Number> cache(n);
    cache[1] = 1;

    Number max{0};
    for (Number i = 2;  i < n;  ++i) {
        cache[i] = cache[i/2] + i % 2 * cache[i/2+1];
        if (cache[i] > max) {
            max = cache[i];
        }
    }

    return max;
}

int main()
{
    Number number;
    std::cin >> number;
    if (!std::cin) {
        std::cerr << "Invalid input\n";
        return EXIT_FAILURE;
    }
    std::cout << max_fusc(number) << '\n';
}
\$\endgroup\$
7
  • \$\begingroup\$ This won't pass the SPOJ tester - says that the answer is wrong. But I've tested this locally, and it is working fine till 10^7 - greater than that, this code fails to run, just like the previous implementation. \$\endgroup\$ Nov 3 at 12:53
  • \$\begingroup\$ Perhaps the online challenge has other constraints - a common one is that it wants the results modulo some other number (often 1'000'000'007, I think). \$\endgroup\$ Nov 3 at 13:16
  • \$\begingroup\$ If you want to evaluate the function for larger values, then we need to use more of the properties of the function. Works fine here with 10⁸ as input (giving result 317811) but larger values obviously require more memory for the result cache. \$\endgroup\$ Nov 3 at 13:17
  • \$\begingroup\$ This was what I saw as generic - f(2n) = f(n) and f(2n+1) = f(n) + f(n+1) - using this would force us to use brute force. If we go down a little, it talks about arithmetic progression, and so I was thinking that maybe we could leverage that? But then, traversal of vectors is very slow, when we reach the order of 10^7. Should it be better that we use array? \$\endgroup\$ Nov 3 at 13:24
  • 1
    \$\begingroup\$ The constraint given by SPOJ is \$n \le 10^{15}\$. Paired with the memory limit of 1536 MB it effectively prohibits any cache-based solution. \$\endgroup\$
    – vnp
    Nov 3 at 16:59
0
\$\begingroup\$

Given the constraints not mentioned in the question (namely that input may be as large as 10¹⁵ and memory use is limited to 1½ GB), this loop is not the way to approach this problem:

    for(int i=1; i<powerOfTwo; i++) {

Instead, we'll want to find ways to determine the maximum value by examining the properties of the sequence. It probably helps to consider the binary representation of numbers, given the importance of dividing by two to the definition of the function.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.