Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

175iq's blog

By 175iq, history, 2 months ago, In English,

Can someone please share their stress testing library?

I am looking for random tree, graph(connected/disconnected) generators and different type of array generators.

Read more »

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

By 175iq, history, 3 months ago, In English,

I recently found out that inserting a vector in a map is possible :

map< vector<int>, int > mp;
vector<int> vec = {1,2,3,4,5};
mp[vec] = 5;
cout<<mp[vec];
// prints 5
  1. If there are N vectors in mp present as keys already, what is the time complexity to insert a new vector of size M in mp ? Is it O(M*log(N) or something else depending upon the sizes of vectors present in mp already?
  2. What would be the time complexity of a query operation such as mp[vec]? Please help.

Read more »

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

By 175iq, history, 16 months ago, In English,

By what factor is Kosaraju's algorithm for finding strongly connected component slower as compared to Tarjan's algorithm. It appears to me that the factor should be 3 as there are 2 dfs passes in Kosaraju's algorithm and we also have to transpose the graph once. Am I missing something ?

Also is there any way to find the tranpose graph without declaring a new graph and storing the edges in reverse order ? (Basically reversal of graph without use of extra memory)

Read more »

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