1-line solution with detailed problem clarification & math proof (please read if you really want to know what this problem means)


  • 3

    Clarifications:
    I definitely think the description in this problem needs to be clarified as I initially read it. After reading some posts, I finally got exactly what it expected and restricted in this problem of the storytelling style (which is likely to introduce ambiguity).

    Here are the two key points that have to be clarified if you really want to work on this "poorly" defined problem:

    • A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time (!). I guess this is the really bizarre assumption hidden behind this story. And I finally got this point after reading some posts.
    • After a pig has instantly finished drinking buckets, there has to be a "cool down" time of minutesToDie minutes. During this time, only observation is allowed and no feedings at all. Actually, this is a derived hint from the problem instead of an assumption. Because after feeding on poison bucket, it is stated that a pig will die within minutesToDie minutes instead of exact minutes. This means that if you feed a pig more than once in a time frame less that minutesToDie minutes, there is no way to tell which feeding contains poison if the pig happens to die eventually

    With the two key points above, I think the problem picked a "bad" story. Instead, it could be re-translated into a better story such as:

    • Given N sources with exactly one of them sending bad signal. You are given x receivers to detect which source is sending bad signal. A receiver can be configured to pick up signals from any number of specified sources. The bad signal will permanently damage a receiver within minutesToDie minutes after received. Find the minimum x if given minutesToTest minutes to test.

    Solution:

        int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
          return ceil(log(buckets)/log(minutesToTest/minutesToDie+1));  // log_{T+1}(N)
        }
    

    Proof: For given minutesToDie and minutesToTest, with the clarification above, the only thing that matters here is the number of tests allowed T = (int)(minutesToTest/minutesToDie) because of the "cool down" restriction. Then the problem is translated equivalently to:

    • How many states can we generate with x pigs and T tests to cover N scenarios?

    The number of states is exactly (T+1)^x and here is why. For each pig during T tests, it has exactly T+1 states: dies at some test#i (1<=i<=T) or still alive eventually. For x pigs, obviously the maximum possible number of states we could have is (T+1)^x since each pig's well-being solely depends on whether it ever fed on poison bucket and nothing to do with other pigs. So all we need to do is to

    • find minimum x such that (T+1)^x >= N, which means x = ceil(logN/log(T+1)).

    Now we have the optimal candidate, but can we actually implement a feeding solution to achieve that optimum solution? Sure, here it is:

    1. Label buckets as a (T+1)-based number represented as x-dimensional vector v = (v[1], v[2], ...,v[x]) consecutively ascending from (0,0,...0). (each 0<=v[j]<=T)
    2. For each Test#i (1<=i<=T), if all pigs are dead by now, process is finished. Otherwise, for each pigj alive, feed it on all buckets with v[j] = i simultaneously, and record its death time D[j] = i if it dies after this test.
    3. Default D[j] = 0 if pigj is still alive after all T tests.

    Then we claim that: bucket with label (D[1],D[2],...,D[x]) must be the poison one.

    Because for each pigj, by design of Step 2, it is guaranteed to be alive before feeding on bucket (D[1],D[2],...,D[x]) and all those pigs which have ever fed on this bucket died right after that test.


  • 0
    H

    +1 for your clarifications.

    You touched on this, but I would also like to see the problem specifically state that any given bucket can be sampled an infinite number of times (by an unlimited number of pigs). At first, I was thinking that only one sample can be taken from a given bucket (and after that point, it was considered "consumed"). Found out I was wrong after running my code.


Log in to reply
 

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