Count sub-sequences of an array having median lying in that subsequence itself

up vote
3
down vote

favorite

We need to calculate the number of sub-sequences of an array having its median lying in the sub-sequence itself. My code is -

#include <bits/stdc++.h> 
using namespace std; 


#define MOD 1000000007
#define fori0n for(int i=0;i<n;i++)
#define inputLoop for(int j=0;j<t;j++)

// FAST SCANNING .. 
template<typename T> void scan(T &x) 




// FAST PRINTING.. 
template<typename T> void print(T n) 
 
 bool neg = 0; 

 if (n < 0) 
 n *= -1, neg = 1; 

 char snum[65]; 
 int i = 0; 
 do
 
 snum[i++] = n % 10 + '0'; 
 n /= 10; 
 

 while (n); 
 --i; 

 if (neg) 
 putchar('-'); 

 while (i >= 0) 
 putchar(snum[i--]); 

 putchar('n'); 
 







float median(vector<int> new_array, int num)
 sort(new_array.begin(), new_array.end());
 float median = (num % 2 != 0) ? (new_array[((num+1)/2)-1]) : (float)(new_array[(num/2)-1] + new_array[num/2]) / 2;
 return median;


void subsetsUtil(vector<int>& A, vector<vector<int> >& res, 
 vector<int>& subset, int index) 
 
for (int i = index; i < A.size(); i++) 

 // include the A[i] in subset. 
 subset.push_back(A[i]); 
 res.push_back(subset); 

 // move onto the next element. 
 subsetsUtil(A, res, subset, i + 1); 

 subset.pop_back(); 
 

return; 
 


vector<vector<int> > subsets(vector<int>& A) 
 
 vector<int> subset; 
 vector<vector<int> > res; 

 // include the null element in the set. 
 //res.push_back(subset); 

 // keeps track of current element in vector A; 
 int index = 0; 
 subsetsUtil(A, res, subset, index); 

 return res; 
 


int main() 
 

//ios_base::sync_with_stdio(false);
//cin.tie(NULL);



int t;
scan(t);
//cin>>t;
inputLoop 
int n;
scan(n);
//cin>>n;

// find the subsets of below vector. 
vector<int> arr; 

int input;
fori0n 
 //cin>>input;
 scan(input);
 arr.push_back(input);


vector<vector<int> > res = subsets(arr); 
int goodMedian = 0;
// Print result 
for (int i = 0; i < res.size(); i++) 



 //cout<<"Sub set : "<<i<<" _ With Size : "<<res[i].size()<<" == ";


 // if size == 1 or 3 
 if(res[i].size() % 2 != 0) 
 // there will always be a good median 
 //cout<<"GOOD MEDIAN ";
 goodMedian++;
 
 else if(res[i].size() == 2) median(res[i], 2) == res[i][1]) 
 //cout<<"GOOD MEDIAN ";
 goodMedian++;
 
 
 else if(res[i].size() % 2 == 0) median(res[i], res[i].size()) == res[i][(size - 1)/2]) 
 //cout<<"GOOD MEDIAN ";
 goodMedian++;
 
 



 //for (int j = 0; j < res[i].size(); j++) 
 // cout << res[i][j] << " "; 
 //cout << endl;


 print(goodMedian % MOD);
 
 return 0;

Can anyone suggest any better algorithm for this problem ?

edited 3 hours ago

200_success

126k14148409

asked 3 hours ago

Aditya Navphule

171

New contributor

add a commentÂ |Â

up vote
3
down vote

favorite

We need to calculate the number of sub-sequences of an array having its median lying in the sub-sequence itself. My code is -

#include <bits/stdc++.h> 
using namespace std; 


#define MOD 1000000007
#define fori0n for(int i=0;i<n;i++)
#define inputLoop for(int j=0;j<t;j++)

// FAST SCANNING .. 
template<typename T> void scan(T &x) 




// FAST PRINTING.. 
template<typename T> void print(T n) 
 
 bool neg = 0; 

 if (n < 0) 
 n *= -1, neg = 1; 

 char snum[65]; 
 int i = 0; 
 do
 
 snum[i++] = n % 10 + '0'; 
 n /= 10; 
 

 while (n); 
 --i; 

 if (neg) 
 putchar('-'); 

 while (i >= 0) 
 putchar(snum[i--]); 

 putchar('n'); 
 







