### Jim_Moriarty_'s blog

By Jim_Moriarty_, history, 2 months ago, ,

I wanted to ask which one is better to use because avg. case complexity of set is log(n) while that of unordered_set is o(1) while worst case of set is same but that of unordered set is o(n).

And what are the points that we should take care of while using unordered_set so that we can work with no changes in inbuilt unordered_set?

Any help would be appreciated.

• +2

By Jim_Moriarty_, history, 3 months ago, ,

Can two strongly connected components overlap ?

I read somewhere that they can't.

But at the same time I encountered a problem https://www.hackerearth.com/practice/algorithms/graphs/strongly-connected-components/tutorial/

problem is at the bottom of the page Consider the example testcase given - 5 6

1 4

1 3

2 4

3 4

4 5

5 1

I found manually that there are two SCCs -(1, 3, 4, 5) and (2) So the answer should be zero. But it's given as -3. So am I not understanding something about SCC or the answer given is wrong? Please help.

• +4

By Jim_Moriarty_, history, 3 months ago, ,
• This is the code that I have studied for finding SCC and I have several doubts.
Spoiler

//code is from steven and felix book.

Can one node be contained in two SCCs?

5 6

1 4

1 3

2 4

3 4

4 5

5 1

consider this testcase ; 5 is number of nodes and 6 is the number of directed edges. 1 4 means there is an directed edge from 1 to 4.

if I assume that one node is contained in only one SCC then 1->4->5 will be considered or 1->3->4->5 for 1, 4 and 5.

And how we update dfs_low[u] in case of visited node as dfs_low[u]=min(dfs_low[u], dfs_low[v.first]) or as dfs_low[u]=min(dfs_low[u], dfs_num[v.first]). Which one is correct and why ?

Any help would be appreciated.

• -11

By Jim_Moriarty_, history, 3 months ago, ,

Firstly we have string list then we have empty line then we have another string list. I want both list of strings to be stored in separate string vectors. How do I take the input.

Eg.

perfect rhyme crime time

crime rhyme

How do I take input here?

• -3

By Jim_Moriarty_, history, 3 months ago, ,

Can anyone explain the relation between modular inverse of p^k and p^(k-1) given M. Any help would be appreciated.

• -6

By Jim_Moriarty_, history, 3 months ago, ,

• -4

By Jim_Moriarty_, history, 3 months ago, ,

I was recently solving a problem using a vector first but I got MLE (memory limit exceeded). Then I declared an array of maximum size it got accepted in only 64 KiB. So if any of you know about how does memory limit get affected when we declare anything (large size) globally. And how does it affect the memory limit.

Code which got MLE — https://www.hackerearth.com/submission/41144649/ Code which got AC — https://www.hackerearth.com/submission/41145515/

• +7

By Jim_Moriarty_, history, 3 months ago, ,

please suggest me some articles that explain implementation of trie using 2D arrays. Not using pointers. I Have found one article but I am unable to understand it from there. Please do help. Thanks in advance.

• +9

By Jim_Moriarty_, history, 3 months ago, ,

Two sequences A and B each of which consist of distinct elements . Find the lcs of two sequences. I have read an explanation on stack overflow but I was not able to understand. Please help with this...

• +12

By Jim_Moriarty_, history, 4 months ago, ,

Problem link- https://www.spoj.com/problems/CISTFILL/ I am getting WA but I am unable to find my error.

• 0

By Jim_Moriarty_, history, 4 months ago, ,

This original problem is titled ‘My Ancestor’ and was used in the Thailand ICPC National Contest 2009. Abridged problem description: Given a weighted (family) tree of up to N ≤ 80K vertices with a special trait: Vertex values are increasing from root to leaves. Find the ancestor vertex closest to the root from a starting vertex v that has weight at least P. There are up to Q ≤ 20K such offline queries.

I am also unable to find the actual link of the problem and hence the solution. Actually this problem is given in steven and felix book.

• +1

By Jim_Moriarty_, history, 4 months ago, ,

Is there a data structure which performs O(1) or O(logn) insertion at back and same for removal and we can find the number of elements less than K (any particular element ) in O(logn) if the data structure is already sorted (means binary search is applicable )

• +12

By Jim_Moriarty_, history, 4 months ago, ,

I am not getting the logic to solve this. Please explain . Problem link- https://www.spoj.com/problems/ORDERS/

• +4

By Jim_Moriarty_, history, 4 months ago, ,

Can anyone explain !! How the complexity of building the merge sort is O(nlog(n)) . As if we build segment tree for maximum query it will take O(n) time because we had to cover approx 2*n to 4*n nodes and at each node merging two children nodes took O(1) time. But here in merge sort merging two children nodes takes O(n) time . So how come the complexity is O(nlog(n))?

• +3

By Jim_Moriarty_, history, 4 months ago, ,

• -2

By Jim_Moriarty_, history, 4 months ago, ,

I think my solution is going wrong for test case 9. https://ideone.com/GzT8G7 I have been trying since past 2 days. Please help me debug it.