Calculating number of unharmed leaves

Question

I recently came across this problem that asks you to print the number of leaves not eaten by the caterpillars:

As we all know caterpillars love to eat leaves. Usually, a caterpillar sits on leaf, eats as much of it as it can (or wants), then stretches out to its full length to reach a new leaf with its front end, and finally "hops" to it by contracting its back end to that leaf.

We have with us a very long, straight branch of a tree with leaves distributed uniformly along its length, and a set of caterpillars sitting on the first leaf. (Well, our leaves are big enough to accommodate upto 20 caterpillars!). As time progresses our caterpillars eat and hop repeatedly, thereby damaging many leaves. Not all caterpillars are of the same length, so different caterpillars may eat different sets of leaves. We would like to find out the number of leaves that will be undamaged at the end of this eating spree. We assume that adjacent leaves are a unit distance apart and the length of the caterpillars is also given in the same unit.

For example suppose our branch had 20 leaves (placed 1 unit apart) and 3 caterpillars of length 3, 2 and 5 units respectively. Then, first caterpillar would first eat leaf 1, then hop to leaf 4 and eat it and then hop to leaf 7 and eat it and so on. So the first caterpillar would end up eating the leaves at positions 1,4,7,10,13,16 and 19. The second caterpillar would eat the leaves at positions 1,3,5,7,9,11,13,15,17 and 19. The third caterpillar would eat the leaves at positions 1,6,11 and 16. Thus we would have undamaged leaves at positions 2,8,12,14,18 and 20. So the answer to this example is 6.

Fortunately, the question is easy and can put a workable code in a decent time. The problem is that it is probably taking more memory than expected, because all the test cases run fine in my PC, but one of them gives a runtime error when run on the servers. How can this be improved?

#include <iostream>
#include <vector>
#include <algorithm>

int main (int argc, char const* argv[])
{
    long long n , k;
    std::cin >> n >> k;
    std::vector<int> caterpillars;
    std::vector<long long>v;
    for(int i=0;i<k;i++){
        int a;
        std::cin >> a;
        caterpillars.push_back(a);
    }
    for(int i=0;i<k;i++){
        for(int j=0;caterpillars[i]*j +1 <= n;j++){
            int temp = caterpillars[i] * j +1;
            v.push_back(temp);
        }
    }
    sort(v.begin(),v.end());
    int number = 0;
    long long prev = 0;
    for(int i=0;i<v.size();i++){
        if(v[i] != prev){
            number++;
        }
        prev = v[i];
    }
    std::cout << n - number << std::endl;
    return 0;
}

And here is that particular testcase which is causing problems:

762744433 19
96412 40852 19611 563380 236733 559627 750968 413673 300332 65 682403 441221 180068 668364 493413 443706 613246 715846 728157

Answer 1

Uses too much memory, and too much time

Your current solution works but uses too much memory. The problem requirement specifies maximum 16 MB memory to be used. Your program uses 4 bytes for each number reached including duplicates. Given the maximum n of 1000000000, maximum caterpillars of 20, and worst case of each caterpillar having value 2, your program would require 40 GB of memory to solve that case.

Also, your program takes too long to run. Given the worst case scenario mentioned above, your program would need to iterate 10 billion times. Even at a rate of 1 billion iterations per second, that would take 10 seconds and your time limit is 3.

I will describe some incremental improvements to your solution to fix the memory issue, and then describe a completely different approach that solves the time issue as well.

Slightly better: use sieve approach

Instead of adding reached numbers to a vector and then sorting, you can do better by creating a std::bitset or vector<bool> to store which numbers were reached. For example, you could create a vector<bool> of size n+1, and then as you reach each number, you set reached[num] = true. At the end, you scan the vector to count many numbers are unreached. Assuming that vector<bool> uses 1 bit per element, this solution requires 125 MB of memory, which is still larger than permitted. However, this at least won't crash your computer if you run it. Here is a sample solution:

#include <iostream>
#include <vector>
#include <algorithm>

int main (int argc, char const* argv[])
{
    long long n , k;
    std::cin >> n >> k;
    std::vector<int> caterpillars;
    std::vector<long long>v;
    for(int i=0;i<k;i++){
        int a;
        std::cin >> a;
        caterpillars.push_back(a);
    }
    std::vector<bool> reached(n);
    for(int i=0;i<k;i++){
        int val = caterpillars[i];
        for(int j=0;j < n;j+= val) {
            reached[j] = true;
        }
    }
    int unreached = 0;
    for(int j=0;j < n;j++) {
        if (!reached[j])
            unreached++;
    }
    std::cout << unreached << std::endl;
    return 0;
}

