maybesomeone's blog

By maybesomeone, history, 3 weeks ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

By maybesomeone, history, 3 weeks ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By maybesomeone, 3 weeks ago, In English

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

int N;
cin >> N;

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

cout << answer;

Read more »

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

By maybesomeone, history, 5 weeks ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By maybesomeone, history, 5 weeks ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By maybesomeone, history, 6 weeks ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

By maybesomeone, history, 3 months ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it