SPyofgame's blog

By SPyofgame, history, 3 years ago,

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

$\begin{cases} 1 \leq lx \leq rx \leq n\\ 1 \leq ly \leq ry \leq n\\ rx - lx + 1 = v\\ ry - ly + 1 = v\\ v\ |\ rx\\ v\ |\ ry\\ \end{cases}$

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$.

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

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(d(n) \times n^2)$ and atleast $O(n^2)$.

It should fail but it didnt, it passed in $1216 ms$

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

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

• +7

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   0 Did you notice that $4 \le n \le 5200$so $n^{2} \le 27040000$then it can pass in at most 2 seconds with the extra operations you're doing (2e8 operations takes about 1 seconds).‬
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 But it the worst case it is $O(d(n) \times n^2)$ not $n^2$.The positive integer with most divisors below $5200$ is $5040$ with $60$ divisorsIn the worst cases in should be $T(n) = c_0 \times 5040^2 \times 60 = 1524096000 = 15.24096 \times 10^8$
 » 3 years ago, # |   0 The worst-case for your code is when it notices a problem only at the very last element at each iteration with n=5040. I suspect that's exactly what's happening in test cases 57 and 70. So your solution probably isn't hackable.
•  » » 3 years ago, # ^ |   0 Oh, that because of constant factor isnt it ?