This program solved the "tough case" 762744433 19 ... in 0.9 seconds on my computer. However, on the worst case of 1000000000 20 2 2 2 2 ..., it took 16 seconds to solve, which exceeds the time limit of 3 seconds.

Next improvement: use fixed amount of memory

To keep your program within the 16 MB memory limit, you need to do the sieving in segments instead of all at once. For example, you can compute the solution in segments of 1000000, using only 125 KB of memory for the vector<bool>. Here is an example of how you can do that:

#include <iostream>
#include <vector>
#include <algorithm>

#define BUFSIZE        1000000

int main (int argc, char const* argv[])
{
    long long n , k;
    std::cin >> n >> k;
    std::vector<int> caterpillars;
    std::vector<long long>v;
    for(int i=0;i<k;i++){
        int a;
        std::cin >> a;
        caterpillars.push_back(a);
    }
    std::vector<bool> reached(BUFSIZE);
    int unreached = 0;
    for(int i=0;i<n;) {
        int size = n-i;
        if (size > BUFSIZE)
            size = BUFSIZE;
        std::fill(reached.begin(), reached.end(), false);
        for (int j=0;j<k;j++) {
            int val = caterpillars[j];
            int first = (i % val);
            if (first != 0)
                first = val - first;
            for (int r = first; r < size; r += val)
                reached[r] = true;
        }
        for (int r = 0; r < size; r++) {
            if (!reached[r])
                unreached++;
        }
        i += size;
    }
    std::cout << unreached << std::endl;
    return 0;
}

Similar to the previous program, this program also solved the "tough case" in 0.9 seconds. It took 14 seconds to solve the worst case, though. Although there are some optimizations that could be made, it seems that a new algorithm might be needed.

A different approach

This problem is somewhat reminiscent of the FizzBuzz problem. In FizzBuzz, each number divisible by 3 is Fizz, each number divisible by 5 is Buzz, and each number divisible by both 3 and 5 is FizzBuzz. If I asked how many numbers between 1 and n are one of Fizz/Buzz/FizzBuzz, you could come up with a \$O(1)\$ solution instead of an \$O(n)\$ solution.

If you think about it a little, n/3 numbers are either Fizz or FizzBuzz, and n/5 numbers are either Buzz or FizzBuzz, and n/15 numbers are FizzBuzz. So the count of "named" numbers is n/3 + n/5 - n/15.

You can transfer this approach to the caterpillar problem. Given 2 caterpillars of length a b, the number of leaves eaten is n/a + n/b - n/lcm(a,b), where lcm() is the least common multiple of a and b.

Now you can extend the approach for 3 caterpillars. With three caterpillars of length a b c, you can have leaves eaten by a, b, c, ab, bc, ac, or abc, where ab means eaten by both a and b. After doing some reasoning on this, you would come up with the formula:

Leaves eaten = n/a + n/b + n/c - n/lcm(a,b) - n/lcm(b,c) - n/lcm(a,c) + n/lcm(a,b,c)

The formula generalizes to:

Leaves eaten = Sum(n/one) - Sum(n/two) + Sum(n/three) - Sum(n/four) + Sum(n/five) - ...

where Sum(n/five) means the sum of all combinations of the form n/lcm(five caterpillars).

To solve using this method, you need to generate each combination of caterpillars. With 20 caterpillars, this means you need to go through each of the \$2^{20}\$ combinations, which is actually only 1 million combinations so it should complete quickly. In general, with \$k\$ caterpillars, this solution solves the problem in \$O(2^k)\$ time. So you definitely do not want to use this solution with a large number of caterpillars.

I wrote a sample solution that used recursion to generate each combination. The solve() function tries two cases: including the current caterpillar or not including it, and recurses to the next caterpillar for each case. You can easily see that this generates 2^k cases.

Here is my solution using this approach:

#include <iostream>
#include <vector>
#include <algorithm>

