and who cares about them?

They have made bad problems too

For the UVa problem in the link: Let's calculate dp[l][r][len] — the most points we can gain if we do operations on s[l] to s[r] with the same len characters as s[r] attached at the back of the string. Let p be the leftmost index satisfing s[p] = s[p + 1] = ... = s[r] and q be some indicies satisfing s[q] = s[r] and s[q] ≠ s[q + 1].

Then we can list the dp equations:

• dp[l][r][len] = dp[l][p - 1][0] + (r - p + 1 + len)² — if we clean all blocks from p to r ;

• dp[l][r][len] = dp[q + 1][p - 1][0] + dp[l][q][r - p + len + 1] — if we decide to clean blocks from q + 1 to p - 1 first and the others at last.

For today's E problem just substitute (r - p + 1 + len)² with the most points we can gain from the string with same characters of length r - p + 1 + len. This can be done by another simple dp.

I know the constraints suggest a O(n³) solution, but maybe many states cannot be approached? I desire the proof too ><

Nope, a number can have max of n^1/3 factors.and for each factor we are doing only n^2/x^2 work so actual complexity would be near to n^2 with some constant.

if you just check from all the numbers from 1 to sqrt(n) for a divisor of n, then this is the complexity in the worst case.

You are trying to hack me haha. Find it out yourself

Binary search wouldn't work as it is not a monotonous sequence.
Eg:

 12
 E00
 E00
 E00
 E00
 E00
 E00
 E00
 E00
 E00
 E00
 E00
 E00
 

I also did the same, but here our assumption for binary search to work is that if the current_divisor is not answer then the answer is less than the current_divisor but this is false answer can be greater than current_divisor.

Consider first two submatrices starting from the first row:

11

11

and

10

10

Here the second submatrix doesn't have similar elements (combination of 0 and 1). So 2- compression isn't possible

See my implementation if you want short and easy to understand code.

root of all numbers in set are equal to x

Sorry, but I don't understand why did it cause so much abmiguity. There is no definition of some k-th root in the statement, only digital root of x, which, obviously, does not depend on any number k. Hence the phrase "k-th root" is something absolutely undefined.

I looked at the input reading in your code. You are currently using sys.stdin.readlines(). I've been a much bigger fan of sys.stdin.read().splitlines(). It might be quicker, but more importantly removes all '\n'. So I pretty much never use sys.stdin.readlines().

Switching to sys.stdin.read().splitlines() makes one of your solutions go from 1699 ms to 1434 ms. Then I tried to switch from PyPy3 to PyPy2. It went from 1434 ms to 1075 ms. So there's still a lot of things you can do to speed up your solution without modifying anything in the algorithmic part. Don't know how used you are to python 2 but it is usually noticeable faster than python 3.

Python2 is pretty similar to python3 code wise with some exceptions. A small tip is to start out your python 2 code with

from __future__ import print_function
range = xrange
input = raw_input

and most things will be like how it is in python3.