float median(vector<int> new_array, int num)
 sort(new_array.begin(), new_array.end());
 float median = (num % 2 != 0) ? (new_array[((num+1)/2)-1]) : (float)(new_array[(num/2)-1] + new_array[num/2]) / 2;
 return median;


void subsetsUtil(vector<int>& A, vector<vector<int> >& res, 
 vector<int>& subset, int index) 
 
for (int i = index; i < A.size(); i++) 

 // include the A[i] in subset. 
 subset.push_back(A[i]); 
 res.push_back(subset); 

 // move onto the next element. 
 subsetsUtil(A, res, subset, i + 1); 

 subset.pop_back(); 
 

return; 
 


vector<vector<int> > subsets(vector<int>& A) 
 
 vector<int> subset; 
 vector<vector<int> > res; 

 // include the null element in the set. 
 //res.push_back(subset); 

 // keeps track of current element in vector A; 
 int index = 0; 
 subsetsUtil(A, res, subset, index); 

 return res; 
 


int main() 
 

//ios_base::sync_with_stdio(false);
//cin.tie(NULL);



int t;
scan(t);
//cin>>t;
inputLoop 
int n;
scan(n);
//cin>>n;

// find the subsets of below vector. 
vector<int> arr; 

int input;
fori0n 
 //cin>>input;
 scan(input);
 arr.push_back(input);


vector<vector<int> > res = subsets(arr); 
int goodMedian = 0;
// Print result 
for (int i = 0; i < res.size(); i++) 



 //cout<<"Sub set : "<<i<<" _ With Size : "<<res[i].size()<<" == ";


 // if size == 1 or 3 
 if(res[i].size() % 2 != 0) 
 // there will always be a good median 
 //cout<<"GOOD MEDIAN ";
 goodMedian++;
 
 else if(res[i].size() == 2) median(res[i], 2) == res[i][1]) 
 //cout<<"GOOD MEDIAN ";
 goodMedian++;
 
 
 else if(res[i].size() % 2 == 0) median(res[i], res[i].size()) == res[i][(size - 1)/2]) 
 //cout<<"GOOD MEDIAN ";
 goodMedian++;
 
 



 //for (int j = 0; j < res[i].size(); j++) 
 // cout << res[i][j] << " "; 
 //cout << endl;


 print(goodMedian % MOD);
 
 return 0;

Can anyone suggest any better algorithm for this problem ?

edited 3 hours ago

200_success

126k14148409

asked 3 hours ago

Aditya Navphule

171

New contributor

add a commentÂ |Â

up vote
3
down vote

favorite

We need to calculate the number of sub-sequences of an array having its median lying in the sub-sequence itself. My code is -

#include <bits/stdc++.h> 
using namespace std; 


#define MOD 1000000007
#define fori0n for(int i=0;i<n;i++)
#define inputLoop for(int j=0;j<t;j++)

// FAST SCANNING .. 
template<typename T> void scan(T &x) 




// FAST PRINTING.. 
template<typename T> void print(T n) 
 
 bool neg = 0; 

 if (n < 0) 
 n *= -1, neg = 1; 

 char snum[65]; 
 int i = 0; 
 do
 
 snum[i++] = n % 10 + '0'; 
 n /= 10; 
 

 while (n); 
 --i; 

 if (neg) 
 putchar('-'); 

 while (i >= 0) 
 putchar(snum[i--]); 

 putchar('n'); 
 







float median(vector<int> new_array, int num)
 sort(new_array.begin(), new_array.end());
 float median = (num % 2 != 0) ? (new_array[((num+1)/2)-1]) : (float)(new_array[(num/2)-1] + new_array[num/2]) / 2;
 return median;


void subsetsUtil(vector<int>& A, vector<vector<int> >& res, 
 vector<int>& subset, int index) 
 
for (int i = index; i < A.size(); i++) 

 // include the A[i] in subset. 
 subset.push_back(A[i]); 
 res.push_back(subset); 

 // move onto the next element. 
 subsetsUtil(A, res, subset, i + 1); 

 subset.pop_back(); 
 

return; 
 


vector<vector<int> > subsets(vector<int>& A) 
 
 vector<int> subset; 
 vector<vector<int> > res; 

 // include the null element in the set. 
 //res.push_back(subset); 

 // keeps track of current element in vector A; 
 int index = 0; 
 subsetsUtil(A, res, subset, index); 

 return res; 
 


