1
\$\begingroup\$

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 Ti and Tj 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 Ti and Tj 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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Are you saying that your program takes much longer to run than 3 seconds? Or is it fast enough but you would like to know how to make it even faster? \$\endgroup\$
    – mkrieger1
    Jan 17, 2018 at 17:33
  • \$\begingroup\$ The link just seems to go to a generic page, without any problem statement. That's why we want sufficient context in the body of the question to be able to understand the purpose of the code! \$\endgroup\$ Jan 18, 2018 at 12:09

2 Answers 2

1
\$\begingroup\$

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;

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

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.

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