Jim_Moriarty_'s blog

By Jim_Moriarty_, history, 2 months ago, In English,

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.

Read more »

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

By Jim_Moriarty_, history, 3 months ago, In English,

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.

Read more »

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

By Jim_Moriarty_, history, 3 months ago, In English,
      • 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.

Read more »

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

By Jim_Moriarty_, history, 3 months ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By Jim_Moriarty_, history, 3 months ago, In English,

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

Read more »

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

By Jim_Moriarty_, history, 3 months ago, In English,
 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

By Jim_Moriarty_, history, 3 months ago, In English,

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/

Read more »

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

By Jim_Moriarty_, history, 3 months ago, In English,

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.

Read more »

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

By Jim_Moriarty_, history, 3 months ago, In English,

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...

Read more »

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

By Jim_Moriarty_, history, 4 months ago, In English,

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

solution link- https://ideone.com/yVDJ1t Please help...

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Jim_Moriarty_, history, 4 months ago, In English,

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.

Read more »

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

By Jim_Moriarty_, history, 4 months ago, In English,

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 )

Read more »

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

By Jim_Moriarty_, history, 4 months ago, In English,

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

Read more »

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

By Jim_Moriarty_, history, 4 months ago, In English,

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

Read more »

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

By Jim_Moriarty_, history, 4 months ago, In English,

How to proceed after coordinate compression.. Please help.. https://www.spoj.com/problems/POSTERS/ — problem link

Read more »

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

By Jim_Moriarty_, history, 4 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it