Today, the problem G2 could be solved in an extravagant way, using randomized xor-hashing, I am not quite sure what is the chance that I will get hacked,so please feel free to either try and hack my solution, or write a comment describing approximated chance of my random getting hacked. (If you do come up with the approximation, i will edit the blog to include your statement)

Here`s the submission 238069601

UPD: My solution turned out to be the one that is the main one

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!

Last 2 or 3 contests solutions are being leaked in the internet,and because of that many "smart people",that have no clue how to solve something,are being carried up in the tournament table.Is this fair? I think no,but leave your opinion in comments.

edit: today A,B,C and D were leaked,so I think it affected almost every rated participant

Since 12.07.2021 I have been solving at least 1 problem a day,and now I don't know if I should keep going up until 730 days,or just give up?