MainuCodingBadiPasandAe's blog

By MainuCodingBadiPasandAe, history, 2 months ago, In English

Hello friends. The year 2023 is midway and so I have prepared the top log2(10) optimizations of 2023 for your viewing pleasure. Without forthor ado, let us begin.

OPTIMIZATION OF DIJKSTRA ALGORITHM TO RUN IN Θ(E + V) FOR HAMILTONIAN GRAPHS: In the relaxation condition of djikstra algorithm, we will binary search for the nearest node with distance greater than current distance in the hamiltonian graph and so we will reduce time complexity by factor of log V (becoz of binary search) so TC becomes : O((E / logV) * log V + V) = Θ(E + V)

KOSARAJU OPTIMIZATION TO WORK FOR CYCLIC GRAPHS: we can use the property of binary search to quickly decompose cycles into directed edges then we will use our little mfriemd binary search on the dfs stack to find the topological order.

OPTIMIZATION OF SPARSE TABLE TO ANSWER RANGE MAXIMUM FREQUENCY QUERIES IN Ω(log N): we will simple use binary search for reducing time complexity from O(N) to Ω(log N)

OPTIMIZATION OF CONVOLUTION ON NESTED INTERVALS TO RUN IN O(log(r + l) * 3.77742307 ^ (r — l + 1)): now you may be thinking how is this possible. I say there is something called binary search. so we will use him.


OPTIMIZATION OF BITSET USING BINARY SEAARCH: needless to say we can optimize bitset using nested binary searches to reduce complexity by log N on every nested binary search, as nest limit tends to inifniity, this allows us to solve all problems in Ω(1) in the limit n -> infinity

thank you for your attention mriemds,

With respect. mainucodingbadipasandae


2 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

It is worth noting that the solution to the Hamiltonian problem is average, and under extreme bad luck it can reach the square. However, this can only rely on luck rather than constructing data. Using srand(constant) in CF can be attacked by hackers.

about "KOSARAJU OPTIMIZATION TO WORK FOR CYCLIC GRAPHS". In fact, we already have a linear shortest path here, but because of the complex data structure involved, it has no practical value in CP.