Can someone tell me how to solve this(Lazy Bartender) problem ?
3 Likes
Depends on constraints. You can solve it easily if either N or C is small. If N is small, then you can just brute force. If ‘C’ is small, you can use bitmask dp, DP[i][mask] = minimum number of drinks from the first ‘i’ drinks for all customers represented by ‘mask’. I don’t think there are better solutions because this problem seems to be similar to the Set Cover problem, which is NP-Hard.
1 Like
So what would be the expected time complexity of Brute Force?
O(C*2^N). The other solution has complexity O(N*2^C).
But in original question N and C was given to me as,
1 < N < 1000
1 < C < 10000
Take a look at this : https://en.wikipedia.org/wiki/Set_cover_problem , its easy to see that every instance of this problem can be reduced to Lazy Bartender. So, I don’t think there is a polynomial time solution.
I don’t think it can be solved.
Is that not possible to pick the bars greedy, I mean first sort all the cocktails in ascending order and then pick one by one?
What do you mean by ascending order ? ascending based on what ?
1 Like
You can do this…
Use hashing or a frequency array for drinks (n1,n2…)
Then count the frequency of all the drinks that can be supplied i.e.lets say
customer 1 =n1,n2,n3
customer 2 =n1,n4,n3
customer 3 =n1
Now frequency array will be 3 1 2 1 for all the drinks respectively. Now sort the frequency array and provide drinks to the customer in decreasing order of frequency. Continue this process till all the customers are satisfied.
So the time complexity will become O(c*n +nlogn).
This has no guarantees on optimality. A simple counterexample, consider c1 = {n1,n2}, c2 = {n1,n2}, c3 = {n3}. Your algo serves using 3 when the optimal is 2. In this case there are duplicates, but it’s easy to construct harder cases.
Ohh yeah!!! You are right. But i got a slight correction. We would also have to reduce frequency of all the drinks of that customer whom we are supplying a drink.This complexity remains cn(overall for all customers) .After that we have to sort it again. So at most we have to sort it c times. So net complexity is O(cn +cnlogn)=O(cnlogn).
But i am not sure that it will run in the given time constraints. Please check!! But i think this will give an optimal solution. If anyone can improve this please comment!!!
c1 = {n1,n3}, c2 = {n1,n2}, c3 = {n1,n4}, c4 = {n4,n5}, c5 = {n3,n6}, c6 = {n2,n7}. The highest frequency doesn’t always give the best solution. In the worst case you would have to check every subsequence in your sorted frequency array.
As @hemanth_1 mentioned in the comments in to their answer, set cover is reducible to lazy bartender, and set cover is NP-hard. So unless P=NP there is no polynomial algorithm for this problem. So either P=NP or your algorithm does not give the optimal answer. It’s very much the latter.
1 Like