Maxim and Restaurant (Part 2)

Maxim and Restaurant (Part 1)

In previous post I discussed a O(n ^ 3 * k) solution. Today, I'm going to discuss how we can reduce the complexity to O(n ^ 2 * k). Basically if we see the problem from a different angle we don't need to run our DP for each blocker.

For n persons in queue, we have n! permutations. Lets consider the number of permutations for which we can allow only one person is p1, number of permutations for which we can allow two persons is p2, and so on.

So expected number of persons -
$e = \frac{p1 * 1 + p2 * 2 + ... pn * n}{n!}$

Which can be represented as -
$e = \frac{(p1 + p2 + ... + pn) + (p2 + p3 + ... + pn) + ... + (pn)}{n!}$

Here, p1 + p2 + ... + pn actually represents the number of ways where we can allow at least 1 persons. Lets call it m1. Similarly, p2 + p3 + .. + pn represents number of ways where we can allow at least 2 persons, which is m2 and so on.

So our equation is now -
$e = \frac{m1 + m2 + ... + mn}{n!}$
$=> e = \frac{m1}{n!} + \frac{m2}{n!} + \frac{m2}{n!}$
$=> e = f1 + f2 + .. + fn$

Here, fi = probability of allowing at least i persons.

In last post, in our dynamic programming has states dp[i][j]. In dp[i][j], we calculated probability of having sum j by adding first i persons. For a given k, if we add up all dp[k][j] for all 1 <= j <= p, we'll find the probability of allowing at least k persons. So by removing the blocker and running the dynamic programming algorithm only once we can simply calculate f1, f2, .. fn, and by adding these values, we can get our result.

So here is the simplified code -

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int[] a = new int[n];
        int total = 0;
        for (int i = 0; i < n; ++i) {
            a[i] = in.readInt();
            total += a[i];
        }
        int p = in.readInt();
        if (total <= p) {
            out.printLine(n);
            return;
        }

        double res = 0.;
        double[][] dp = new double[n + 1][p + 1];
        dp[0][0] = 1.0;
        for (int i = 0; i < n; ++i) {
            int cur = a[i];
            for (int oldCount = n - 1; oldCount >= 0; --oldCount) {
                for (int oldSum = 0; oldSum + cur <= p; ++oldSum) {
                    dp[oldCount + 1][oldSum + cur] += dp[oldCount][oldSum] / (n - oldCount) * (oldCount + 1);
                }
            }
        }

        for (int count = 1; count <= n; ++count) {
            for (int size = 0; size <= p; ++size) {
                res += dp[count][size];
            }
        }
        out.printLine(res);
    }

Maxim and Restaurant (Part 1)

Today I am going to discuss about a problem from +Codeforces - Maxim and Restaurant.

Maxim has n(<=50) guests in a queue and his table length is p (<=50). Maxim cannot arrange guests if summation of width of guests is more than p. So he allows next person in the queue to enter the room if total summation doesn't exceed p. If by adding next person makes it more than p, Maxim just discards the rest of the queue and doesn't allow anyone else to enter. What is the expected number of guests Maxim will allow if all of his guests queued up in a random order?

Solution:
We can iterate over all guests and consider that guest as a blocker, that means, this person will block the rest of the queue and will make the sum more than p.

We will now calculate a function f(count, sum), for all  0<=count<=n-1 and 0<=sum<=p. Here f(count, sum) represents, probability of having summation "sum" by adding first "count" persons in the queue. We'll be calculating f, without using the "blocker".  For all values of count and sum, f(count, sum) will contribute to our result if after adding blocker it makes the sum more than p. i.e. sum + width(blocker) > p. If that condition is true, we'll add $ f(count, sum) \times \frac{1}{n - count} \times count $. Here f(count, sum) is the probability of having summation "sum" by first "count" person, (1 / (n - count)) is the probability of having the blocker as a next person and count is the number persons will enter for this kind of permutation.

Check my java solution to see below how I calculated f using dynamic programming. Here dp(i, j) represents f(i, j).

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int[] a = new int[n];
        int total = 0;
        for (int i = 0; i < n; ++i) {
            a[i] = in.readInt();
            total += a[i];
        }
        int p = in.readInt();
        if (total <= p) {
            out.printLine(n);
            return;
        }

        double res = 0.;
        for (int blocker = 0; blocker < n; ++blocker) {
            double[][] dp = new double[n][p + 1];
            dp[0][0] = 1.0;

            for (int i = 0; i < n; ++i) {
                if (i == blocker) continue;
                int cur = a[i];

                for (int oldCount = n - 2; oldCount >= 0; --oldCount) {
                    for (int oldSum = 0; oldSum + cur <= p; ++oldSum) {
                        dp[oldCount + 1][oldSum + cur] +=
                              dp[oldCount][oldSum] / (n - oldCount) * (oldCount + 1);

                    }
                }
            }

            for (int count = 0; count < n; ++count) {
                for (int size = 0; size <= p; ++size) {
                    if (size + a[blocker] <= p) continue;
                    res += (dp[count][size] * count) / (n - count);
                }
            }
        }
        out.printLine(res);
    }

Here, dp[oldCount + 1][oldSum + cur] += dp[oldCount][oldSum] / (n - oldCount) * (oldCount + 1); because, after having a permutation of oldCount I can add a new person in this permutation in (oldCount + 1) possible positions. So we're multiplying (oldCount + 1), and probability of being selected at (oldCount + 1)th person from (n - oldCount) person is 1 / (n - oldCount). So we're multiplying this also. All f(count, sum) can be counted in O(n * n * p). As we're iterating over all the blockers. So the overall algorithm will be O(n ^3 * p).

No can you think of a solution having complexity O(n ^ 2 * p). I'll try to explain that in next post.