Can somebody hack my brute-forces solution ?

Revision en1, by SPyofgame, 2021-12-05 19:06:50

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)

My approach

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} (\frac{n}{x})^2 = n^2 \times \underset{x|n}{\Large \Sigma} (\frac{1}{x})^2 = n^2 \times \frac{\pi^2}{6} = O(n^2)$$$

This give us a simple solution that run in $$$373 ms$$$.

https://codeforces.net/contest/1107/submission/138112085

But my brute-force version of the solution also passed in $$$1216 ms$$$

https://codeforces.net/contest/1107/submission/138111659

The complexity seems to be at most $$$O(σ(n) \times n^2)$$$ and atleast $$$O(n^2)$$$, it should fail but it didnt

Can someone construct a test hack for it, since I failed to find such test that it will fail.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English SPyofgame 2021-12-05 21:34:19 2
en3 English SPyofgame 2021-12-05 19:09:42 23
en2 English SPyofgame 2021-12-05 19:08:41 368
en1 English SPyofgame 2021-12-05 19:06:50 4652 Initial revision (published)