problem setters solution is just a greedy approach as ingredients are represented using integer values ranging less than 500 so he is making a hash map of ingredients which store the frequency of the ingredient, whenever the count for some ingredient goes odd, he makes a cut
On Wed, Nov 2, 2011 at 7:25 PM, shady <[email protected]> wrote: > actually i wanted to know what approach the problem setter is using, since > this problem is NP hard so optimal solution is not always possible. > > On Wed, Nov 2, 2011 at 7:20 PM, sunny agrawal <[email protected]> > wrote: >> >> This is a challenge problem >> and you don't need to find a best solution for each case, optimal >> solutions are acceptable if they satisfy the problem constraints >> for this problem the constraint is cuts should be made so that both >> are able to eat equal no of each available ingredient >> >> Examples: >> Lets take the last testcase >> >> 8 >> 500 400 2 400 500 500 2 500 >> >> in this testcase as you can see if cuts are made like >> 500 400 2 | 400 | 500 | 500 2 500 >> Jack | Jill | Jack| Jill >> so using only 3 cuts we can divide this so that both get same and >> equal no of each type of available ingredients >> >> Scoring for this problem is done depending upon how many cuts your >> program outputs relative to others >> >> On Wed, Nov 2, 2011 at 6:17 PM, shady <[email protected]> wrote: >> > >> > Hi, >> > Can anyone what is being done here ? This is a >> > question http://www.codechef.com/JAN11/problems/SPLIT/ from Codechef. I >> > have >> > read the editorials, but that didn't help. >> > http://www.codechef.com/download/Solutions/2011/January/Setter/Split.cpp >> > >> > -- >> > You received this message because you are subscribed to the Google >> > Groups "Algorithm Geeks" 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/algogeeks?hl=en. >> >> >> >> -- >> Sunny Aggrawal >> B.Tech. V year,CSI >> Indian Institute Of Technology,Roorkee >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" 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/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" 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/algogeeks?hl=en. > -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" 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/algogeeks?hl=en.
