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.