I come to a fun problem, and after I tried hard to solve it, I curiously to find better algorithm, but I cant.
The problem is:
There are $$$N$$$ buildings with $$$a_1, a_2, \dots, a_n$$$ metters height. These days are hard, the heavy raining weather still not ended yet. In day $$$d$$$, every building with height $$$h$$$ only have $$$x_d = \lfloor \frac{h}{d} \rfloor$$$ height left of good space to use, while others are sunk underwater. Every building having the same value $$$x_d$$$ on day $$$d$$$ will group together (including $$$x_d = 0$$$ which sunk completely underwater) in a way that no other building with same value $$$x_d$$$ in another group.
The question is:
In each size $$$s$$$ from $$$1$$$ to $$$n$$$, what is the earliest day $$$d$$$ that have at least one group of size $$$s$$$ (if there is no suitable day then output -1)
The constraints are:
- $$$N \leq 300$$$
- $$$a_i \leq 10^9$$$
The examples are:
Input:
3
1 2 5
Output:
1 3 6
Explanation:
Day 1: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{5}{1} \rfloor$$$ } $$$=$$$ { $$$1, 2, 5$$$ } — First group of size 1: Any of {$$$1$$$} {$$$2$$$} {$$$5$$$}
Day 2: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{5}{2} \rfloor$$$ } $$$=$$$ { $$$0, 1, 2$$$ }
Day 3: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{5}{3} \rfloor$$$ } $$$=$$$ { $$$0, 0, 1$$$ } — First group of size 2: Only {$$$1, 2$$$}
Day 4: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{4} \rfloor, \lfloor \frac{2}{4} \rfloor, \lfloor \frac{5}{4} \rfloor$$$ } $$$=$$$ { $$$0, 0, 1$$$ }
Day 5: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{5} \rfloor, \lfloor \frac{2}{5} \rfloor, \lfloor \frac{5}{5} \rfloor$$$ } $$$=$$$ { $$$0, 0, 1$$$ }
Day 6: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{6} \rfloor, \lfloor \frac{2}{6} \rfloor, \lfloor \frac{5}{6} \rfloor$$$ } $$$=$$$ { $$$0, 0, 0$$$ } — First group of size 3: Only {$$$1, 2, 5$$$}
Input:
3
1 1 5
Output:
1 1 6
Explanation:
Day 1: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{1} \rfloor, \lfloor \frac{1}{1} \rfloor, \lfloor \frac{5}{1} \rfloor$$$ } $$$=$$$ { $$$1, 1, 5$$$ } — First group of size 1: Any of {$$$1$$$} {$$$1$$$} {$$$5$$$}
Day 2: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{2} \rfloor, \lfloor \frac{1}{2} \rfloor, \lfloor \frac{5}{2} \rfloor$$$ } $$$=$$$ { $$$0, 0, 2$$$ } — First group of size 2: Only {$$$1, 1$$$}
Day 3: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{3} \rfloor, \lfloor \frac{1}{3} \rfloor, \lfloor \frac{5}{3} \rfloor$$$ } $$$=$$$ { $$$0, 0, 1$$$ }
Day 4: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{4} \rfloor, \lfloor \frac{1}{4} \rfloor, \lfloor \frac{5}{4} \rfloor$$$ } $$$=$$$ { $$$0, 0, 1$$$ }
Day 5: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{5} \rfloor, \lfloor \frac{1}{5} \rfloor, \lfloor \frac{5}{5} \rfloor$$$ } $$$=$$$ { $$$0, 0, 1$$$ }
Day 6: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{6} \rfloor, \lfloor \frac{1}{6} \rfloor, \lfloor \frac{5}{6} \rfloor$$$ } $$$=$$$ { $$$0, 0, 0$$$ } — First group of size 3: Only {$$$1, 2, 5$$$}
Input:
3
2 2 2
Output:
-1 -1 2
Explanation:
Day 1: $$$x[d] = $$$ { $$$ \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor$$$ } $$$=$$$ { $$$2, 2, 2$$$ } — First group of size 3: Only {$$$2, 2, 2$$$}
Day 2: $$$x[d] = $$$ { $$$ \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor$$$ } $$$=$$$ { $$$0, 0, 0$$$ }
Day 3: $$$x[d] = $$$ { $$$ \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor$$$ } $$$=$$$ { $$$0, 0, 0$$$ }
Day 3 $$$\leq k \rightarrow \infty$$$: $$$x[d] = $$$ { $$$ \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor$$$ } $$$=$$$ { $$$0, 0, 0$$$ } — There are no group of size 1 and 2
My approach to this problem:
Since day $$$k > max(a[i])$$$ will make all array always being as $$$x[k] =$$$ {$$$0, 0, \dots, 0$$$}, we only need to check for each value $$$k \in [1, d]$$$. Then we can calculate how many group of size $$$s$$$ in day $$$k$$$. My approach is to increase the value $$$f[\lfloor \frac{a_i}{k} \rfloor] = s$$$ means in day $$$\lfloor \frac{a_i}{k} \rfloor$$$ have group of size $$$s$$$, then minimize the first day we have the group of size $$$s$$$
This approach is $$$O(n \times max(a_i))$$$
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
int k = *max_element(all(a)) + 1;
vector<int> f(k + 1, 0);
vector<int> q(n + 1, +INF);
for (int x = 1; x <= k; ++x) /// Checking possible dividing value
{
for (int t : a) ++f[t / x]; /// Calculating value f[] for each day [t / x]
for (int t : a) minimize(q[f[t / x]], x); /// Minimize first day have group of size k
for (int t : a) --f[t / x]; /// Reset the array
}
for (int i = 1; i <= n; ++i)
cout << (q[i] == +INF ? -1 : q[i]) << '\n';
return 0;
}
Lets $$$setL$$$ be a set of good potential $$$k$$$ for dividing. Since there are some $$$k$$$ that having group of size $$$s$$$ but never will be good enough to be the smallest day. That is for each $$$a_i$$$, we find all $$$k$$$ that have smallest day $$$d$$$ that might appear a group of size $$$\lfloor \frac{a_i}{k} \rfloor$$$ and insert into $$$setL$$$.
The upper bound complexity is $$$O(n\ \times k log(k))$$$ where $$$k = |setL| = O(n \times \sqrt{max(a_i)})$$$ but since $$$a_i$$$ is small, and the bigger $$$n$$$ is, the more number of duplicate values will all be eliminated by using $$$set<>$$$. It would reduce both complexity and constant factor significantly
int main()
{
int n;
cin >> n;
set<int> setL;
vector<int> a(n);
for (int &x : a)
{
cin >> x;
int sqrtx = sqrt(x);
for (int t = 1; t <= sqrt(x); ++t)
{
setL.insert(x / t + 1);
setL.insert(t + 1);
}
setL.insert(x + 1);
setL.insert(1);
}
vector<int> res(n + 1, +INF);
for (int x : setL)
{
map<int, int> F;
for (int t : a) ++F[t / x]; /// Calculating value f[] for each day [t / x]
for (int t : a) minimize(res[F[t / x]], x); /// Minimize first day have group of size k
}
for (int g = 1; g <= n; ++g) cout << (res[g] == +INF ? -1 : res[g]) << '\n';
return 0;
}
With $$$T = \sqrt{max(a_i)}$$$ then all such $$$k \leq T$$$ are potential. We only care for such $$$k > T$$$ which we can use branch and bound to reduce constant matter.
By using map, we can calculate faster by ignoring duplicates. Iterating through map reducing the $$$O(log)$$$ factor each query
int n;
vector<int> a;
map<int, int> b;
map<int, int>::iterator it;
int delta = 0;
vector<int> res;
void solve(int x)
{
int sum = 0, val = -1;
for (it = b.begin(); it != b.end(); ++it)
{
int cur = it->first / x;
if (cur != val)
{
if (res[sum - 1] == +INF) delta--;
minimize(res[sum - 1], x);
val = cur;
sum = 0;
}
sum += it->second;
}
if (res[sum - 1] == +INF) delta--;
minimize(res[sum - 1], x);
if (delta == 0)
{
for (int x : res) cout << x << '\n';
exit(0);
}
}
int main()
{
cin >> n;
a.resize(n);
for (int &x : a)
{
cin >> x;
++b[x];
}
delta = n;
res.assign(n, +INF);
int k = ceil(sqrt(*max_element(all(a))));
for (int x = 1; x <= k; ++x) solve(x);
if (k > 1)
{
set<int, greater<int> > S;
for (int x : a) S.insert(x);
set<int> setL;
for (int x : S)
{
int lim = min(k, x / (k - 1));
for (int t = 1; t <= lim; ++t)
{
int v = x / t + 1;
setL.insert(v);
}
}
for (int x : setL) solve(x);
}
for (int x : res) cout << (x == +INF ? -1 : x) << '\n';
return 0;
}