int main() 
 

//ios_base::sync_with_stdio(false);
//cin.tie(NULL);



int t;
scan(t);
//cin>>t;
inputLoop 
int n;
scan(n);
//cin>>n;

// find the subsets of below vector. 
vector<int> arr; 

int input;
fori0n 
 //cin>>input;
 scan(input);
 arr.push_back(input);


vector<vector<int> > res = subsets(arr); 
int goodMedian = 0;
// Print result 
for (int i = 0; i < res.size(); i++) 



 //cout<<"Sub set : "<<i<<" _ With Size : "<<res[i].size()<<" == ";


 // if size == 1 or 3 
 if(res[i].size() % 2 != 0) 
 // there will always be a good median 
 //cout<<"GOOD MEDIAN ";
 goodMedian++;
 
 else if(res[i].size() == 2) median(res[i], 2) == res[i][1]) 
 //cout<<"GOOD MEDIAN ";
 goodMedian++;
 
 
 else if(res[i].size() % 2 == 0) median(res[i], res[i].size()) == res[i][(size - 1)/2]) 
 //cout<<"GOOD MEDIAN ";
 goodMedian++;
 
 



 //for (int j = 0; j < res[i].size(); j++) 
 // cout << res[i][j] << " "; 
 //cout << endl;


 print(goodMedian % MOD);
 
 return 0;

Can anyone suggest any better algorithm for this problem ?

edited 3 hours ago

200_success

126k14148409

asked 3 hours ago

Aditya Navphule

171

New contributor

We need to calculate the number of sub-sequences of an array having its median lying in the sub-sequence itself. My code is -

#include <bits/stdc++.h> 
using namespace std; 


#define MOD 1000000007
#define fori0n for(int i=0;i<n;i++)
#define inputLoop for(int j=0;j<t;j++)

// FAST SCANNING .. 
template<typename T> void scan(T &x) 




// FAST PRINTING.. 
template<typename T> void print(T n) 
 
 bool neg = 0; 

 if (n < 0) 
 n *= -1, neg = 1; 

 char snum[65]; 
 int i = 0; 
 do
 
 snum[i++] = n % 10 + '0'; 
 n /= 10; 
 

 while (n); 
 --i; 

 if (neg) 
 putchar('-'); 

 while (i >= 0) 
 putchar(snum[i--]); 

 putchar('n'); 
 







float median(vector<int> new_array, int num)
 sort(new_array.begin(), new_array.end());
 float median = (num % 2 != 0) ? (new_array[((num+1)/2)-1]) : (float)(new_array[(num/2)-1] + new_array[num/2]) / 2;
 return median;


void subsetsUtil(vector<int>& A, vector<vector<int> >& res, 
 vector<int>& subset, int index) 
 
for (int i = index; i < A.size(); i++) 

 // include the A[i] in subset. 
 subset.push_back(A[i]); 
 res.push_back(subset); 

 // move onto the next element. 
 subsetsUtil(A, res, subset, i + 1); 

 subset.pop_back(); 
 

return; 
 


vector<vector<int> > subsets(vector<int>& A) 
 
 vector<int> subset; 
 vector<vector<int> > res; 

 // include the null element in the set. 
 //res.push_back(subset); 

 // keeps track of current element in vector A; 
 int index = 0; 
 subsetsUtil(A, res, subset, index); 

 return res; 
 


int main() 
 

//ios_base::sync_with_stdio(false);
//cin.tie(NULL);



int t;
scan(t);
//cin>>t;
inputLoop 
int n;
scan(n);
//cin>>n;

// find the subsets of below vector. 
vector<int> arr; 

int input;
fori0n 
 //cin>>input;
 scan(input);
 arr.push_back(input);


vector<vector<int> > res = subsets(arr); 
int goodMedian = 0;
// Print result 
for (int i = 0; i < res.size(); i++) 



 //cout<<"Sub set : "<<i<<" _ With Size : "<<res[i].size()<<" == ";


 // if size == 1 or 3 
 if(res[i].size() % 2 != 0) 
 // there will always be a good median 
 //cout<<"GOOD MEDIAN ";
 goodMedian++;
 
 else if(res[i].size() == 2) median(res[i], 2) == res[i][1]) 
 //cout<<"GOOD MEDIAN ";
 goodMedian++;
 
 
 else if(res[i].size() % 2 == 0) median(res[i], res[i].size()) == res[i][(size - 1)/2]) 
 //cout<<"GOOD MEDIAN ";
 goodMedian++;
 
 



 //for (int j = 0; j < res[i].size(); j++) 
 // cout << res[i][j] << " "; 
 //cout << endl;


 print(goodMedian % MOD);
 
 return 0;

