Codechef Deforestation problem: Finding maximum rope length between trees

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;







up vote
1
down vote

favorite












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.







share|improve this question

















  • 1




    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?
    – mkrieger1
    Jan 17 at 17:33










  • 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!
    – Toby Speight
    Jan 18 at 12:09
















up vote
1
down vote

favorite












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.







share|improve this question

















  • 1




    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?
    – mkrieger1
    Jan 17 at 17:33










  • 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!
    – Toby Speight
    Jan 18 at 12:09












up vote
1
down vote

favorite









up vote
1
down vote

favorite











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.







share|improve this 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 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.









share|improve this question












share|improve this question




share|improve this question








edited Jan 17 at 23:08









200_success

123k14143401




123k14143401









asked Jan 17 at 17:05









NanBlanc

111




111







  • 1




    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?
    – mkrieger1
    Jan 17 at 17:33










  • 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!
    – Toby Speight
    Jan 18 at 12:09












  • 1




    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?
    – mkrieger1
    Jan 17 at 17:33










  • 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!
    – Toby Speight
    Jan 18 at 12:09







1




1




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?
– mkrieger1
Jan 17 at 17:33




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?
– mkrieger1
Jan 17 at 17:33












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!
– Toby Speight
Jan 18 at 12:09




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!
– Toby Speight
Jan 18 at 12:09










2 Answers
2






active

oldest

votes

















up vote
1
down vote













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;







share|improve this answer




























    up vote
    1
    down vote













    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.






    share|improve this answer





















      Your Answer




      StackExchange.ifUsing("editor", function ()
      return StackExchange.using("mathjaxEditing", function ()
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
      );
      );
      , "mathjax-editing");

      StackExchange.ifUsing("editor", function ()
      StackExchange.using("externalEditor", function ()
      StackExchange.using("snippets", function ()
      StackExchange.snippets.init();
      );
      );
      , "code-snippets");

      StackExchange.ready(function()
      var channelOptions =
      tags: "".split(" "),
      id: "196"
      ;
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function()
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled)
      StackExchange.using("snippets", function()
      createEditor();
      );

      else
      createEditor();

      );

      function createEditor()
      StackExchange.prepareEditor(
      heartbeatType: 'answer',
      convertImagesToLinks: false,
      noModals: false,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: null,
      bindNavPrevention: true,
      postfix: "",
      onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      );



      );








       

      draft saved


      draft discarded


















      StackExchange.ready(
      function ()
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f185334%2fcodechef-deforestation-problem-finding-maximum-rope-length-between-trees%23new-answer', 'question_page');

      );

      Post as a guest






























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes








      up vote
      1
      down vote













      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;







      share|improve this answer

























        up vote
        1
        down vote













        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;







        share|improve this answer























          up vote
          1
          down vote










          up vote
          1
          down vote









          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;







          share|improve this answer













          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;








          share|improve this answer













          share|improve this answer



          share|improve this answer











          answered Jan 17 at 23:40









          Austin Hastings

          6,1591130




          6,1591130






















              up vote
              1
              down vote













              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.






              share|improve this answer

























                up vote
                1
                down vote













                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.






                share|improve this answer























                  up vote
                  1
                  down vote










                  up vote
                  1
                  down vote









                  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.






                  share|improve this answer













                  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.







                  share|improve this answer













                  share|improve this answer



                  share|improve this answer











                  answered Jan 18 at 12:08









                  Toby Speight

                  17.8k13491




                  17.8k13491






















                       

                      draft saved


                      draft discarded


























                       


                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function ()
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f185334%2fcodechef-deforestation-problem-finding-maximum-rope-length-between-trees%23new-answer', 'question_page');

                      );

                      Post as a guest













































































                      Popular posts from this blog

                      Chat program with C++ and SFML

                      Function to Return a JSON Like Objects Using VBA Collections and Arrays

                      Will my employers contract hold up in court?