Codechef Deforestation problem: Finding maximum rope length between trees
Clash 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.
c++ performance programming-challenge
add a comment |Â
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.
c++ performance programming-challenge
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
add a comment |Â
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.
c++ performance programming-challenge
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.
c++ performance programming-challenge
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
add a comment |Â
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
add a comment |Â
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;
add a comment |Â
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.
add a comment |Â
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;
add a comment |Â
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;
add a comment |Â
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;
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;
answered Jan 17 at 23:40
Austin Hastings
6,1591130
6,1591130
add a comment |Â
add a comment |Â
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.
add a comment |Â
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.
add a comment |Â
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.
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.
answered Jan 18 at 12:08
Toby Speight
17.8k13491
17.8k13491
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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