4
\$\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)

or, equivalently:

  • F(0) and F(1) is 0 and 1 respectively
  • For any even argument, the value is F(2n) = F(n)
  • For any odd argument, the value is F(2n + 1) = F(n) + F(n+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\$
2
  • \$\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
    Commented Nov 1, 2021 at 13:47
  • \$\begingroup\$ @Teepeemm I've added an unambiguous definition of F() from the SPOJ site. \$\endgroup\$
    – CiaPan
    Commented May 16 at 5:57

5 Answers 5

8
\$\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\$
6
  • \$\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
    Commented Oct 31, 2021 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
    Commented Oct 31, 2021 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
    Commented Oct 31, 2021 at 13:17
  • \$\begingroup\$ @AshvithShetty What values of n did you try? It might be that when you submit it, they try a value of n such that your code allocates too much memory. \$\endgroup\$
    – G. Sliepen
    Commented Oct 31, 2021 at 19:36
  • \$\begingroup\$ I doubt it matters. Again, the problem statement says n can be up to 10^15, and just naively allocating a vector of 10^15 elements will surely use more memory than is available. \$\endgroup\$
    – G. Sliepen
    Commented Oct 31, 2021 at 19:47
4
\$\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\$
4
\$\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\$
3
\$\begingroup\$

scanf() is not for reading input, it's for parsing input:

scanf() is not a function I use or suggest for reading input (it is meant to parse formatted data), but I understand that fgets() + snprintf()/strtol()... would add more complexity and function calls.

The least that can be done is:

if (scanf("%d", &n) != 1) {
    fprintf(stderr, "Error: invalid input.");
    return EXIT_FAILURE; // <cstdlib>
}

Note that if the input exceeds the maximum value that an int can hold, the behaviour is undefined. (There's no redemption once undefined behavior has been invoked, you can't possibly avoid this. You can not somehow magically go back in time and fix things once the damage has been done.)

scanf() is defined by the ISO C Standard, which says (C11 7.21.6.2 The fscanf function /10):

If this object does not have an appropriate type, or if the result of the conversion cannot be represented in the object, the behavior is undefined.

Same for C18, and C23/C24.

Also note that if the conversion failed, n would remain uninitialised, but the behaviour wouldn't be undefined per se, because its address has been taken, assuming it doesn't have a trap representation, in which case the code will always invoke undefined behaviour. Otherwise, if there are no trap representations, the variable takes an unspecified value.

Though your code may not invoke undefined behavior, the answer would be incorrect because you'd be processing something that wasn't what was provided as input.

Aside: It is more conventional to use the the C++ counterparts of the C headers (they're prefixed with c, and .h is left off). Unqualified scanf() comes from the C compatibility header <stdio.h> - when using the C++ header <cstdio> one should use standard-namespace std::scanf(). Same goes for printf().

See: (Why) is using an uninitialized variable undefined behavior?.

\$\endgroup\$
2
\$\begingroup\$

Don’t Calculate values Unnecessarily

For odd n > 1, F(n) = F(n/2) + F(n/2 + 1) = F(n - 1) + F(n + 1). F(0) < F(1) = F(2). This means that any odd number has a fusc value greater than or equal to both of the even numbers above or below it. You don’t need to compare to them.

Furthermore, for odd n > 1, F(n - 1) = F(n/2 - 1) + F(n/2), meaning that F(n) > F(n-2) iff f(n/2 + 1) > f(n/2 - 1). If they are twin odd numbers, you can tail-recurse this same check. If they are both even, dividing both by 2 would get you a pair of adjacent numbers, and by the lemma above, the odd one of the pair has a greater value of F than the even one. You can also ignore any values you know are less than or equal to the lower number, until you encounter one that’s greater. Only at that point would you need to calculate and compare.

It therefore follows that, of any twin even numbers, the one congruent to 2 modulo 4 has a higher F value than the one congruent to 0 modulo 4.

Also for odd n > 1, F(n) > F(n/2 + 1), so scanning from top to bottom, you know that it is safe to check only values above half the upper bound. All values below this are guaranteed to be less than or equal to a number you’ve already checked.

Note that you do not need to actually calculate the values of fusc to determine which number is greater than its immediate neighbors, but you will need to calculate and compare another value that you only know is greater than some other value. You could delay doing this if it is less than the next odd number past it, until coming to one that is less than it.

Pass Large Objects by Reference

You’re making a copy of the entire vector of fuscs with each call.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.