5
\$\begingroup\$

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) || (c > 57)) 
     c = getchar(); 

     for ( ; c < 48||c > 57 ; c = getchar()); 

     for ( ; c > 47 && c < 58; c = getchar() ) 
             x= (x << 3) + ( x << 1 ) + ( c & 15 ); 

      if (neg) x *= -1; 
}



// 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) {
        if(median(res[i], 2) == res[i][0] || median(res[i], 2) == res[i][1]) {
            //cout<<"GOOD MEDIAN ";
            goodMedian++;
        }
    }
    else if(res[i].size() % 2 == 0) {
        int size = res[i].size();
        if(median(res[i], res[i].size()) == res[i][size / 2] || 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 ?

\$\endgroup\$
4
\$\begingroup\$
  • 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.
\$\endgroup\$
3
\$\begingroup\$

A function like this, with clearly defined inputs and outputs, is best written with the aid of unit tests to confirm its correct operation.

Start by extracting the actual computation out of main():

auto count_passing_subseqs(const std::vector<int>& v)
{
    std::vector<std::vector<int> > res = subsets(v); 
    // (rest of implementation...)

    return goodMedian % MOD;
}

Now we can write our first test. The empty sequence has no subsequences at all, so let's check that:

#include <gtest/gtest.h>

TEST(count, emptyInput)
{
    EXPECT_EQ(0, count_passing_subseqs({}));
}

That passes; good. We can add the next most simple cases, with just one or two elements in input:

TEST(count, oneInput)
{
    EXPECT_EQ(1, count_passing_subseqs({1}));
}

TEST(count, twoSmallSame)
{
    EXPECT_EQ(3, count_passing_subseqs({1, 1}));
}

TEST(count, twoSmallDifferent)
{
    EXPECT_EQ(2, count_passing_subseqs({1, 2}));
}

Let's try some larger values, still in a small array:

TEST(count, twoLargeSame)
{
    auto constexpr m = INT_MAX;
    EXPECT_EQ(3, count_passing_subseqs({m, m}));
}

TEST(count, twoLargeDifferent)
{
    auto constexpr m = INT_MAX / 3;
    EXPECT_EQ(2, count_passing_subseqs({m, m-1}));
}

That gives us some lovely juicy bugs to fix:

[ RUN      ] count.twoLargeSame
207153.cpp:177: Failure
      Expected: 3
To be equal to: count_passing_subseqs({m, m})
      Which is: 2
[  FAILED  ] count.twoLargeSame (0 ms)
[ RUN      ] count.twoLargeDifferent
207153.cpp:183: Failure
      Expected: 2
To be equal to: count_passing_subseqs({m, m-1})
      Which is: 3
[  FAILED  ] count.twoLargeDifferent (0 ms)

One of those is due to integer overflow in (float)(new_array[(num/2)-1] + new_array[num/2]) / 2; the other is due to the limited precision of float.


Once we have fixed those bugs, we can move on to longer sequences. If we have an n-element array with all members equal, every subarray must contain its median. If we have an n-element array with all members different, only the odd-length subarrays will contain their medians.

// modular exponentiation - base ** exponent % reduction
static constexpr auto expmod(std::size_t base, std::size_t exponent, std::size_t reduction)
{
    std::size_t i = base;
    std::size_t result = 1;
    while (exponent) {
        if (exponent % 2) {
            result *= i;
        }
        i *= base;              // ignore risk of overflow here
        i %= reduction;
        base *= base;           // and here
        base %= reduction;
        exponent /= 2;
    }
    return result;
}

TEST(count, ManySame)
{
    static constexpr std::size_t length = 1000;
    static auto const v = std::vector<int>(length, 4);
    auto constexpr expected = expmod(2, length, MOD) - 1;
    EXPECT_EQ(expected, count_passing_subseqs(v));
}

TEST(count, ManyDifferent)
{
    static constexpr std::size_t length = 1000;
    static auto const v = []{
        std::vector<int> v(length, {});
        std::iota(v.begin(), v.end(), 0);
        return v;
    }();
    auto constexpr expected = expmod(2, length-1, MOD);
    EXPECT_EQ(expected, count_passing_subseqs(v));
}

This exposes another weakness in the implementation:

[ RUN      ] count.ManySame
unknown file: Failure
C++ exception with description "std::bad_alloc" thrown in the test body.
[  FAILED  ] count.ManySame (405 ms)
[ RUN      ] count.ManyDifferent
unknown file: Failure
C++ exception with description "std::bad_alloc" thrown in the test body.
[  FAILED  ] count.ManyDifferent (408 ms)

This suggests that our memory use scales poorly - we need an algorithm that doesn't allocate so much extra storage.


I'll stop at this point, but I hope you can see how proper tests will help improve your code, and allow you to change algorithms with more confidence.

\$\endgroup\$
2
\$\begingroup\$

Beginning with some depressingly-common 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.
  • Be careful with goodMedian++ - the variable is an int, which has limited range, and Undefined Behaviour on overflow. Prefer an unsigned type, such as std::size_t for counting.
  • Avoid comparisons between signed and unsigned integers, such as in for (int i = index; i < A.size(); i++). Just use std::size_t i and the bug is magically fixed.
  • Don't depend on floating-point equality. In median(res[i], 2) == res[i][0], median returns a float (which likely has less precision than int), making that test unreliable with large values. (In the size==2 case, it's total overkill anyway, as you only need to test res[i][0] == res[i][1].)
  • 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).
\$\endgroup\$
  • \$\begingroup\$ If the Size of array is about 1000 so to not overflow the final answer. \$\endgroup\$ – user184108 Nov 7 '18 at 17:16
  • \$\begingroup\$ I have read somewhere that the use of macros makes the execution faster. \$\endgroup\$ – user184108 Nov 7 '18 at 17:18
  • \$\begingroup\$ But binding of macros is done at compilation time? \$\endgroup\$ – user184108 Nov 7 '18 at 17:26
  • \$\begingroup\$ 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. \$\endgroup\$ – Toby Speight Nov 7 '18 at 17:32
  • \$\begingroup\$ I'm not going to simply tell you, since this looks like a code-challenge and you should be prepared to do some thinking for yourself (otherwise the challenge is lost), but there's some hints in my review that should help. \$\endgroup\$ – Toby Speight Nov 7 '18 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy