i tired shell sort,it was giving TLE

1 3 2 4.

Это по-вашему отсортирован?

Here is the greedy algorithm to deal with problem E.

step 1: Start with an uncolored table.
step 2: Set the pointer to the first cell.
step 3: If the pointed cell is uncolored, run the greedy subroutine described below.
step 4: If the pointer hasn't reach the last cell, set the pointer to the next cell(from left to right and from top to bottom as the problem mentioned), then go to step 3.
step 5: end the algorithm

The greedy subroutine:
step 1: Mark an 1*1 square whose upperleft corner is the pointed cell.

step 2: Determine the color of the pointed cell by choosing the smallest possible letter without breaking the rules. This color(chosen color) will be used to color all the cells in the square.

step 3: Enlarge the square from n*n to (n+1)*(n+1) (the upperleft corner of the square is still the pointed cell)

step 4: If atleast one of the conditions below is true, cancel the last enlarge step(change back the size from (n+1)*(n+1) to n*n) and go to step 5. Else, go to step 3.
(1) Any of the cells in the square is already colored.
(2) Square go out of bound.
(3) the cell in upperright corner of the square can be colored with a smaller letter than the chosen color without connecting its neighbors outside the square. (connecting means two cells using same color and share a side, same as the definition in the problem)
(4) If color all the cells in the square with the chosen color, any of the cells in the square(only need to check the border cells) is connecting to some cell outside the square.

step 5: Color all the cells in the square using the chosen color in step 2.

step 6: end the subroutine.

a>=1111 поэтому и RE

you can check how many characters from position i matches with the prefix of the string with z-algo in O(N) and determine the suffixes that matches prefix.

After that construct a suffix array and compute lcp of all suffixes with the suffix of position 1(whole string). you can build suffix array in nLOGn^2 and get all LCP in nLOGn. It will work because you are literally comparing the prefix with all possible substring start points. Store the LCP values in a frequency array and do a cumulative sum in reverse order. It will give you frequency of each prefix substring. It will work because if you found a LCP of 5 between two string that means you can also get a common prefix of (1,2,3,4).

my submission

you can check how many characters from position i matches with the prefix of the string with z-algo in O(N) and determine the suffixes that matches prefix.

After that construct a suffix array and compute lcp of all suffixes with the suffix of position 1(whole string). you can build suffix array in nLOGn^2 and get all LCP in nLOGn. It will work because you are literally comparing the prefix with all possible substring start points. Store the LCP values in a frequency array and do a cumulative sum in reverse order. It will give you frequency of each prefix substring. It will work because if you found a LCP of 5 between two string that means you can also get a common prefix of (1,2,3,4).

my submission

The Z-function method is obviously simpler and more intuitive. here.

Now, let's understand how the prefix-function method works. here.

Checking which prefixes-suffixes match is pretty straightforward. $$$pi[N]$$$ stores the length of the longest proper prefix which is also a suffix. So, this is our first matching prefix-suffix. Now, $$$pi[pi[N]]$$$ stores the length of the longest matching prefix-suffix of length less than $$$pi[N]$$$. Similarly, $$$pi[pi[pi[N]]]$$$ stores the length of the longest matching prefix-suffix whose length is less than $$$pi[pi[N]]$$$, and so on, until finally the length of our prefix becomes $$$0$$$.

Now, how does the less intuitive tree method work, for counting the number of occurrences of each prefix. There are $$$N+1$$$ vertices from $$$0$$$ to $$$N$$$, each denoting a prefix of that length. There is at least once occurrence of each prefix. Also, $$$pi[v]$$$ denotes that there is an occurrence of the prefix of length $$$pi[v]$$$. Now, for each vertex $$$v$$$, we add an edge from vertex $$$pi[v]$$$ to $$$v$$$. Then, the number of occurrences of a vertex of length $$$v$$$ will be $$$1$$$ $$$+$$$ frequency of $$$v$$$ in the $$$pi$$$ array $$$+$$$ sum of all occurrences of its immediate children in the tree.

Why? $$$pi[v]$$$ signifies that the prefix of length $$$pi[v]$$$ is the immediate fallback for the prefix of length $$$v$$$, meaning: the prefix of length $$$pi[v]$$$ is the next longest prefix which will definitely be present in any string which contains the prefix of length $$$v$$$. So, a prefix of length $$$v$$$ will be contained in any prefix of length $$$u$$$, such that $$$pi[u]=v$$$. So, just adding the contributions of the immediate children in the tree gives us the contribution of all places where the prefix of length $$$v$$$ was inside another prefix of a longer length, and prevents over-counting.

It can also be solve by using suffix array, here's my shitty code(no one can understand) 86931883

It should've give TLE but it didn't, idk why.

z functions and ordered set for count