175iq's blog

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

There are some problems, particularly from old contests, whose editorial is hard to understand(as it is not explanatory enough) and leaves me clueless regarding step(s) in the editorial.

Posting a blog for every problem whose editorial I couldn't understand doesn't seem like a good way to ask for help.

Where should I ask for help in such cases? Is there any discord server/telegram channel/any other thing where other people are active and I can ask for help for problems rated 1700-1900 ?

Read more »

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

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

I am using sublime text 3 with pre compiled headers as mentioned in this blog.

The build that I am using is as follows :

{
"cmd" : ["g++ -std=c++17 $file_name -o $file_base_name && timeout 4s ./$file_base_name <input.txt >stdout.txt 2>stderr.txt"], 
"selector" : "source.c",
"shell": true,
"working_dir" : "$file_path"
}

If I use <bits/stdc++.h>, it takes 1.2s to compile and run every time I run any code( eg. Hello World code) using Ctrl+B.

When I use "bits/stdc++.h" (and expect the compilation time to become less) it actually takes 5-6 s to compile and run even the "Hello World" program for the first time using Ctrl+B. From next time, it takes 0.3 s only but the first time, it takes as long as 5-6s.

For every new program that I write, it happens like this. For eg. If I change the "Hello World" program to print 10 numbers from 1-10, it will again take 5-6s to compile and run. Then from the second time, it will take 0.3-0.4 s.

The directory structure is as follows :

CP/

  • bits/
    • stdc++.h
    • stdc++.h.gch
  • code.cpp (this is the file in which I write the code)

I have tried finding some information online but couldn't find anything useful. Can someone please help me out?

Read more »

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

By 175iq, history, 10 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, 11 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, 2 years 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