Can someone tell me how to solve this(Lazy Bartender) problem ? asked 07 Apr, 15:39

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 NPHard. answered 10 Apr, 22:41
So what would be the expected time complexity of Brute Force?
(11 Apr, 13:21)
O(C*2^N). The other solution has complexity O(N*2^C).
(11 Apr, 16:00)
But in original question $N$ and $C$ was given to me as, $1 < N < 1000$ $1 < C < 10000$
(11 Apr, 23:03)
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.
(11 Apr, 23:25)
You can see the original question here(https://goo.gl/Mgnqc4)
(11 Apr, 23:29)
I don't think it can be solved.
(11 Apr, 23:48)
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?
(12 Apr, 11:13)
1
What do you mean by ascending order ? ascending based on what ?
(13 Apr, 22:39)
showing 5 of 8
show all
