Editorial for Baltic OI '11 P5 - Meetings
Submitting an official solution before solving the problem yourself is a bannable offence.
Let's denote by the time needed for
participants to reach a decision. First we observe that
never decreases as
increases. From this follows that when we divide the
participants into
groups, we want to make the largest group as small as possible. Thus, it is optimal to let most
groups have size
and the last one may be smaller. This gives us a simple dynamic programming
solution with
memory and
time that would be sufficient to get
points:
a[1] = 0; // special case: no meeting
for (int i = 2; i <= n; ++i) {
a[i] = i * p + v; // baseline: no groups
for (int j = 1; j < i; ++j) {
// j groups: the size of groups is i/j rounded up
int k = (i - 1) / j + 1;
int t = a[k] + a[j];
if (a[i] > t)
a[i] = t;
}
}
Next we can observe that the inner loop in the above solution basically finds the value of as:
Since this is symmetric, we only need to consider the pairs where
, or
. Thus we can get a solution with
running time and earn
points just by replacing the line
for (int j = 1; j < i; ++j)
with the line
for (int j = 1; j * j < i; ++j)
To model dividing the groups into sub-groups, we can recurrently express and
in
, and eventually arrive at the general form:
Without further sub-grouping and thus the total working time corresponding to the grouping in
can be expressed as:
Obviously in
depends only on
, but not on the choice of values of
. Thus, to minimize the
value of
for a fixed
, we need to choose
so that
would be minimal.
Since the sum of factors multiplying to a given product is minimal when the factors are equal, we obtain the optimal value for when
are as close to
as possible. More precisely, we need to
use
for as many and
for as few
as possible so that
would still be at least
.
Since each must be at least
(there's no benefit in creating sub-groups with just one member), we only need to consider the values of
up to
. From the preceding, we can easily compute
using just
multiplications, which gives us a solution with
memory and
time that would get the full score:
// computes T(n, k) for fixed k
long long solve_k(long long n, int p, int v, int k) {
long long fact = (long long) pow(n, 1.0 / k);
// since fact was rounded down above, we now increase
// some factors by 1 to have them multiply to at least n
int incr = 0;
while (power(fact + 1, incr) * power(fact, k - incr) < n)
++incr;
// the answer is \sum(factors)*p + k*v
return (k * fact + incr) * p + k * v;
}
// computes T(n)
long long(solve(long long n, int p, int v) {
if (n == 1)
return 0;
long long result = solve_k(n, p, v, 1);
for (int k = 2; 2ll << k <= n; k++) {
long long r = solve_k(n, p, v, k);
if (result > r)
result = r;
}
return result;
}
Looking at the task text, there might be some doubt whether the group leaders are required to hold
a single meeting or may also form sub-groups among themselves. In other words, are we allowed to
use as the right-hand side of
or should we be restricted to
instead?
It turns out this does not matter, as any process involving the
group leaders forming
sub-groups
could also be modeled as forming
groups first and these splitting into a total of
sub-groups.
Comments