C# Explained Single Line [45ms]


  • 2
    L
    return buckets == 1 ? 0 : (int)Math.Ceiling(Math.Log(buckets, (minutesToTest/minutesToDie) + 1));
    

    minutesToTest/minutesToDie determines the number of trials that can take place before the time limit is exceeded (using integer division).

    Each trial will result in 1 state change: death at t, aside from the final trail, which will also result in the implicit result of a living pig. There are minutesToTest/minutesToDie + 1 states overall. Call the number of states x

    We can represent each bucket in base x. We can use the log function to know how many digits a number will have in base x: ceil(log_x(buckets))

    Each pig can represent x states, so we need one pig per digit, leading to the code above.

    Note that an invalid result will be returned if minutesToDie<minutesToTest, as there is no valid solution in this case unless there is a single bucket.

    Small worked example:

    25, 15, 60. Poisoned bucket: 13

    base = 60/15 + 1 = 5
    number of digits = ceil(log_5(25)) = 2

    t=0
    Pig_0 = [0,5,10,15,20]
    Pig_1 = [0,1,2,3,4]
    t=1
    Pig_0 = [1,6,11,16,21]
    Pig_1 = [5,6,7,8,9]
    t=2
    Pig_0 = [2,7,12,17,22]
    Pig_1 = [10,11,12,13,14] - dead. The number begins with 2.
    t=3
    Pig_0 = [3,8,13,18,23] - dead, the number ends in 3.

    Poisoned bucket (13 in base 5) = 23 (2*5+3)
    Therefore the number is 23, or 13 in decimal.


  • 0
    B

    in t=0, pig_0=[0,5,10,15,20] do you mean this pig will be fed with 5 buckets at t=0?


  • 1
    K

    @lano1 At time t = 1, why Pig_0 is again trying bucket 1 as Pig_1 has already tried it at t = 0?


  • 1
    L

    @bargitta said in C# Explained Single Line [45ms]:

    in t=0, pig_0=[0,5,10,15,20] do you mean this pig will be fed with 5 buckets at t=0?

    Yes, both pigs will be fed with 5 buckets on each round (until death).

    @kaidul said in C# Explained Single Line [45ms]:

    @lano1 At time t = 1, why Pig_0 is again trying bucket 1 as Pig_1 has already tried it at t = 0?

    You're completely correct.

    Quite honestly, because I felt it removed unnecessary decisions when explaining the problem and makes the pattern more easy to see. We're not trying to optimise for "number of drinks", only for "number of pigs used".

    As an aside, the example is used to explain why the maths works. The computer would not need to perform any of the time steps listed


Log in to reply
 

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