The Statement
Here in this problem 1107D. Compression
Given an integer $$$n$$$ and a binary table $$$A[n][n]$$$
We are asked to find maximum $$$x$$$ that exist a binary table $$$B\left[\left \lceil \frac{n}{x} \right \rceil \right]\left[\left \lceil \frac{n}{x} \right \rceil \right]$$$
That this equation is satisfied $$$B\left[\left \lceil \frac{i}{x} \right \rceil \right]\left[\left \lceil \frac{j}{x} \right \rceil \right]$$$ $$$= A[i][j]\ \forall\ 1 \leq i, j \leq n$$$ (sorry but I dont know why the latex is broken like that)
The solution
So my approach is to check for all $$$v | n$$$ if there is exist such table.
Let call a square $$$(lx, ly)$$$ is a subtable $$$A[lx..rx][ly..ry]$$$ for
So there are $$$\frac{n}{v} \times \frac{n}{v}$$$ such subtables
Binary Table $$$B[][]$$$ will exist if and only if $$$A[x][y] = A[u][v]$$$ for all subtables $$$(lx, ly)$$$ and $$$lx \leq x, u \leq rx$$$ and $$$ly \leq y, v \leq ry$$$
My solution is just check for all $$$x\ |\ n$$$ from $$$n$$$ downto $$$1$$$.
If $$$x$$$ is satisfied then just simply output it.
The checking can simply be done using partial sum matrix.
The complexity will be $$$\underset{x|n}{\Large \Sigma} \left(\frac{n}{x} \right)^2 = n^2 \times \underset{x|n}{\Large \Sigma} \left(\frac{1}{x}\right)^2 = n^2 \times \frac{\pi^2}{6} = O(n^2)$$$
This give us a simple solution that run in $$$373 ms$$$.
My Hacking Question
For brute-force version, I check it by comparing each position one by one.
So the complexity seems to be at most $$$O(σ(n) \times n^2)$$$ and atleast $$$O(n^2)$$$.
It should fail but it didnt, it passed in $$$1216 ms$$$
Can someone construct a test hack for it, since I failed to find such test that it will fail.
