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