Redaksiya

Let's solve this task when $k=0$.

The naive solution would be to sort the strings using comparator which checks for two strings $x,y$ if it is true that.

where $x+y$ denotes concantenation of strings $x$ and $y$.

However, this aproach could be too slow. There is a faster method of checking which of the following is smaller ($x+y$ or $y+x$). We will be checking this by precomputing hashes of every string and using binary search.

If hash of string $x+y$ is equal to hash of $y+x$ on position $mid$ then all the symbols of $x+y$ and $y+x$ untill $mid$ are equal (that means that we assign $l=mid$). Otherwise at least one symbol is different (so we assign $r=mid$).

When we found the position $k$ in which $k$'th symbol of $x+y$ is not equal to $k$'th symbol of $y+x$ we just compare them.

Total time complexity $O(n\cdot lo{g}^2(n))$.

When $k=1$, it is a bit more complicated. The solution is to check manually which string is the most optimal one for reversing. (And if it is actually optimal to reverse one of the strings)

First of all, we will need to store $2\cdot n$ pairs.

For every string in $c$ we will precompute hashes. After this we need to use the algorihtm from the solution for $k=0$.

Right now we have the optimal solution which uses $2\cdot n$ strings, we need to determine which one we will be reversing. For that we will be considering only ones that are smaller when reversed than the original ones.

After we determined the candidates for reversing, we will manually check which string concantenation is lexicographically the smallest one.

For this, we will compute hashes for concantenation of all strings without the reverses.For each reversed string we will store the index in which it should have started if it was included in the resulting string, and the index in which the original string (not reversed) starts.

Let's call $b_i$ the string concantenation if reversed is $i$'th string. Also, $b_0$ is concantenation in which no string is reversed. In order to check which one is smaller $b_x$ or $b_y$, we will need several things:

• position of strings $s_x$ and $s_y$ in array $c$.

• length of all strigns that are not reversed and are placed before our strings

• indexes in which reversed strings $x$ and $y$ start.

• indexes in which not reversed strings $x$ and $y$ start.

Let's check what happens with $b_0$ when we reverse string $x$:

we erase segment which contains string $x$ and insert segment of $reversed(s[x])$.

So:

As we can see, there are 4 segments which form $b_x$ and the difference between $b_0$ ans $b_x$ is not really that big. If we have computed hashes for $b_0$, hashes for reversed strings, indexes in which the partition of $b_0$ happens for each $b_i$ needed, we can use the same technique that we used while comparing strings via binary search in block where $k=0$.

Hence, the total time complexity is equal to $O(n\cdot lo{g}^2(n)+n\cdot log(n))=O(n\cdot lo{g}^2(n))$.

Please don't forget that this solution has to be optimized as much as possible because there is a huge constant factor that comes out of hashing.