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/138112085int n;
bool a[LIM][LIM];
int b[LIM][LIM];
bool check(int x, int y, int u, int v) /// Check if this square is valid
{
int sum = b[u][v] - b[u][y - 1] - b[x - 1][v] + b[x - 1][y - 1];
return (sum == 0) || (sum == (u - x + 1) * (v - y + 1));
}
bool check(int scale) /// Check if the scaling is valid
{
for (int lx = 1, rx = scale; lx <= n; lx += scale, rx += scale)
for (int ly = 1, ry = scale; ly <= n; ly += scale, ry += scale)
if (!check(lx, ly, rx, ry)) return false;
return true;
}
int main()
{
ios::sync_with_stdio(NULL);
cin.tie(NULL);
/// Input
cin >> n;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; j += 4)
{
char c;
cin >> c;
/// Decode a[i][j]
int v = (c <= '9') ? c - '0' : c + 10 - 'A';
a[i][j + 0] = v >> 3 & 1;
a[i][j + 1] = v >> 2 & 1;
a[i][j + 2] = v >> 1 & 1;
a[i][j + 3] = v >> 0 & 1;
}
}
/// Constructing partialsum table
for (int i = 0; i <= n; ++i) b[i][0] = b[0][i] = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
/// Find answer
for (int x = n; x >= 1; --x)
if (n % x == 0 && check(x))
return cout << x, 0;
return 0;
}
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
int n;
bool a[LIM][LIM];
bool check(int scale) /// Check if this scaling is valid
{
for (int lx = 1, rx = scale; lx <= n; lx += scale, rx += scale)
for (int ly = 1, ry = scale; ly <= n; ly += scale, ry += scale)
for (int x = lx; x <= rx; ++x)
for (int y = ly; y <= ry; ++y)
if (a[x][y] != a[lx][ly])
return false;
return true;
}
int main()
{
// file("Test");
ios::sync_with_stdio(NULL);
cin.tie(NULL);
/// Input
cin >> n;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; j += 4)
{
char c;
cin >> c;
/// Decode a[i][j]
int v = (c <= '9') ? c - '0' : c + 10 - 'A';
a[i][j + 0] = v >> 3 & 1;
a[i][j + 1] = v >> 2 & 1;
a[i][j + 2] = v >> 1 & 1;
a[i][j + 3] = v >> 0 & 1;
}
}
/// Find result
for (int x = n; x >= 1; --x)
if (n % x == 0 && check(x))
return cout << x, 0;
return 0;
}
Can someone construct a test hack for it, since I failed to find such test that it will fail.
Did you notice that
so
then it can pass in at most 2 seconds with the extra operations you're doing (2e8 operations takes about 1 seconds).
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$$$
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.
Oh, that because of constant factor isnt it ?