SPyofgame's blog

By SPyofgame, history, 2 months ago, In English

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


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


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

  • Vote: I like it
  • +7
  • Vote: I do not like it

2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Did you notice that

$$$4 \le n \le 5200 $$$


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

  • »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    In the worst cases in should be $$$T(n) = c_0 \times 5040^2 \times 60 = 1524096000 = 15.24096 \times 10^8$$$

    • »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you are right, maybe the tests are not so strong, or maybe codeforces servers can run 1e9 operations in 1 second then we won't have any troube by your time complexity XD.

2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.