Hi, What you describe is called a greedy algorithm: an algorithm where you make decisions based on local information, without revisiting those decisions later. In many cases, and here too, this leads to globally suboptimal solutions. If you want to see the concrete examples where your approach fails, I suggest you download a correct solution from the leaderboard, run it on the testdata, and compare its output with yours.
For this problem, there are two correct approaches. 1. Brute-force the set of malted flavors. Since there are at most 10 flavors, there are only 2^10 = 1024 sets to try (you can conveniently use bitmasks here). This solution is pretty lame, but I'd recommend it during a contest because it's easy to code it up quickly and it gets the job done. 2. For a smarter solution (that also works with many more flavors than 10), observe that if all customers like at least one unmalted flavor, then we don't have to prepare any malted batches at all. However, if some customer wants only malted flavors, then that must be the ONLY flavor they like, since the problem statement guarantees that "each customer will like at most one malted flavor". In that case, we must make that flavor malted, and remove the unmalted version from the options of the other clients, since we cannot make a malted and unmalted batch of the same flavor (from the problem statement: "There is exactly one batch for each flavor of milkshake, and it is either malted or unmalted.") It may now be the case that another client only likes a malted flavor (possibly because we've just eliminated the unmalted flavor they liked). Then we must make that flavor malted, too, and again remove the unmalted version as an option for everyone else. We can continue like this until one of two things happens: either all remaining customers like at least one unmalted flavor, or one of the customers doesn't like any of the remaining possible flavors. In the first case, we've found an optimal solution. In the second case, no solution exists. Note that the algorithm I described above is also somewhat greedy: as soon as a customer is found with only one, malted preference, we decide to make that flavor malted, and never revisit that decision. In this case, that's correct, because in that situation our decision is forced. That's also how we know the constructed solution is optional: we only made a flavor malted when we were absolutely certain we had to do it. In general, the kind of greedy solutions to watch out for are those where you prematurely fix your answer, even though you have multiple possibilities to choose from. In your example, you order the preference lists by length (which is typically a good heuristic) but if the shortest preference list contains more than one option, then you can't make an optimal choice without considering the other customer's preferences. That's why your approach didn't work. - Maks. On Thursday, November 26, 2015 at 6:06:05 PM UTC+1, Fork Security wrote: > Hello, > > I'm trying solve the Milkshake problem[0] from Round 1A of the CodeJam, 2008. > > I have a list of costumers' preferences and I need to produce a set of batches > of milkshakes, specifying for each batch if I have to order them malted or > unmalted -- to satisfy all the clients. > > Moreover, I have to minimize the number of malted batches. > > My idea was to build a list of lists, where each list represents the set of > preferences for a costumer. > > preferences = [ > [(1,1), (2, 0)], ## That is, flavour1 malted, flavour2 unmalted > ... > ] > > Then I sort the entire list of preferences by the length of each set of > preferences, then sorted again for each set of preferences, > putting the unmalted flavours first, then the malted one. > > preferences = [ > [(1,1)], > [(1,0), (3,0)], > [(5,0), (1,1), (3,1)], > ... > ] > > By satisfying the costumers, starting from the most "choosey", trying their > "unmalted preferences" first, I thought I was supposed to pick (whenever > possible) the batches that satisfied each costumer, keeping the number of > malted batches the lowest possibile. > > Why I'm wrong? > > The code that I'm using to generate the solution is here[1]. > > Thank you in advance! > > [0], https://code.google.com/codejam/contest/32016/dashboard#s=p1 > [1], https://gist.github.com/giuscri/50046796166ef9fcb0ae -- 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 [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/083a2d11-d35c-4e10-bc64-afbe6f2cdc9f%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
