This is the editorial for the Unofficial Div 4 Round #2 created by SlavicG and mesanu.
We hope everyone had fun and enjoyed the contest!
Problem A — Catching the Impostor.
Tutorial
The problem is just implementation. Just check if exactly $$$n$$$ $$$-1$$$ numbers are encountered. You can easily do this using a set or a frequency array.
Problem B — Epic Permutation
Tutorial
There is only one epic permutation for each $$$n$$$, and the permutation always looks like this [ $$$1$$$, $$$2$$$, $$$3$$$,... ]. This is because the greatest gcd we can obtain for each position $$$i$$$ and the element at that position is the position itself if we choose the element to be equal to the position. So the answer is just the sum of the first $$$n$$$ positive integers. It can be calculated using a loop because of the small constraints or using the formula $$$\frac{n \cdot (n+1)}{2}$$$.
Problem C — Similar Arrays
Tutorial
It can be proven that the best number to create the array with, is the median (the middle element when the array is sorted) of the initial array. So, sort the array. Now, the median is the middle element $$$(med = a[n/2])$$$. To get the answer iterate over the array and add $$$abs(a_i - med)$$$ to it.
Proof why the median is the best choice
We denote the median as $$$m$$$. We have the sorted array $$$a$$$ where some elements are smaller, some are equal, and some are larger than $$$m$$$ in this order. Let's consider the other possible choices which are, choosing a smaller value than $$$m$$$ and a larger value than $$$m$$$ if we choose a greater value than $$$m$$$, then the difference between the elements smaller and equal to $$$m$$$ will increase by $$$x - m$$$. And the difference between the elements greater than $$$m$$$ will increase by $$$x - m$$$. But, because there are at least as many elements equal or smaller to $$$m$$$ as elements greater than $$$m$$$ we can see it is not optimal to choose this number, because in the best case, the difference wouldn't change and in the worst case, it would change by $$$x$$$. The same technique can be used for numbers smaller than $$$m$$$. This leaving $$$m$$$ as the best choice.
Problem D — Sanda's Job
Tutorial
We need to find if the difference between $$$n$$$ and $$$x$$$ is also a permutation of $$$x$$$'s digits. There are many ways to do this, and our solution is to transform $$$x$$$ and $$$n-x$$$ into strings, then sort the strings and see if they are equal. This is possible in C++ using to_string(int value) function.
Problem E — Count Substrings
Tutorial
We iterate through string $$$s$$$, and whenever we encounter a substring $$$t$$$, we add to the answer the number of unique substrings we can make using it. We can calculate this with the formula (number of characters since the start of the last encounter)$$$\cdot$$$(the number of characters until the end of the string). This is because the start of the substring must be between the start of the last $$$t$$$ substring in $$$s$$$ and the start of the $$$t$$$ substring just encountered(so we don't double count previous substrings). The end must be between the last element of this $$$t$$$ substring and the last element of string $$$s$$$.
Problem F — Game on Grid
Tutorial
