Blog with useful not so obvious implementations of well-known algorithms

Revision en4, by FBI, 2023-02-17 12:37:42

So, the main reason why I am writing this blog is because I think that it may be useful for everybody who struggles with ideas but knows hoe to code well.

First trick

concerns every task of finding a minimum of the function among every continuous subsequence of the array if \begin{equation}f(l,r)\end{equation} is defined as \begin{equation} f(i, j) (1 ≤ i, j ≤ n)=q(i, j)^2 + g(i, j)^2\end{equation} And \begin{equation} g(l,r)=g(1,r)-g(1,l-1)\end{equation} \begin{equation} q(l,r)=q(1,r)-q(1,l-1)\end{equation} The way to solve this is by rewriting this formula into \begin{equation} f(i,j)=\sqrt{a^2+b^2}\end{equation} I think that if you learnt geometry in school, you certainly understand that this is eulers distance formula. Now, if we want to find the minimum among every pair, we just have to find the minimum distance between 2 points on the grid! And there actually exists an algorithm to compute this answer in O(n*logn) it is described here

One of the tasks that can be solved using this: 429D - Tricky Function

Second trick

Concerns tasks in which we need to compute maximum of the same function. By transferring every point to the grid, we can solve this task geometrically,there exists an algorithm that solves it in O(n*logn) time (convex hull trick) implementation and proof why it works

Third trick

(the last one i can remember while being in a hospital because of my heart problems)

Is to use binary prefix trie if we have to find k-th MEX of the array. Also, it can be used if we have to compute the answer while XOR-ing every element of an array with some X (I can`t find the problem, so if someone knows what I am talking about, give me the link to that problem)

Feel free to share some tricks in comments,to save this blog, to upvote it so other people also know these tricks and even maybe share their own trick knowledge, every trick written in comments will be added to this blog!

Tags #geometry, #tricks, #binary-trie, #convex hull


  Rev. Lang. By When Δ Comment
en4 English FBI 2023-02-17 12:37:42 66
en3 English FBI 2023-02-17 11:07:01 316 (published)
en2 English FBI 2023-02-17 10:57:32 1223
en1 English FBI 2023-02-17 10:09:55 755 Initial revision (saved to drafts)