Monk and Sorting Algorithm[HackerEarth]

help
1

Hello guys can you help me reduce the time complexity of my code for the problem Monk and Sorting Algorithm: Code Monk - Be a better programmer

I tried to optimize my code as much as possible and now I have no idea to further reduce the time complexity.

**#include<bits/stdc++.h>**

** #define ll long long int**

** using namespace std;**

** int counter;**

** bool anyNonZero = false;**

** ll powerOf10[19];**

** bool compare(const int& a, const int& b){**

** ll wa = a;**

** wa/=powerOf10[min(18, 5*(counter-1))];**

** wa%=powerOf10[min(18, 5counter - 5(counter-1))];**

** ll wb = b;**

** wb/=powerOf10[min(18, 5*(counter-1))];**

** wb%=powerOf10[min(18, 5counter - 5(counter-1))];**

** if(wa!=0 || wb!=0) anyNonZero=true;**

** return wa<wb;**

** }**

** void print(vector& num){**

** for(int i=0;i<num.size();i++){**

** cout << num[i] << " ";**

** }**

** cout << endl;**

** }**

** int main(){**

** int n;**

** cin >> n;**

** powerOf10[0]=1;**

** for(int i=1;i<=18;i++) powerOf10[i]=powerOf10[i-1]10;*

** vector num(n);**

** for(int i=0;i<n;i++) cin >> num[i];**

** counter = 1;**

** while(true){**

** anyNonZero = false;**

** stable_sort(num.begin(), num.end(), compare);**

** if(!anyNonZero) break;**

** print(num);**

** counter++;**

** }**

** return 0;**

** }**

I did nothing fancy, I kept finding the weight and then sorting the vector using the stable_sort function and then printing my result.

My time complexity as I think should be O(5*(time taken by stable sort)) which is when I googled to be O(5nlog^2n).

What can I do? Please help me.

2

I have solved it in java. But the key reason why I was getting TLE was becuase I wasn’t using fast Input Output. So, just search out the web for Fast Input and Output in C++, it surely will help you!

3

stable_sort of STL takes O(n*(logn)^2) space in case of memory insufficiency. Since here the numbers are large that might be the case. Hence we need to implement merge sort for the same.

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

using ll = long long int;

ll arr[1000001], tmp[1000001], org[1000001], tmp1[1000001];

void merge(int start, int mid, int end)
{
	int p = start; 
	int q = mid;
	int r = p;
	while (p < mid && q <= end) {
		if (arr[p] <= arr[q]) {
		    tmp1[r] = org[p];
			tmp[r++] = arr[p++];
		} else {
		    tmp1[r] = org[q];
			tmp[r++] = arr[q++];
		}
	}
	while (p < mid) {
	    tmp1[r] = org[p];
		tmp[r++] = arr[p++];
	}
	while (q <= end) {
	    tmp1[r] = org[q];
		tmp[r++] = arr[q++];
	}
	for (p = start; p <= end; ++p) {
		arr[p] = tmp[p];
		org[p] = tmp1[p];
	}
}

void merge_sort(int l, int r)
{
	if (l < r) {
		int mid = (l+r) >> 1;
		merge_sort(l, mid);
		merge_sort(mid+1, r);
		merge(l, mid+1, r);
	}
}

void solve(){

	ll n;
	scanf("%lld", &n);

	ll max_ele = 0, multiplier = 1;

	// we need to make chunks until there are no chunks left
	// a good way to know this is make chunks of max ele of arr
	for(int i = 0; i < n; i++){
		scanf("%lld", &org[i]);
		if(org[i] > max_ele) max_ele = org[i];
	}


	while(max_ele / multiplier){

		for (int i = 0; i < n; ++i) {
	        arr[i] = (org[i] / multiplier) % 100000;
	    }

		// Implementing merge sort O(nlogn)
		merge_sort(0, n-1);

		for(int i = 0; i < n; i++)
			printf("%lld ",org[i]);
		printf("\n");

		multiplier *= 100000;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solve();
	
	return 0;
}