For the small case where there are only two customers, the greedy strategy you should be using is to try to wear down the largest stacks of tickets on the same seat first. In that case, after picking any two tickets for different seats in your ride 1, you will pick one of the seat 3 tickets in ride 2 before you take the tickets for seats 1 and 2 again. You only ever have to promote when there are more tickets for the same seat than the largest number of tickets bought by one customer. If that occurs for seat #1, you have to do more rides instead, since you can't promote.
The large case is remarkably similar. Here, you first figure the number of rides as the maximum of: The largest number of tickets bought by one customer The number of tickets purchased for seat 1 Half (rounded up) the total tickets purchased for seats 1 and 2 (if seat 2 has more tickets purchased than seat 1, this is the number of rides you need after promotions) A third (rounded up) of the tickets purchased for seats 1-3 etc. Then you only promote where there are more tickets purchased for one seat than the number of rides. Because of the half, a third, etc. conditions on the number of rides, you are guaranteed to find places to promote those tickets to without overflowing the limit on some other seat. The trick then is scheduling all the rides, when you might have, say, five people with five tickets each which among them include five tickets each for seats 1 through 5. If everybody has one ticket for each seat, any Latin square arrangement will do. I spent a little while trying to find a case where this COULDN'T be completed, and decided (correctly) it wasn't possible, though the algorithm is difficult to see. But the problem doesn't require us to produce a schedule, so the above is all you need for a large solution. On Sun, May 14, 2017 at 12:10 AM, DSL <[email protected]> wrote: > Hi, > > I tried the problem for practice and got correct answers to all but one of > the small input test cases using a greedy strategy. > > B-small-practice.in Case #38 > > Input: > 3 2 6 > 1 2 > 1 1 > 3 1 > 2 2 > 2 1 > 3 2 > > Output (I got: 3 1) > 3 0 > > My code is at https://ideone.com/Q6rnSx > > Unnecessary promotion occurs due to the seat assignment: > Ride 1 = Seat 1: Customer 1 + Seat 2: Customer 2 > Ride 2 = Seat 1: Customer 2 + Seat 2: Customer 1 > Ride 3 = Seat 3: Customer 1 + Seat 3: Customer 2 (one of the seats need to > be promoted) > > Can avoid this with the following seat assignment: > Ride 1 = Seat 1: Customer 1 + Seat 2: Customer 2 > Ride 2 = Seat 1: Customer 2 + Seat 2: Customer 3 > Ride 3 = Seat 1: Customer 3 + Seat 2: Customer 1 > > I would appreciate either a simple fix for my greedy solution if possible > or a different working greedy solution. > > Thanks > > -- > 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/5ef8143a-9704-49e0-ad20-5f6b490b7a18%40googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- 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/CAMAzhzgpo8Lg8JJ9bwkHL4sHb0LRDjAZJH3dD_5OHcrA3wR%3D%3Dw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