Can anyone suggest any better algorithm for this problem ?

c++ algorithm array statistics

edited 3 hours ago

200_success

126k14148409

asked 3 hours ago

Aditya Navphule

171

New contributor

edited 3 hours ago

200_success

126k14148409

asked 3 hours ago

Aditya Navphule

171

New contributor

edited 3 hours ago

200_success

126k14148409

edited 3 hours ago

200_success

126k14148409

edited 3 hours ago

200_success

126k14148409

asked 3 hours ago

Aditya Navphule

171

New contributor

asked 3 hours ago

Aditya Navphule

171

asked 3 hours ago

Aditya Navphule

171

New contributor

Aditya Navphule is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

add a commentÂ |Â

2 Answers
2

active

oldest

votes

up vote
1
down vote

Some fairly standard observations:

<bits/stdc++.h> is non-standard and a bad choice for user code.

using namespace std; is harmful and should be avoided

Avoid preprocessor macros for constants or simple functions such as std::foreach()

Don't use numeric character codes - that will make your code mysteriously fail on non-ASCII systems.

Use std::printf() or std::cout instead of writing your own "fast" print function. Don't optimize before you profile, or you'll end up wasting time on code that's a minuscule part of the run time.

Use standard input functions, for the same reason.

Don't copy all the subsets of input into that vector of vectors; that's a big waste of space and time.

Don't recalculate the median for every sub-sequence; change to a more efficient algorithm (e.g. for every element (potential median), expand outwards and count how many occasions occur when the number of larger/equal elements matches the number of smaller/equal elements - you should be able to perform such a test using only integer arithmetic).

Indent the main() code properly, and split it into functions that each have a clear responsibility.

Explain (in a comment) why the final result is printed modulo MOD (and why we ignore overflows when counting, rather than also incrementing modulo MOD).

edited 2 hours ago

answered 3 hours ago

Toby Speight

21.4k436104

If the Size of array is about 1000 so to not overflow the final answer.
â€“Â Aditya Navphule
3 hours ago

I have read somewhere that the use of macros makes the execution faster.
â€“Â Aditya Navphule
2 hours ago

But binding of macros is done at compilation time?
â€“Â Aditya Navphule
2 hours ago

Macros get expanded by the preprocessor, not bound. Function calls are resolved/inlined at compile-time too, so I don't know what your concern is. Of course, any difference is completely swamped by the memory allocation and tedious recalculation - there's no point micro-optimising such trivial details when the algorithm is so inefficient.
â€“Â Toby Speight
2 hours ago

Okay, now I understand, thanks, can you please tell me how I can make the algorithm efficient?
â€“Â Aditya Navphule
2 hours ago

Â |Â
show 1 more comment

up vote
1
down vote

Don't #include <bits/stdc++.h> but explicitly include proper requested headers.

Try to limite uses of using namespace std;, it lead to painfull errors and weird bug.

Don't use preprocessor constants. Instead, use const and constexpr values.

Don't use macro, write directly code or use (inline) (constexpr) function if you use the same code at much places.

Try to return value instead of taking an input reference.

Avoid old array in favour of std::array.

Don't use register keyword in c++

Don't assign 1 or 0 to a bool, use true and false instead.

getchar return int, why trying to convert to T.

Try to use C++ iostream instead of getchar or putchar

Instead of magical values, use const char (eg 'A') to express chars bound..

Use curly braces for your statement

Don't try to be smart putting many statement on the same line, separated by comma. It's not.

The expression n *= -1 can by simplified in n = -n

Don't use for loops if you don't want Initialization+Condition+Operation. It's ugly.

Take care about indents.

edited 1 hour ago

answered 2 hours ago

Calak

1,06911

add a commentÂ |Â

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: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

Aditya Navphule is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207153%2fcount-sub-sequences-of-an-array-having-median-lying-in-that-subsequence-itself%23new-answer', 'question_page');

);

Post as a guest

Name

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

