Major flaw in current algorithm [FIXED]


  • 18
    L

    EDIT: This issue has now been fixed.
    I personally feel that @ifyouseewendy's equivalent approach: [https://discuss.leetcode.com/topic/67482/solution-with-detailed-explanation] is significantly better explained than mine and would recommend that you read/upvote this to understand the problem.

    --

    The basic case (and presumably a significant amount more) are incorrect as more efficient solutions can be generated if we do not use base 2.

    Assume for now we have: [buckets, 15, 60]

    Per pig, we have 5 states that we can detect: death on 15, 30, 45, 60, or life.

    Assume for the moment we have 5 buckets and one pig with the above timings.

    Represent each bucket as an integer in base 5 (0-indexed).

    Pig drinks from bucket 0 at 0 minutes, bucket 1 at time 15 etc...
    If the pig is still alive, by elimination, we know that bucket 4 would be poisonous.
    This should be trivial to see.

    We now increase the number of buckets to 25, we have ceil(log_5(25)) = 2 pigs

    Bucket 25 is labelled 44, bucket 1 is labelled 00.
    At time t, have the first pig drink from the buckets where the first digit is t, have the second pig drink when the second digit is t. As each pig represents a single digit in base 5, and 25 consists of two base 5 digits, two pigs are necessary. We can determine the value of each digit based on the time of death of each pig. An overlap of the death of two pigs gives us the information of two digits, so nothing is lost.

    Example: 18 is poisonous (33 in base 5).

    On t=3, one pig is drinking [15,16,17,18,19] and the other is drinking [3,8,13,18,23]. We can see that if both die, the intersection of the sets yields 18.

    Given the default input: 1000, 15, 60

    The above yields the minimum number of pigs = ceil(log_5(1000)) = 5 pigs.

    The OJ currently returns 8 pigs, which is significantly higher.


  • 6
    I

    I think you are right!
    The code would look something like this:

    public class Solution {
        public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
            if (buckets--==1){
                return 0;
            }
            int base=minutesToTest/minutesToDie+1;
            int count=0;
            while (buckets>0){
                buckets/=base;
                count++;
            }
            return count;
        }
    }
    

  • 0
    Y

    @lano1 I'm with you, and would update the test cases.


  • 2
    L

    @inferee

    I believe it can be shortened to the following (assuming the values of minutesToTest and minutesToDie are valid

    public class Solution {
        public int PoorPigs(int buckets, int minutesToDie, int minutesToTest) 
            => buckets == 1 ? 0 : (int)Math.Ceiling(Math.Log(buckets, (minutesToTest/minutesToDie) + 1));
    }

  • 1
    Y

    @lano1 @inferee
    I updated the question with both solutions you provided. Thanks!


  • 0
    T

    How about (minutesToDie > minutesToTest)? In this case, base == 1, I think it should return (buckets - 1)


  • 0
    L

    @tju_xu said in Major flaw in current algorithm [FIXED]:

    How about (minutesToDie > minutesToTest)? In this case, base == 1, I think it should return (buckets - 1)

    I feel that there is no valid answer (unless buckets == 1) as you cannot complete 1 trial within the time limit.

    I'm happy to return an invalid value in this case, but it's a fair point which may want to be addressed in the question.


  • 1
    T

    Sorry, I didn't understand the problem correctly.


  • 0
    C

    Did you consider the pig died from your testing?
    I also got the answer 8.

    my formular is x(x-1)(x-2)(x-3) = 1000

    x is approx 7.23
    so x = 8


  • 0
    L

    @cookiecookie said in Major flaw in current algorithm [FIXED]:

    Did you consider the pig died from your testing?

    Yes,

    Each pig represents a place digit of the poisoned bucket (not necessarily represented in a decimal base). The time of death (or non-death) represents the value of that digit. You won't need more pigs as there is nothing more to measure.

    NB: We are be able to get away with less pigs in some situations, but the question asks for the number of pigs for any value of poisoned bucket, therefore we return the maximum value (worst case).

    I get the impression that you skimmed the original post, if that's not the case then can you let me know where you don't understand so I can elaborate further.

    Cheers :)


  • 0
    A

    In the case when number of attempts > 1, this is not considering the case that one pig died. In the second attempt you need to get one more pig to get the experiment going.


  • 0
    L

    @ankardip said in Major flaw in current algorithm [FIXED]:

    In the case when number of attempts > 1, this is not considering the case that one pig died. In the second attempt you need to get one more pig to get the experiment going.

    Can you point out the exact paragraph that you're referencing so I can explain better?


  • 0
    A

    @lano1 t = 0, pig1 -> buckets: {0, 1, 2, 3, 4}, pig2 -> buckets: {1, 6, 11, 16, 21}. What you point out is if both dies, we know bucket 1 is poison, and it is correct. But if pig1 dies, and pig2 survives, what next? You still need to continue t=1 case with 2 pigs. But pig1 is dead. So in total you need 3 pigs. Right?


  • 1
    L

    @ankardip said in Major flaw in current algorithm [FIXED]:

    @lano1 t = 0, pig1 -> buckets: {0, 1, 2, 3, 4}, pig2 -> buckets: {1, 6, 11, 16, 21}. What you point out is if both dies, we know bucket 1 is poison, and it is correct. But if pig1 dies, and pig2 survives, what next? You still need to continue t=1 case with 2 pigs. But pig1 is dead. So in total you need 3 pigs. Right?

    Note: You started pig2 at 1, whereas this should have been at 0, not that it makes a difference.

    From your example (modified to be 0-based):

    At t=1, we know that the first digit of the number is 0, therefore the potential poisoned buckets are [1,2,3,4]. We have 1 pig and 4 states, with 3 attempts left.
    pig2 = [1,6,11,16,21]
    pig2 = [2,7,12,17,22]
    pig2 = [3,8,13,18,23]

    If the pig is not dead, we know that 4 is the non-poisoned bucket.


  • 1
    A

    @lano1 Cool! Makes sense! Thanks!


  • 1
    E

    Generally speaking we can detect pig death on 16, 17, 18 ... minutes. And even on half of minutes. So I don't see why we couldn't use same pig to drink from new bucket say once a minute or more.


  • 0
    K

    @elvenmonk I think that would make a solid point in an interview. Thank you.


Log in to reply
 

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