TSORT: Getting wrong answer. But my code passes every test case I try.

general
,
1

Hi , I was trying to solve the problem TSORT Problem - CodeChef.
can you please take a look at my solution here and point whats wrong.
CodeChef: Practical coding for everyone

I am getting wrong answer.

2

Your solution gives the wrong answer under some (random) circumstances, but due to your use of rand() (whose precise behaviour may change across installs, or even versions of gcc), it’s entirely possible that you will see the “correct” answer on every test case you’ve tried.

Worse, since rand() is deterministic given the same starting seed, running the same testcase over and over again doesn’t help expose the flaw - you’ll get the same result each time you run it!

I’ve modified your program to initialise the random number generator with the current time, in order to break the determinism:

#include <iostream>
#include <string>
#include <sys/time.h>

#define ll long long int
#define getLine(s) while(s.length()==0){ getline(cin,s); }
#define getArray(n, arr) for(int i=0;i<n;i++){ std::cin>>arr[i]; }
using namespace std;

class Pair{
    public:
    int m1,m2;
    Pair(int m1,int m2){
        this->m1=m1;
        this->m2=m2;
    }
};

Pair getPartition3(int arr[],int low,int high){
    int partition1 = low;
    int partition2 = low;
    for(int i=low;i<=high;i++){
        if(arr[i]<arr[high]){
            swap(arr[partition2], arr[partition1]);
            swap(arr[partition1], arr[i]);
            partition2++;
            partition1++;
        } else if(arr[i]==arr[high]){
            swap(arr[partition2], arr[i]);
            partition2++;
        }
    }
    
    Pair pair(partition1,partition2);
    return pair;
}

void quick_sort(int arr[], int low,int high){
    if(low<high){
        int k = low+rand()%(high-low+1);
        swap(arr[k],arr[high]);
        Pair pair=getPartition3(arr,low,high);
        quick_sort(arr,low,pair.m1-1);
        quick_sort(arr,pair.m2,high);
    }
}
void solve(){
    int n;
    cin>>n;
    int arr[n];
    getArray(n, arr);
    quick_sort(arr,0,n-1);
    
    for(int i=0;i<n;i++){
        cout<<arr[i]<<endl;
    }
}

int main() {
    struct timeval time;
    gettimeofday(&time,NULL);
    srand(static_cast<unsigned int>((time.tv_sec * 1000) + (time.tv_usec / 1000)));

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }

    return 0;
}

With this, it only takes a few runs with a simple testcase to get your solution to give the wrong result:

[simon@simon-laptop][12:13:10]
[~/devel/hackerrank/otherpeoples]>echo "3
1
0
1" | ./a.out
0
1
1
[simon@simon-laptop][12:13:11]
[~/devel/hackerrank/otherpeoples]>echo "3
1
0
1" | ./a.out
1
0
1

Edit:

Alternatively, just take your original solution and give it a large-ish input like this:

100
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

Your original solution fails on this with my install, and the odds are high it will fail on yours, too :slight_smile:

It consists of 99 1s and a randomly-placed 0, which is hard to sort correctly “by chance”.

1 Like