3
\$\begingroup\$

I've been trying this question from SPOJ, which asks for the user to enter a number n, and they will receive a maximum fusc value that lies in between 0 to n. The conditions for the function are:

  • F(0) and F(1) is 0 and 1 respectively
  • For any even number, the value is F(n) = F(n/2)
  • For any odd number, the value is F(n) = F(n/2) + F(n/2 + 1)

This is my take on the problem:

#include <algorithm>
#include <vector>
#include <stdio.h>
int fusc(int num, std::vector<int> reg) {
    if(num==0) return 0;
    if(num==1) return 1;
    if(num%2==0) return reg[num/2];
    return (reg[num/2] + reg[num/2 + 1]);
}
int main() {
    int n;
    scanf("%d", &n);
    std::vector<int> reg(n+1);
    for(int i=0;i<=n; i++) reg[i] = fusc(i, reg);
    auto it=std::max_element(std::begin(reg), std::end(reg));
    printf("%d\n", *it);
}

I am not sure about why it is taking a lot of time. It would be great if the poor practices in the code would be highlighted.

\$\endgroup\$
1
  • \$\begingroup\$ Aside: when you write "For any odd number, the value is F(n) = F(n/2) + F(n/2 + 1)", I didn't realize at first that you were using integer division. But now I know. And now anyone else will as well. \$\endgroup\$
    – Teepeemm
    Nov 1 at 13:47
6
\$\begingroup\$

Don't mix C and C++ code

Your code is a mix of C and C++. While you can use functions from C's standard library in C++ code, I recommend you avoid it and write as much as possible using just functions from C++'s standard library. In particular:

#include <iostream>
...
int n;
std::cin >> n;
...
std::cout << *it << '\n';

Use std::uint64_t for n

According to the problem statement, \$0 <= n <= 10^{15}\$. But an int, which is usually only 32 bits, can only hold values up to a little over \$10^9\$. So you have to ensure you pack an integer type that is large enough to hold the maximum possible input value. Also, since n will never be negative, use an unsigned type. The standard library provides various fixed-width integer types, the right one here is std::uint64_t.

While the maximum fusc value of n doesn't grow very fast, I would also use a std::vector<std::uint64_t> to store the fusc values, unless you can prove that the maximum fusc value of \$10^{15}\$ is less than \$2^{31}\$.

Pass large objects by reference where appropriate

When you call fusc(), you are passing it the vector with results so far by value. That means a complete copy is made. Since you do that n times, that is very costly. Pass it by reference instead::

int fusc(int num, std::vector<std::uint64_t> &reg) {
    ...
}

Keep track of the maximum while building reg

You are first building the vector reg by adding elements to it, and then you call std::max_element() which goes over the whole vector again. It is faster to just keep track of the maximum value while you are building the vector reg:

std::uint64_t max_fusc = 0;

for (uint64_t i = 0; i <= n; ++i) {
    reg[i] = fusc(i, reg);
    max_fusc = std::max(max_fusc, reg[i]);
}

std::cout << max_fusc << '\n';

Use reserve() and push_back()

If you declare a vector of a given size like so:

std::vector<int> reg(n+1);

It will actually cause all elements of the vector to be filled with zeroes. But you are going to overwrite them later anyway, so this is wasting some time. You can avoid it by not specifying the size up front, but instead using the reserve() method to let the vector allocate all the memory you are going to need for it, and then use push_back() to add the values you calculated:

std::vector<std::uint64_t> reg;
reg.reserve(n + 1);
reg.push_back(0);
reg.push_back(1);
std::uint64_t max_fusc = n ? 1 : 0;

for(std::uint64_t i = 2; i <= n; ++i) {
    reg.push_back(i % 2 == 0 ? reg[i / 2] : reg[i / 2] + reg[i / 2 + 1]);
    max_fusc = std::max(max_fusc, reg.back());
}

Other optimizations

I did some other optimizations in the code above. In your fusc(), you were checking if num was 0 or 1. This is only necessary for the first two calls to fusc(), afterwards it is redundant. You can just add the first two elements to reg manually, then you don't have to deal with these special cases anymore. With this, fusc() is so simple that I just removed it.

The initialization of max_fusc is also done such that your program will still give the correct output if n is 0 or 1.

You can probably do more optimizations as well, by using knowledge about how the fusc sequence progresses. There is already some information on the SPOJ page you mentioned: if you split the sequence in to groups of size 1, 2, 4, 8 and so on, you will notice some structure: each group is a mirror of itself, and the maximum of a group is always a Fibonacci number. This means that for half the possible values of \$n\$, you can just get away with calculating the \$2+\left\lfloor\log_2{n}\right\rfloor\$th Fibonacci number, and for the other half of the possible values of \$n\$ you at least know that that Fibonacci number is the upper bound, and the previous Fibonacci number is a lower bound.

Also look at the Wikipedia page about the Calkin-Wilf tree for an interesting read of where the fusc sequence pops up.

\$\endgroup\$
9
  • \$\begingroup\$ Competitive programmer guys use scanf/printf because they believe cin/cout is slow. Better to mention std::ios_base::sync_with_stdio(false) \$\endgroup\$
    – frozenca
    Oct 31 at 9:57
  • 4
    \$\begingroup\$ @frozenca It shouldn't matter here, it's just reading and printing a single number. It might be different if I/O is a large part of the work that has to be done. \$\endgroup\$
    – G. Sliepen
    Oct 31 at 11:05
  • \$\begingroup\$ There's so much more to exploit; the first occurrence of a Fibonacci number is at an index which is a Jacobsthal number, fucs(2 * n) is always smaller than fucs(2 * n - 1) and fucs(2 * n + 1). I suspect there must be some way to use a binary search to get the answer, but I'm already nerdsniped enough. \$\endgroup\$
    – G. Sliepen
    Oct 31 at 13:17
  • \$\begingroup\$ @G.Sliepen not sure what's happening when I submit the answer online, but it is throwing a runtime error (SIGABRT). What do you suspect could be the issue? It runs fine locally, by the way. \$\endgroup\$ Oct 31 at 18:07
  • 1
    \$\begingroup\$ @G.Sliepen I doubt using vectors to calculate each and every value would be a good idea. Instead, I believe that maybe using the arithmetic progression would be beneficial. But I am not sure how we can implement that - although I can see that the next series progresses with adding the two numbers, and placing the product between them in the new array. For example, if we start with (1, 2), then add 1+2, which gives 3. Now place the new sum before 2, and mirror the pattern, but remove 1 - we get (1, 3, 2 | 3). The next pattern will be (1, 4, 3, 5, 2 | 5, 3, 4). \$\endgroup\$ Nov 2 at 13:13
3
\$\begingroup\$

Don't ignore crucial return values

G. Sliepen has covered nearly all the things I was going to say (in particular, passing the array by value is your key performance problem).

The only thing I have to add to that answer is in regard to this line:

    scanf("%d", &n);

If we ignore the return value from std::scanf(), we have no idea whether n was successfully assigned to. If there's any conversion failure, we will be operating on an uninitialized value, rather than reporting the error to the user.

The equivalent when using C++ I/O is testing the state of std::cin after using the >> streaming operator - again, without that test, the program is faulty.

\$\endgroup\$
0
\$\begingroup\$

I am not sure about why it is taking a lot of time

Well, this pops out: int fusc(int num, std::vector<int> reg)

Why are you passing reg by value? You are copying the entire vector each time you call the function, and then throwing away the local copy after each function call. This causes memory allocation and deallocation, which is slow.

It is very unusual to pass non-primitive things by value in C++, so this should stand out as an immediate red flag when you look over the code. We expect to see const std::vector<int>& reg instead.

If you're new to C++ and used to languages with reference semantics (where "objects" are actually pointers), this might go unnoticed.

\$\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.