Poor Pigs, Editorial Logic Explained Super In-Depth!! (Python3)
Preface\n\nSo you may have read the editorial and got the general gist of problem, but still don\'t understand it fully. This is my attempt at explaining it and
# Preface\n\nSo you may have read the editorial and got the general gist of problem, but still don\'t understand it fully. This is my attempt at explaining it and how I derived the solution.\n\n# Explanation\n\nIn the editorial, it says that in 1 trial n pigs can test $$2^n$$ buckets.\n\nThis is an important part of the logic so let\'s first try to understand that. \n\nLet\'s first look at the basic case, with 2 buckets and 1 pig: \n-- The pig eat bucket 1. \nIf it dies, bucket 1 is poisonous. \nIf it doesn\'t die, bucket 2 is poisonous.\n\nNow let\'s look at 4 buckets 2 pig.\n-- Pig 1 eat bucket 1 and 2.\n-- Pig 2 eat bucket 2 and 3.\nIf only pig 1 dies, bucket 1 is poisonous.\nIf only pig 2 dies, bucket 3 is poisonous.\nIf pig 1 and pig 2 die, bucket 2 is poisonous.\nIf no pigs die, bucket 4 is poisonous.\n\nSo you can see we are leveraging pigs eating overlapping buckets to determine whether buckets are poisonous. And we are using combinations of these overlaps to determine which bucket is poisonous. If a certain combination of deaths happen, we know a certain bucket is poisonous. \n\nAdditionally, note that we always leave one bucket uneaten. That is the case where all pigs stay alive, meaning that uneaten bucket is poisonous. We can also have 1 bucket where all pigs eat from. If all pigs die, that bucket is poisonous.\n\nNow let\'s look at a more complex example, 8 buckets 3 pigs.\n-- Pig 1 eat bucket 1, 2, 3, 7\n-- Pig 2 eat bucket 2, 4, 5, 7\n-- Pig 3 eat bucket 3, 5, 6, 7\nIf only pig 1 dies, bucket 1 is poisonous.\nIf only pig 2 dies, bucket 4 is poisonous.\nIf only pig 3 dies, bucket 6 is poisonous.\nIf pig 1 and 2 dies, bucket 2 is poisonous.\nIf pig 1 and 3 dies, bucket 3 is poisonous.\nIf pig 2 and 3 dies, bucket 5 is poisonous.\nIf all pigs die, bucket 7 is poisonous.\nIf no pigs die, bucket 8 is poisonous.\n\nSo you see, again we are using unique combinations of pigs dying to determine which bucket is poisonous! So let\'s flip it around and think from the buckets perspective/ POV. To test each bucket, it can be assigned to a unique combination of pig deaths. \n\nHow many different combinations of pig deaths can we derive from n pigs? \n\nWe can determine this using two ways:\n-- We can do combinations where only 1 pig dies, n choose 1. Combinations where 2 pigs die, n choose 2. All the way to n choose n. So the total number of combinations is n choose  1 + n choose 2 + .... + n choose n = 2^n. You can search up the proof by induction or just memorize this.\n-- The other more intuitive way, in my opinion, is you can see that in 1 trial each pig has 2 states, alive or dead. So total number of combinations of alive/dead states for n pigs is $$2^n$$. Since each pig adds a degree of 2 to the number of total combinations. So number of combinations with $$n$$ pigs and $$s$$ states is $$s^n$$.\n\nSo now, it makes sense that with 1 trial, n pigs can test $$2^n$$ buckets.\n\nNow to solve the real problem, with the hard part out of the way.\n\nIn the real problem, there can be multiple trials. In total, we have (total time // time to die) trials that we can fit inside of the allowed time. So to determine the total number of states per each pig, we see that it is (total time // time to die) + 1. This is because each pig could die after trial 1, after trial 2, after trail 3.... all the way to the last trial. So thats t trials. The +1 is for the state where the pig never dies. \n\nSo assign a variable states to (tt // td) + 1. Again, we want to determine how many combinations we can derive with n pigs and states states. Each unique combination can be assigned to a bucket! Using the same logic as above , we can see that n pigs with `states` states can test $$states^n$$ buckets.\n\nSo all we have to do is solve the equation, states^n = buckets. And find the minimum n that makes this equation valid! We can simplify by taking the log of both sides and pulling n out. Finally, we get $$n = log(buckets) / log(states)$$. And we take the `math.ceil` of that since we are looking for the minimum needed. \n\nHope this explanation helped someone!\n\n\n\n# Complexity\n- Time complexity: O (1)\n\n- Space complexity: O (1)\n\n# Code\n```\nclass Solution:\n    def poorPigs(self, n, td, tt):\n        # n pigs with t trials can test (t + 1)^n buckets\n        # # states = t + 1, dead after each trial + alive \n        # find minimum number of pigs to satisfy (t + 1) ^ n = buckets\n        # can binary search or instantly solve using math\n        states = tt // td + 1\n        return math.ceil(math.log2(n) / math.log2(states))\n\n        \n```
['Math', 'Combinatorics', 'Python3']