up vote
1
down vote

Some fairly standard observations:

<bits/stdc++.h> is non-standard and a bad choice for user code.

using namespace std; is harmful and should be avoided

Avoid preprocessor macros for constants or simple functions such as std::foreach()

Don't use numeric character codes - that will make your code mysteriously fail on non-ASCII systems.

Use std::printf() or std::cout instead of writing your own "fast" print function. Don't optimize before you profile, or you'll end up wasting time on code that's a minuscule part of the run time.

Use standard input functions, for the same reason.

Don't copy all the subsets of input into that vector of vectors; that's a big waste of space and time.

Don't recalculate the median for every sub-sequence; change to a more efficient algorithm (e.g. for every element (potential median), expand outwards and count how many occasions occur when the number of larger/equal elements matches the number of smaller/equal elements - you should be able to perform such a test using only integer arithmetic).

Indent the main() code properly, and split it into functions that each have a clear responsibility.

Explain (in a comment) why the final result is printed modulo MOD (and why we ignore overflows when counting, rather than also incrementing modulo MOD).

edited 2 hours ago

answered 3 hours ago

Toby Speight

21.4k436104

If the Size of array is about 1000 so to not overflow the final answer.
â€“Â Aditya Navphule
3 hours ago

I have read somewhere that the use of macros makes the execution faster.
â€“Â Aditya Navphule
2 hours ago

But binding of macros is done at compilation time?
â€“Â Aditya Navphule
2 hours ago

Macros get expanded by the preprocessor, not bound. Function calls are resolved/inlined at compile-time too, so I don't know what your concern is. Of course, any difference is completely swamped by the memory allocation and tedious recalculation - there's no point micro-optimising such trivial details when the algorithm is so inefficient.
â€“Â Toby Speight
2 hours ago

Okay, now I understand, thanks, can you please tell me how I can make the algorithm efficient?
â€“Â Aditya Navphule
2 hours ago

Â |Â
show 1 more comment

up vote
1
down vote

Some fairly standard observations:

<bits/stdc++.h> is non-standard and a bad choice for user code.

using namespace std; is harmful and should be avoided

Avoid preprocessor macros for constants or simple functions such as std::foreach()

Don't use numeric character codes - that will make your code mysteriously fail on non-ASCII systems.

Use std::printf() or std::cout instead of writing your own "fast" print function. Don't optimize before you profile, or you'll end up wasting time on code that's a minuscule part of the run time.

Use standard input functions, for the same reason.

Don't copy all the subsets of input into that vector of vectors; that's a big waste of space and time.

Don't recalculate the median for every sub-sequence; change to a more efficient algorithm (e.g. for every element (potential median), expand outwards and count how many occasions occur when the number of larger/equal elements matches the number of smaller/equal elements - you should be able to perform such a test using only integer arithmetic).

Indent the main() code properly, and split it into functions that each have a clear responsibility.

Explain (in a comment) why the final result is printed modulo MOD (and why we ignore overflows when counting, rather than also incrementing modulo MOD).

edited 2 hours ago

answered 3 hours ago

Toby Speight

21.4k436104

If the Size of array is about 1000 so to not overflow the final answer.
â€“Â Aditya Navphule
3 hours ago

I have read somewhere that the use of macros makes the execution faster.
â€“Â Aditya Navphule
2 hours ago

But binding of macros is done at compilation time?
â€“Â Aditya Navphule
2 hours ago

Macros get expanded by the preprocessor, not bound. Function calls are resolved/inlined at compile-time too, so I don't know what your concern is. Of course, any difference is completely swamped by the memory allocation and tedious recalculation - there's no point micro-optimising such trivial details when the algorithm is so inefficient.
â€“Â Toby Speight
2 hours ago

Okay, now I understand, thanks, can you please tell me how I can make the algorithm efficient?
â€“Â Aditya Navphule
2 hours ago

Â |Â
show 1 more comment

up vote
1
down vote

Some fairly standard observations:

<bits/stdc++.h> is non-standard and a bad choice for user code.

using namespace std; is harmful and should be avoided

Avoid preprocessor macros for constants or simple functions such as std::foreach()

Don't use numeric character codes - that will make your code mysteriously fail on non-ASCII systems.

Use std::printf() or std::cout instead of writing your own "fast" print function. Don't optimize before you profile, or you'll end up wasting time on code that's a minuscule part of the run time.

