Top 10 optimizations 2023- (collectors edition)

Revision en1, by TheBhediyaOfDalalStreet, 2023-03-23 11:56:12

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

HONORABLE MENTION:

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

Literature: https://arxiv.org/pdf/0909.4437.pdf http://www.amazon.com/Optimizing-energy-consumption-wireless-networks/dp/3659121207 http://www.superknjizara.hr/index.php?page=autor&idautor=13819 http://www.jucs.org/jucs_23_3/generating_politician_profiles_based http://authors.elsevier.com/a/1SQGc5aecSN1Bg https://arxiv.org/pdf/1705.07279.pdf

Tags #for_beginners, bitset fanclub, binary search fanclub, mainucodingbadipasandae

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English TheBhediyaOfDalalStreet 2023-03-25 21:52:51 0 (published)
en5 English TheBhediyaOfDalalStreet 2023-03-25 21:52:14 0 (saved to drafts)
en4 English TheBhediyaOfDalalStreet 2023-03-25 20:21:37 40 Tiny change: '.07279.pdf' -> '.07279.pdf https://codeforces.me/blog/entry/53168' (published)
en3 English TheBhediyaOfDalalStreet 2023-03-24 17:05:14 13 Tiny change: 'ON NESTED DIMENSIONS TO RUN I' -> 'ON NESTED INTERVALS TO RUN I'
en2 English TheBhediyaOfDalalStreet 2023-03-24 17:04:24 2 Tiny change: 'ty by fact of log V ' -> 'ty by factor of log V '
en1 English TheBhediyaOfDalalStreet 2023-03-23 11:56:12 1957 Initial revision (saved to drafts)