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.

Perfect Memory

Problem name: Perfect Memory
Problem source: Topcoder, SRM 513, Div 1 - 500
Link: http://www.topcoder.com/stat?c=problem_statement&pm=11500 (Log in is required to see the problem)

In this problem you have a board having N * M cells. Each cell has a symbol in it's back. Each symbol is in exactly two cells in the board. So there will be (N * M) / 2 symbols. In each move you can turn two cells one by one to see the symbols behind them. If these two symbols differ, both the cell turned back to hide the symbols again. If both the symbols are same, they will remain same and never turn back again. What is the expected number of moves to make all the symbols visible, if you have the perfect memory?

Note that, having perfect memory, you'll never forget what was the symbol in a cell which you saw, but turned back. In this problem it's guaranteed that N * M will be even.

I couldn't solve this problem in real contest. I thought in each turn both of the cells will be turned simultaneously. But in the problem statement it was clearly mentioned that, two cells will be turned one by one. It seems that I am not the only one who got this wrong.

This problem can be solved by dynamic programming. Our state will be (total, seen, turn). Here,
total = number of symbols for which both cells are not seen yet i.e. at least one cell is unseen. So we are actually considering (2 * total) cells.
seen = number of symbols partially seen i.e. number of cells of which exactly one cell is seen.
turn = Is this the first turn or second turn of the move? We know each move consists of two turns.

Initially, total = (N * M) / 2, seen = 0, and turn = FIRST.

Boundary condition: If total = 0, we don't have any symbol left to consider, so expected number will be zero.

In state (total, seen, turn), we have (total * 2 - seen) cells we didn't see yet. Lets say unseen = total * 2 - seen.

Now if the turn = FIRST, here we will always open an unseen cell and two things can happen after turning a cell on.
1. With p1 probability the cell contains a symbol which is already seen in another cell.
2. With p2 probability the cell contains a new symbol which is not visible before.

Here,
p1 = seen / unseen
p2 = 1.0 - p1

If (1) happens, we will just turn on the other symbol we already saw, and both will remain open forever. So our new state will be (total - 1, seen - 1, FIRST) and one move will be completed.
If (2) happens, new state will be (total, seen + 1, SECOND)

exp_move(total, seen, FIRST) = p1 * (1 + exp_move(total - 1, seen - 1, FIRST)) +
p2 * (exp_move(total, seen + 1, SECOND)

Note that, in first option we completed a move, so added +1, but in second option move is not done yet.

If turn = SECOND, we'll open another unseen cell. Three things can happen
1. With probability p1, symbol in the SECOND turn matches with the symbol of the FIRST turn.
Here p1 = 1 / unseen
2. With probability p2, symbol in the SECOND move matches with a symbol which is previously seen, but not seen in the first turn of this move. So,
p2 = seen / unseen - p1 = (seen - 1) / unseen
3. With probability p3, symbol in the SECOND move is completely a new symbol.
p3 = 1 - p2 - p3

If (1) happens, this pair will remain visible, so our state will be (total - 1, seen - 1, FIRST) and one move will be completed.
If (2) happens, this pair will be turned back, but we know both cells of the symbol of last turn. So we'll open both symbol in next move, so two moves will be completed in this case and new state will be (total - 1, seen - 1, FIRST).
If (3) happens, just another seen added. So state will be (total, seen + 1, FIRST), and one move will be completed.

exp_move(total, seen, SECOND) = p1 * ((exp_move(total - 1, seen - 1, FIRST) + 1) +
p2 * ((exp_move(total - 1, seen - 1, FIRST) + 2) +
p3 * ((exp_move(total, seen + 1, FIRST) + 1)

My solution in C++:

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <queue>
#include <cstring>
#include <set>
#include <ctime>
#include <cfloat>
using namespace std;

typedef long long i64;
#define I64 "%lld"
#define rep(i,n) for (i=0; i < (n); ++i)
#define all(c) (c).begin(),(c).end() 

bool done[1500][1500][2];
double memo[1500][1500][2];
enum{FIRST = 0, SECOND};
double exp_move(int total, int seen, int turn) {
    double &ret = memo[total][seen][turn];
    if (done[total][seen][turn]) return ret;
    done[total][seen][turn] = true;

    int unseen = total * 2 - seen;
    if (total == 0) return ret = 0;

    ret = 0.;
    
    // open one unseen cell randomly
    if (turn == FIRST) {
        double p1 = 0, p2 = 0;

        // Probability of it's pair is already seen is p1
        if (seen > 0) {
            p1 = (double) seen / (double) unseen;
            ret += p1 * (exp_move(total - 1, seen - 1, FIRST) + 1);
        }

        // Probability of it's pair is not seen yet is p2
        if (unseen > seen) {
            p2 = 1.0 - p1;
            ret += p2 * (exp_move(total, seen + 1, SECOND));
        }
    }
    else {
        double p1 = 0, p2 = 0, p3 = 0;

        // Probability of it's pair is already open is p1
        p1 = (double) 1 / (double) unseen;
        ret += p1 * (exp_move(total - 1, seen - 1, FIRST) + 1);

        // Probability of it's pair is seen but not open is p2
        if (seen > 1) {
            p2 = (double) (seen - 1) / (double) unseen;
            ret += p2 * (exp_move(total - 1, seen - 1, FIRST) + 2);
        }

        // Probability of it's pair is unseen is p3
        if (unseen > seen) {
            p3 = 1.0 - p1 - p2;
            ret += p3 * (exp_move(total, seen + 1, FIRST) + 1);
        }
    }
    return ret;
}

class PerfectMemory {
    public:
    double getExpectation(int N, int M) {
        return exp_move((N * M) / 2, 0, FIRST);
    }
};