Top 10 optimizations 2017- (collectors edition)

Revision en1, by bukefala, 2017-07-07 23:47:35

Hello friends. The year is almost over so I have prepared the top 10 optimizations of 2017 for your viewing pleasure. Without forthor ado, let us begin.

  1. OPTIMIZATION OF FLOYD VARŠAL ALGORITHM TO RUN IN N^2: simply instead of going from 1 to N in third loop we willuse bitset which will visit the remaining nodes automatically

  2. SEGMENT TREE OPTIMIZATION TO RUN IN O(NlogMlogQ) complexity. We will simply use bitset to fetch our data between nodes instead of every time having to calculate hashes in nodes all over again.

  3. OPTIMIZATION OF FENWICK TO ACCEPT QUERIES OF TYPE: EXPAND INTERVAL BY CONSTANT C We will simply use bitset which will store every expansion in every possible moment in time. You will say this is obviously too slow. But it can be easily optimized. We will simply make another bitset map for these changes.

  4. USING LCA AS A TOOL TO OPTIMIZE TRIE You maybe thinking that LCA has nothing to do with trie. but-witg SIMPLE usage of little thing called bitset,. we can chsnge this. simply make bitset remeber on evrry turn where yoou ended up afta joining nodes into components. time complexity: o(QlogLoglogNM) it can be essily proven but i will leave it to readers prectis

  5. COMPRESSING ENTIRE HASMHAP INTO A TRIPLET OF BINARY SEARCH TREES How? YOU WILLASK. i willsay: it csn be done with the help of our little mriemd bitset. we will simply store him into a SEPARATE container instead of keeping it with the other trees . This will also improve memory!!!! Readers practice

  6. MULTIPLYING BIGNUMS IN O(LOG23.5NMQRSQRT(LOG(nm))) Simply store the factors inside a RB tree of bitsets and use improved FFT.

  7. IMPROVED FFT Simply make bitset for every multiplication and merge them every logNth operation. You can not merge naively but it csn be easily merged via heuristic approach. readers prectis

  8. CONCAVE HULL TRICK Ok. You ssy concave hull can not be used for quad tree optimization trick. It can. One word: bitset.

  9. MACHINE LEARNING TRICK WITH BITSET Simply use AI bitset for storing your patterns.

  10. REVOLUTIONARY OPTIMIZATION OF BLOCK CHAIN The circular implementation of a new hashing algorithm using to optimize proof of work concept. Hashing the last block with the nonce from the previous nth block as to make it circular.

thank you for your attention mriemds,

With respect. bukefala


Tags optimizations, 2017, 2k17, topcoderjam


  Rev. Lang. By When Δ Comment
en1 English bukefala 2017-07-07 23:47:35 2791 Initial revision (published)