Codechef Deforestation problem: Finding maximum rope length between trees

Question

Here is the CodeChef page to the problem. Given N trees, each at x-position x with height T, string a rope between two trees T_i and T_j such that:

• A rope connecting the tops of the trees is at 45 degrees from the x-axis
• The rope does not pass through any other trees
• The length of the rope, minus the total height reduction by cutting trees, is maximized
• Trees T_i and T_j themselves are not cut

Here is my code that need to process 100 × 250,000 data in less than 3 seconds (I don't know the exact spec of the running machine). As I'm quite new to coding, what can I improve or change to make it faster, and more optimized?

// codechef_deforestation.cpp : définit le point d'entrée pour l'application console.
//

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <ctime>

int main()
{
    clock_t startTime = clock();
    //Read input
    freopen("C:\\somepath\\input.in", "r", stdin);
    freopen("C:\\somepath\\output.out", "w", stdout);
    int t;
    std::cin >> t;
    //std::cout << t << std::endl;
    for (int i = 0; i < t; i++)
    {
        double result = -1;
        int n;
        std::cin >> n;
        //std::cout << t << std::endl;
        std::vector <int> x, h;
        x.resize(n);
        h.resize(n);
        //chargement des données
        for (int j = 0; j < n; j++)
        {
            std::cin >> x[j] >> h[j];
            //std::cout << x[j] << h[j] << std::endl;
        }
        //calcul
        for (int j = 0; j < n; j++)
        {
            for (int k = j+1; k < n; k++)
            {
                //std::cout << "k : " << k << std::endl;
                int diff_x = x[k] - x[j];
                int diff_h = h[k] - h[j];
                if (diff_x == diff_h) //si 45 deg
                {
                    double res_int = sqrt(diff_x*diff_x + diff_h* diff_h);
                    for (int l = j + 1; l < k; l++)
                    {
                        //std::cout << "l : " << l << std::endl;
                        if (h[l] > x[l])
                        {
                            res_int = res_int - (h[l] - x[l]);
                        }
                    }
                    if (res_int > result)
                    {
                        result = res_int;
                    }
                }
            }   
        }
        std::cout << std::setprecision(6) << std::fixed << result << std::endl;
        x.clear();
        h.clear();
    }
    clock_t testTime=clock();
    std::cout << testTime - startTime;
    return 0;
}

The freopen() function needs to stay.

Answer 1

There appears to be a bug in your program. In particular, I think this line is wrong:

if (h[l] > x[l])

Starting from location j, the question is not whether h[l] > x[l] but whether h[l] - h[j] > x[l] - x[j]. The 45 degree angle will be relative to the start-point of the line, not the origin, I think.

That said, your loop over l is duplicating the results of looping over k. I think you could profit by keeping a running total of lossage during your k loop, and just adding it in when appropriate.

Viz:

for (j...)
    auto hj = h[j], xj = x[j];

    for (k...)
        auto dx = x[k] - xj;
        auto dh = h[k] - hj;

        auto over_height = dh - dx;

        if (over_height > 0) deforestation += over_height;

        if (over_height == 0) {
            // this k is a candidate
            rope_len = sqrt(...) - deforestation;

        }

Answer 2

Headers

Missing include:

#include <cstdio> // for std::reopen

Some identifiers (std::freopen, std::sqrt, std::clock_t, std::clock) are missing their namespace prefix. This is probably because your compiler defines those identifiers in the global namespace as well as in the std namespace, as it's allowed (but not required) to do. This means that your code isn't portable to other compliant implementations. Thankfully, the error is easy to fix.

File manipulation

I assume that the redirection of input and output is a requirement of your challenge:

//Read input
std::freopen("C:\\somepath\\input.in", "r", stdin);
std::freopen("C:\\somepath\\output.out", "w", stdout);

I think it would be better if it were split into its own function, as it's tangential to the problem algorithm. In any case, you should probably check the return values and (at least) warn the user if either reopen fails.

Even better would be for you to provide the review version with its own test-cases, so we can verify that improvements give the same results.

Variable names

int t;
std::cin >> t;

Is t the number of trees? If so, give it a name that reflects its purpose. And check the return value of >> - otherwise using t is Undefined Behaviour, as it's never been initialized.

Use the correct types

The spec doesn't say that x and h are integer types - consider whether they should be double.

Commented-out code

    //std::cout << t << std::endl;

Did you really mean to present these for review? Either implement a proper "verbose mode" (and you might want to send the information to std::cerr, so as to play nicely in a pipeline), or remove them altogether.

Algorithm

            if (diff_x == diff_h) //si 45 deg

Is this test correct? I think the question might want ±45 degrees, in which case, we'll need std::abs.

                double res_int = std::sqrt(diff_x*diff_x + diff_h* diff_h);

This can be written more simply as

                double res_int = std::hypot(diff_x, diff_h);

Even more simply, as we know diff_x == ±diff_h, we can write

                static auto const sqrt_2 = std::sqrt(2);
                double res_int = sqrt_2 * diff_x;

No need to clear vectors that are leaving scope

    x.clear();
    h.clear();
}

Those two lines are pointless, as x and h will be destructed at the end of the block.

Performance hints

You should be able to reduce the amount of work by reversing the inner loop, to start with the most-separated pairs of trees and work inwards. That way, you can exit the inner loop early when a rope would be too short to become a new maximum even without cutting any trees.

Whilst cutting trees, if res_int < result, we can stop cutting and move on to the next pair.