Turn dynamic programming into mathematical formula


  • 11
    S

    Firstly, we define N = buckets, T = minutesToTest / minutesToDie (round below as integer division), so we can see T is the maximum times we can carry out our test (we can have all our pigs drinking water at the same time and regard it as ONE test).

    Then according to dynamic programming, define dp[n][t] as the maximum buckets we can detect when one of them contains poison, given the n pigs at the beginning and t times for carrying out tests. So let's go through some basic cases.

    dp[1][1] == 2, since if you have just one pig and can only do one test, the maximum buckets you can detect is 2: you can choose any one bucket to feed the pig, and if it dies after a certain time, the poison is in the chosen bucket, otherwise in the other one.

    Then we can know that dp[1][t] == t + 1, you can carry out tests that have the only one pig drinking bucket one by one and get the poisonous bucket.

    How about dp[n][1]? This is a little tricky. We can encode the buckets with binary number, for example, there is 16 buckets and we encode them from 0 to 15 as 0000, 0001, 0010, ..., 1110, 1111, and also give each pig a sequence number from 0 to n - 1. After that, we feed these n pigs as binary number do, that is, we don't feed bucket 0 to any pig, since bucket 0's code is all 0s; we feed bucket 10 whose code is 1010 to pig 1 and pig 3, since the bit 1 and bit 3 of 1010 is 1s while other bits are 0s(we count the bit from LSB and start from 0). After feeding the pigs, we can view the state of each pig, and set state "alive" as 0 and "died" as 1, then these pigs' states form a binary number, for example 1100, means pig 2 and pig 3 are died, which means the code of poisonous bucket is exactly 1100, namely bucket 12. Thus, we can detect as many as 2^n buckets in one test with n pigs, that is, dp[n][1] == 2^n.

    With these basic cases, we can construct our state transition equation now. For dp[n][t], how can we make full use of all 2^n states those pigs can generate after one test? The answer is simple. After one test, if all pigs dies, we must assure there is only one bucket that all pigs drank from, since we don't have any pigs to use afterwards. If we have k pigs alive(0 < k <= n), we can use these pigs to detect at most dp[k][t-1] buckets. With some knowledge of permutation and combination, the number of cases we can have k pigs alive after one test is C(n, k) (when k == 0, it also holds true). So our state transition equation is

    dp[n][t] = 
    C(n,0)+C(n,1)dp[1][t-1]+...+C(n,k)dp[k][t-1]+...+C(n,n)dp[n][t-1], where 0 <= k <= n, t >= 2
    

    Thus

    dp[n][2] =  C(n,0)+C(n,1)dp[1][1]+...+C(n,k)dp[k][1]+...+C(n,n)dp[n][1]= 
    C(n,0)+C(n,1)2^1+...+C(n,k)2^k+...+C(n,n)2^n=3^n
    dp[n][3] =  C(n,0)+C(n,1)dp[1][2]+...+C(n,k)dp[k][2]+...+C(n,n)dp[n][2]= 
    C(n,0)+C(n,1)3^1+...+C(n,k)3^k+...+C(n,n)3^n=4^n
    ...
    

    A concise mathematical formula is generated!

    dp[n][t] = (t+1)^n, for all n >= 1 and t >= 1.
    

    Come back to our origin problem, if we can use minimum n pigs to detect N buckets with T tests, n should be

    ceil(log_(t+1)(N))
    == ceil((log(N)/log(t+1))
    

    Ceil is rounding above. Here I give a illustration of dp[2][2] == (2+1)^2 == 9 as an example below:

    We have 2 pigs at first and can carry out 2 tests. Firstly, we know 2 pigs can form 4 states of "alive"(0) or "died"(1), including 00, 01, 10, 11, each one is relative to a subproblem of dynamic programming. If after one test, two pigs both die, we can only handle one bucket in this case. However, if we have only one pig alive, we can handle dp[1][1](one pig left, with one chance of test left) namely 2 buckets, and there are actually two cases of only one pig left alive(2 == C(2, 1)). If both two are alive, we can handle dp[2][1] = 2^2=4 buckets totally. Thus, we separate 9 into 4 groups, and each one respectively contains 1, 2, 2 and 4 buckets, and design our first test. We feed our pig 0 with bucket 0, bucket 1 and bucket 3, and feed our pig 1 with bucket 0, bucket 2 and bucket 4. So you can see no matter which code is generated after one test, the problem is reduced to a subproblem we have already solved before.

    Based on the analysis above, I can explain the answer for input [1000, 15, 60], in which according to my definition, N == 1000 and T == 60/15=4, the minimum number of pigs we use should be ceil(log_(4+1)(1000))~=ceil(4.29)==5

    Finally, notice that if there is only 1 bucket, we can immediately detect this bucket containing poison, without any pigs or tests.


  • 0
    K

    +1 for nice break-down and explanation. I was moving threads to threads to understand the relation with 5-nary idea and then found this. Thanks !


  • 0

    I also came up with the same dp equation but it's not easy to get the formula until I filled up the matrix and found the numbers are so magic.


  • 1

    Great analysis for an up-vote! Actually, you could directly derive that

    • dp[n][t] = (t+1)^n

    from principle of multiplication without going though the recursive calculation. Note that during t tests, each pig has exactly t+1 possible different statuses: died at some Test#j (1<=j<=t) or still alive after all. So the maximum number of possible statuses of n pigs with t tests is straightforward dp[n][t] = (t+1)^n.

    I posted another analysis with math proof at: 1-line solution with detailed problem clarification & math proof


  • 0
    S

    Just adding a bit clarification on how to jump from a massive DP to a clean nice concise mathematical formula.
    Instead of looking at the result, let us explain the C(n,0) differently.

    from the start

    DP[2][2] = C(n,0) + C(n,1)DP[1][1] + C(n,2)DP[2][1]
    while
    (n+1)^2 = C(n,0) * n^0 * 1^2 +  + C(n,1) * n^1 * 1^1 + C(n,2) * n^2 * 1 ^ 0;
    

    We now could see that the C(n,0) means pick 0 n of (n + 1) and 2 1, C(n,1) means pick 1 n and 1 1.
    thus give us the formula DP[2][2] = DP[1][2] ^ 2 = (t+1) ^ 2 ..... (t+1)^n


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.