### maybesomeone's blog

By maybesomeone, history, 3 weeks ago,

We know that Time Complexity of std::sort is O(N·log(N)). and
Time Complexity of std::stable_sort is O(N·log^2(N)).

The std::sort doesn't preserves the relative order of equal elements while std::stable_sort does. But it is little slower. Can't we just write custom comparator to preserve order like this

int N = 1e5;
std::vector<int> A(N, 1);

std::vector<int> order(N);
std::iota(order.begin(), order.end(), 0);

std::sort(order.begin(), order.end(), [&](int i, int j) {
if (A[i] == A[j]) {
return i < j;
}
return A[i] < A[j];
});


now the std::sort will also preserve relative order of equal elements than why to use std::stable_sort

• +7

By maybesomeone, history, 3 weeks ago,

let array A = {1,3,1,1,1,4,0,0,2,3,1,}

We have to do following 2 operations on it

1.)Decrease all elements from L to R by 1

2.)Given i find right most element j such that for each k. i <= k <= j. A[k] > 0

how can i do this in log(N) ?

• +5

By maybesomeone, 3 weeks ago,

is there any formula to calculate this in O(1) ?

int N;
cin >> N;

int answer = 0;
while (N > 1) {
N = sqrt(N);
}



• +12

By maybesomeone, history, 5 weeks ago,

Is data science and competitive programming related. can anyone explain how they are related what are some common things in both of them

• +6

By maybesomeone, history, 5 weeks ago,

what is fractional knapsack. is this a dp problem or greedy ?

• +6

By maybesomeone, history, 6 weeks ago,

is vector better than deque ?. can someone tell what are some things that makes vector better than deque

• +11

By maybesomeone, history, 3 months ago,

is there a way to skip the chapter 1 of usaco training page. chapter 1 is too easy and i dont want to waste my time on that