Use standard input functions, for the same reason.

Don't copy all the subsets of input into that vector of vectors; that's a big waste of space and time.

Don't recalculate the median for every sub-sequence; change to a more efficient algorithm (e.g. for every element (potential median), expand outwards and count how many occasions occur when the number of larger/equal elements matches the number of smaller/equal elements - you should be able to perform such a test using only integer arithmetic).

Indent the main() code properly, and split it into functions that each have a clear responsibility.

Explain (in a comment) why the final result is printed modulo MOD (and why we ignore overflows when counting, rather than also incrementing modulo MOD).

edited 2 hours ago

answered 3 hours ago

Toby Speight

21.4k436104

Some fairly standard observations:

<bits/stdc++.h> is non-standard and a bad choice for user code.

using namespace std; is harmful and should be avoided

Avoid preprocessor macros for constants or simple functions such as std::foreach()

Don't use numeric character codes - that will make your code mysteriously fail on non-ASCII systems.

Use std::printf() or std::cout instead of writing your own "fast" print function. Don't optimize before you profile, or you'll end up wasting time on code that's a minuscule part of the run time.

Use standard input functions, for the same reason.

Don't copy all the subsets of input into that vector of vectors; that's a big waste of space and time.

Don't recalculate the median for every sub-sequence; change to a more efficient algorithm (e.g. for every element (potential median), expand outwards and count how many occasions occur when the number of larger/equal elements matches the number of smaller/equal elements - you should be able to perform such a test using only integer arithmetic).

Indent the main() code properly, and split it into functions that each have a clear responsibility.

Explain (in a comment) why the final result is printed modulo MOD (and why we ignore overflows when counting, rather than also incrementing modulo MOD).

edited 2 hours ago

answered 3 hours ago

Toby Speight

21.4k436104

edited 2 hours ago

answered 3 hours ago

Toby Speight

21.4k436104

answered 3 hours ago

Toby Speight

21.4k436104

answered 3 hours ago

Toby Speight

21.4k436104

If the Size of array is about 1000 so to not overflow the final answer.
â€“Â Aditya Navphule
3 hours ago

I have read somewhere that the use of macros makes the execution faster.
â€“Â Aditya Navphule
2 hours ago

But binding of macros is done at compilation time?
â€“Â Aditya Navphule
2 hours ago

Macros get expanded by the preprocessor, not bound. Function calls are resolved/inlined at compile-time too, so I don't know what your concern is. Of course, any difference is completely swamped by the memory allocation and tedious recalculation - there's no point micro-optimising such trivial details when the algorithm is so inefficient.
â€“Â Toby Speight
2 hours ago

Okay, now I understand, thanks, can you please tell me how I can make the algorithm efficient?
â€“Â Aditya Navphule
2 hours ago

Â |Â
show 1 more comment

If the Size of array is about 1000 so to not overflow the final answer.
â€“Â Aditya Navphule
3 hours ago

I have read somewhere that the use of macros makes the execution faster.
â€“Â Aditya Navphule
2 hours ago

But binding of macros is done at compilation time?
â€“Â Aditya Navphule
2 hours ago

Macros get expanded by the preprocessor, not bound. Function calls are resolved/inlined at compile-time too, so I don't know what your concern is. Of course, any difference is completely swamped by the memory allocation and tedious recalculation - there's no point micro-optimising such trivial details when the algorithm is so inefficient.
â€“Â Toby Speight
2 hours ago

Okay, now I understand, thanks, can you please tell me how I can make the algorithm efficient?
â€“Â Aditya Navphule
2 hours ago

If the Size of array is about 1000 so to not overflow the final answer.
â€“Â Aditya Navphule
3 hours ago

I have read somewhere that the use of macros makes the execution faster.
â€“Â Aditya Navphule
2 hours ago

But binding of macros is done at compilation time?
â€“Â Aditya Navphule
2 hours ago

Macros get expanded by the preprocessor, not bound. Function calls are resolved/inlined at compile-time too, so I don't know what your concern is. Of course, any difference is completely swamped by the memory allocation and tedious recalculation - there's no point micro-optimising such trivial details when the algorithm is so inefficient.
â€“Â Toby Speight
2 hours ago

Okay, now I understand, thanks, can you please tell me how I can make the algorithm efficient?
â€“Â Aditya Navphule
2 hours ago

