FBI's blog

By FBI, history, 16 months ago, In English

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!

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

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FBI (previous revision, new revision, compare).

»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The first trick is used in this cf problem 429D - Tricky Function.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks, added the link

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FBI (previous revision, new revision, compare).