"At most one of the types a customer likes will be a "malted" flavor." The first consumer is not a valid one. -- Ernest Galbrun
On Fri, Feb 8, 2013 at 2:09 AM, jucaranlu <jucara...@gmail.com> wrote: > Hi guys, I've been trying to solve > milkshakes<http://code.google.com/codejam/contest/dashboard?c=32016#s=p1&a=1>problem. > I tried to implement the steps of the Contest > Solution<http://code.google.com/codejam/contest/dashboard?c=32016#s=a&a=1> but > I've found them incorrect. The steps are the following: > > Start with every flavor unmalted and consider the customers one by one. > If there is an unsatisfied customer who only likes unmalted flavors, and > all those flavors have been made malted, then no solution is possible. > If there is an unsatisfied customer who has one favorite malted flavor, > then we must make that flavor malted. We do this, then go back to step 2. > If there are no unsatisfied customers, then we already have a valid > solution and can leave the remaining flavors unmalted. > But, for example, If you have the next two customers: > > - 2 1 1 2 1 (That customer likes 2 flavors; type 1 malted and type 2 > malted) > - 1 1 0 (That customers likes 1 flavor; type-1 unmalted) > > The steps will conclude it's an Impossible problem (First, type 1=malted, > so you cannot satisfy the second customer) but it's not, 0 1 (type 1 > unmalted, type 2 malted) is a correct answer. > > It can be reduced to a simple SAT problem. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to google-code+unsubscr...@googlegroups.com. > To post to this group, send email to google-code@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msg/google-code/-/asCSoMJ8xT8J. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
