mjhjmtu

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) 
 
 x = 0; 
 bool neg = 0; 
 register T c = getchar(); 

 if (c == '-') 
 neg = 1, c = getchar(); 

 while ((c < 48) 



// 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) 
 else if(res[i].size() % 2 == 0) 
 int size = res[i].size();
 if(median(res[i], res[i].size()) == res[i][size / 2] 



 //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 ?

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).

• 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.