Claim this problem with the Venn diagram


  • 0
    W

    Suppose we have 2 pigs, 15 mins to die, 60 mins to test.

    Then we can test 4 rounds.

    But what is the maximum groups we can test in a round??

    Remember the Venn diagram, we can have 4 possible situations.
    That is, we can test 4 groups with this 2 pigs, we give the example in the following:

    A        B        C        D
            pig1    pig1
                    pig2      pig2
    

    we can let pig1 drink the water from group B and group C,
    and pig2 drink the water from group C and group D.

    With this property, we can test 4^4 = 64 buckets in the end.

    How about we have x pigs and d mins to die, t mins to test??
    We can test 2^x groups in a round, and we have $ r = int(t / d) $ rounds.

    So, we can test at most (2^x)^r buckets.

    p.s. I suppose a pig can drink lots of water, lol.


Log in to reply
 

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