Brute force solutions normally don't work for large input. That's why its necessary to think of a good algorithm.
You will notice that if it is possible to split the candies and make Patrick happy in any of the combinations, then all those combinations will satisfy Patrick. It will never be the case that some of the combinations satisfy Patrick and some don't. So, we just had to keep track of the best combination which is to give the smallest candy to Patrick and rest of the candies to Sean. If the candy pile were allowed to be empty, then the best solution would always be to give all candies to Sean. On 8 May 2011 12:11, anilsoni85 <[email protected]> wrote: > While solving the CandySplitting problem yesterday i was thinking the > problem can be solve in folllowing steps > > 1. Read the candies value and put them in an array of int. > 2. Create combination of different way sean can split the candies. > Like for 2nd sample example possible combination could be > Sean Patrick Sean Sum of his own Candies Patrick's > XOR of Sean & Patrick candies > 3 5,6 > 3 3 3 > 5 3,6 > 5 5 5 > 6 3,5 > 6 6 6 > 3,5 6 > 8 6 6 > 3,6 5 > 9 5 5 > 5,6 3 > 11 3 3 > > Sean maximum Sum of candies where Patrick & Sean candies XOR equal is > 11 so the solution is 11 > > But in solutions i did not found anyone's solution using this > approch...and now i am having doubt n how the problem can be solved > without combinations. > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > > -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