Â |Â
show 1 more comment

up vote
1
down vote

Don't #include <bits/stdc++.h> but explicitly include proper requested headers.

Try to limite uses of using namespace std;, it lead to painfull errors and weird bug.

Don't use preprocessor constants. Instead, use const and constexpr values.

Don't use macro, write directly code or use (inline) (constexpr) function if you use the same code at much places.

Try to return value instead of taking an input reference.

Avoid old array in favour of std::array.

Don't use register keyword in c++

Don't assign 1 or 0 to a bool, use true and false instead.

getchar return int, why trying to convert to T.

Try to use C++ iostream instead of getchar or putchar

Instead of magical values, use const char (eg 'A') to express chars bound..

Use curly braces for your statement

Don't try to be smart putting many statement on the same line, separated by comma. It's not.

The expression n *= -1 can by simplified in n = -n

Don't use for loops if you don't want Initialization+Condition+Operation. It's ugly.

Take care about indents.

edited 1 hour ago

answered 2 hours ago

Calak

1,06911

add a commentÂ |Â

up vote
1
down vote

Don't #include <bits/stdc++.h> but explicitly include proper requested headers.

Try to limite uses of using namespace std;, it lead to painfull errors and weird bug.

Don't use preprocessor constants. Instead, use const and constexpr values.

Don't use macro, write directly code or use (inline) (constexpr) function if you use the same code at much places.

Try to return value instead of taking an input reference.

Avoid old array in favour of std::array.

Don't use register keyword in c++

Don't assign 1 or 0 to a bool, use true and false instead.

getchar return int, why trying to convert to T.

Try to use C++ iostream instead of getchar or putchar

Instead of magical values, use const char (eg 'A') to express chars bound..

Use curly braces for your statement

Don't try to be smart putting many statement on the same line, separated by comma. It's not.

The expression n *= -1 can by simplified in n = -n

Don't use for loops if you don't want Initialization+Condition+Operation. It's ugly.

Take care about indents.

edited 1 hour ago

answered 2 hours ago

Calak

1,06911

add a commentÂ |Â

up vote
1
down vote

Don't #include <bits/stdc++.h> but explicitly include proper requested headers.

Try to limite uses of using namespace std;, it lead to painfull errors and weird bug.

Don't use preprocessor constants. Instead, use const and constexpr values.

Don't use macro, write directly code or use (inline) (constexpr) function if you use the same code at much places.

Try to return value instead of taking an input reference.

Avoid old array in favour of std::array.

Don't use register keyword in c++

Don't assign 1 or 0 to a bool, use true and false instead.

getchar return int, why trying to convert to T.

Try to use C++ iostream instead of getchar or putchar

Instead of magical values, use const char (eg 'A') to express chars bound..

Use curly braces for your statement

Don't try to be smart putting many statement on the same line, separated by comma. It's not.

The expression n *= -1 can by simplified in n = -n

Don't use for loops if you don't want Initialization+Condition+Operation. It's ugly.

Take care about indents.

edited 1 hour ago

answered 2 hours ago

Calak

1,06911

Don't #include <bits/stdc++.h> but explicitly include proper requested headers.

Try to limite uses of using namespace std;, it lead to painfull errors and weird bug.

Don't use preprocessor constants. Instead, use const and constexpr values.

Don't use macro, write directly code or use (inline) (constexpr) function if you use the same code at much places.

Try to return value instead of taking an input reference.

Avoid old array in favour of std::array.

Don't use register keyword in c++

Don't assign 1 or 0 to a bool, use true and false instead.

getchar return int, why trying to convert to T.

Try to use C++ iostream instead of getchar or putchar

Instead of magical values, use const char (eg 'A') to express chars bound..

Use curly braces for your statement

Don't try to be smart putting many statement on the same line, separated by comma. It's not.

The expression n *= -1 can by simplified in n = -n

Don't use for loops if you don't want Initialization+Condition+Operation. It's ugly.

Take care about indents.

edited 1 hour ago

answered 2 hours ago

Calak

1,06911

edited 1 hour ago

answered 2 hours ago

Calak

1,06911

answered 2 hours ago

Calak

1,06911

answered 2 hours ago

Calak

1,06911

add a commentÂ |Â

Aditya Navphule is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Aditya Navphule is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Post as a guest

Name

Search This Blog

Iyfjky