# Editorial

Problem Author: | Illia Shevchenko |

Prepared by: | Illia Shevchenko, Maksym Shvedchenko |

Editorial by: | Illia Fursov |

Group 1. $a=b=c=d$.

In this group, the condition about the equality of the strings is already satisfied. But we also need the strings not to be all equal, thus we need to change any two strings so that they are equal, but not equal to the other two. You can change the same character in both strings, and it will take $2$ operations ($1$ for both strings), so the answer for this group is always $2$.

Time and memory complexity: $O(1)$ (or $O(N)$) (you can even not read any of the input)

Group 2. $a=b=c$.

Note that when making string $s$ equal to $t$ you can avoid making them equal to the other strings. If there is some index $i$ such that $s_{i}=t_{i}$, then you can make $s_{i}$ equal to $t_{i}$ if there is no other string $m$ such that $m_{i}=t_{i}$ and make $t_{i}$ equal to $s_{i}$ otherwise.

If $d=a=b=c$, then the answer is $2$ as in the previous group. Otherwise, you can choose any of the first three strings — for example, $c$ — and make it equal to $d$. Let's say that the distance $dst(s,t)$ between two strings of the same length is the number of positions where their characters are different. Then, the number of operations needed to make $c$ equal to $d$ is $dst(c,d)$, and this is the answer for this group, because if we make $c$ equal to $d$, then $c$ is not equal to $a$ anymore and the pairs of equal strings become different.

Time complexity: $O(N)$ (because of $dst()$ function)

Memory complexity: $O(N)$

Group 3. $a=b$.

Still, if $a=b=c=d$, the answer is $2$. Otherwise, there are two options to satisfy the conditions: make $c$ equal to $d$ in $dst(c,d)$ operations or make $a$ equal to $c$ and $b$ equal to $d$ in $dst(a,c)+dst(b,d)$ operations. But actually, $dst(a,c)+dst(b,d)=dst(a,c)+dst(a,d)=dst(c,a)+dst(a,d)≥dst(c,d)$, so the answer is $dst(c,d)$.

Time complexity: $O(N)$

Memory complexity: $O(N)$

Group 4. $n=1$.

In this group you can check all the pairs of pairs you can make to satisfy the conditions and take the minimum number of operations needed to do it out of these pairs. For every pair, this number is $0$ if $a=b$ and $1$ if $a=b$.

To check all the cases, you can try to "connect" the string $a$ with $b$ ($c$ and $d$), "connect" another two strings with each other, calculate the sum of needed number of operations for both pairs and take the minimum result out of all cases.

Time and memory complexity: $O(N)$.

Group 5. $1≤n≤10_{5}$

The solution for this group is the same as for the previous one, but now you need to calculate the minimum sum of $dst()$'s instead of just zeros and ones.

Time and memory complexity: $O(N)$.