I had insight on my walk home from work. I think this is a DP problem, and you solve num(subset, K), which is the number of ways of labelling subset of vertices with numbers 1 up to K.
The recurrence is num(subset, K) = sum num(subset1, K-1), the sum being over all subsets subset1 of subset such that if y is in subset1, x is in subset and x<=y then x is in subset1. Time O(11*3^14) which should be fast enough. On 21 Jan 2013, at 07:37, Hussein El-Sayed <[email protected]> wrote: > Paul, > > > Thanks for your clear explanation i think it's very helpful, first i thought > it could be solved using LP, but i couldn't transform it to an optimization > problem as its not so. Then i made a directed graph trying to recursively > build the solution, but i found it wrong after that. Also a brute force > solution won't survive as you know. Now i will go through your explanation > then solving it. > > Thanks, > Hussein > > On Mon, Jan 21, 2013 at 12:27 AM, Paul Smith <[email protected]> wrote: > Have you made any effort to solve it yourself? How are you doing? Where > specifically are you stuck? > > Paul Smith > > [email protected] > > > On Sun, Jan 20, 2013 at 8:30 PM, Hussein El-Sayed <[email protected]> > wrote: > The whole problem, i need to know how can i solve this problem. > > > On Sun, Jan 20, 2013 at 6:28 PM, paulmcq <[email protected]> wrote: > I would assume that means "Report the answer modulo 1007" from someone for > whom English is a second language. > > More importantly, are you objecting to the wording or to the content of the > problem? > > > On Saturday, January 19, 2013 10:38:06 AM UTC-6, Luke wrote: > "Module the answer by 1007" is a new usage to me. > > I don't like it. > > > > On 19 Jan 2013, at 16:31, Hussein El-Sayed <[email protected]> wrote: > >> Its is name is Requirement .. you can view it from this url. >> >> >> On Sat, Jan 19, 2013 at 6:20 PM, Amir Hossein Sharifzadeh >> <[email protected]> wrote: >> Which problem? >> >> On Sat, Jan 19, 2013 at 8:57 AM, Hussein El-Sayed <[email protected]> wrote: >> Hello, >> >> Can you please help me solving this problem? >> >> Thanks, >> Hussein >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" 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 https://groups.google.com/groups/opt_out. >> >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" 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 https://groups.google.com/groups/opt_out. >> >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" 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 https://groups.google.com/groups/opt_out. >> >> > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msg/google-code/-/40y_zNXxDN4J. > > 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 post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