// Returns greatest common divisor of a and b.
static inline int gcd(int a, int b)
{
    while (b != 0) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

// Returns least common multiple of a and b.
static inline long long lcm(int a, int b)
{
    a /= gcd(a, b);
    return (long long) a * b;
}

static int solve(std::vector<int> caterpillars, int curCaterpillar,
        int numUsed, int curLcm, int n)
{
    if (curCaterpillar >= caterpillars.size())
        return 0;

    int val = caterpillars[curCaterpillar];
    int reached = 0;

    // Include current caterpillar:
    long long newLcm = lcm(curLcm, val);
    if (newLcm <= n) {
        if (numUsed & 1)
            reached -= n / newLcm;
        else
            reached += n / newLcm;
        reached += solve(caterpillars, curCaterpillar+1, numUsed+1, newLcm, n);
    }

    // Do not include current caterpillar:
    reached += solve(caterpillars, curCaterpillar+1, numUsed, curLcm, n);

    return reached;
}

int main (int argc, char const* argv[])
{
    long long n , k;
    std::cin >> n >> k;
    std::vector<int> caterpillars;
    std::vector<long long>v;
    int reached = 0;

    for(int i=0;i<k;i++){
        int a;
        std::cin >> a;
        caterpillars.push_back(a);
    }
    n--;
    reached = solve(caterpillars, 0, 0, 1, n);
    std::cout << n - reached << std::endl;
    return 0;
}

This solution solved the "tough case" in 0.01 seconds on my computer, and solved the "worst case" in 0.46 seconds.

There are further optimizations that could be made, such as filtering out caterpillars that are multiples of each other before starting the algorithm. Such caterpillars can be removed without changing the result. Using that optimization, the worst time I got for any input I tried was 0.08 seconds.

Answer 2

So i think there are some possible improvements. The general idea should be to utilize a sieve like approach. In principle i like your code, but similar to the other questions your naming is really bad. Noone knows what n, k or v is. so use descriptive names as you yourself will make tiny mistakes and spend some time searching for that "k" instead of an "n".

1. use std::set for your caterpillars, as there is no benefit in multiple ones of the same length.

   size_t numLeafs , numCaterpillars;
   std::cin >> numLeaves >> numCaterpillars;
   std::set<int> caterpillars;
   for (unsigned caterpillar=0; caterpillar < numCaterpillars; ++caterpillar) {
       int a;
       std::cin >> a;
       caterpillars.insert(a);
   }
   

2. Now you could optimize your set further, by checking for multiples etc.

3. Use a std::array for your leafs, as its size is static. You could obviously also use a bitset.

   std::array<bool> leafs (numLeafs+1, true);
   leafs[0] = false;
   leafs[1] = false;
   

   Note that I have made the array one larger to avoid the cumbersome off by one of the question.

4. Sieve the leafs array, by walking all the multiples of your caterpillar lengths.

   for (int length : caterpillars) {
       size_t currentLeaf = length;
       while (currentLeaf < (numLeafs+1)) {
           leafs[currentLeaf] = false;
           currentLeaf *= length;
       }
   }
   

   Now you can just add up every not visited leaf.

Solution

#include <array>
#include <iostream>
#include <set>

int main () {       
    int numLeafs , numCaterpillars;
    std::cin >> numLeafs >> numCaterpillars;
    std::set<int> caterpillars;
    for (unsigned caterpillar=0; caterpillar < numCaterpillars; ++caterpillar) {
        int a;
        std::cin >> a;
        caterpillars.insert(a);
    }

    std::array<bool> leafs (numLeafs+1, true);
    leafs[0] = false;
    leafs[1] = false;

    for (int length : caterpillars) {
        size_t currentLeaf = length;
        while (currentLeaf < (numLeafs+1)) {
            leafs[currentLeaf] = false;
            currentLeaf *= length;
        }
    }

    size_t result = 0;
    for (bool elem : leafs) {
        if (elem) {
           result++;
            }
        }
    }

Answer 3

I found where the error is, but I don't know where to go from there.

The problem occurs when adding eaten leaf to "v" vector:

    for(int i=0;i<k;i++){
    for(int j=0;caterpillars[i]*j +1 <= n;j++){
        int temp = caterpillars[i] * j +1;
        v.push_back(temp);
    }
}

if you comment the "v.push_back(temp)" line, no run time error occurs. Maybe the vector grows too big for their system, or it could be a different problem. My knowledge in C++ is limited to answer that, perhaps someone more experienced will solve it..

Tip: You could find where the run time errors on their system occur, by adding comments to specific segments of the code, submit it and check their review if such error exist. That's how I isolated the error.