Search found 6 matches

by kelvin yang
Thu Apr 03, 2008 2:08 pm
Forum: Volume 114 (11400-11499)
Topic: 11446 - Where is the 'back' button?
Replies: 17
Views: 3373

Re: 11446 - Where is the 'back' button?

I'll talk about my method here. Hope it would be of help. -- spoiler -- /* those who wish to solve the problem themselves might not want to read ahead */ First we can limit our choice of link to only some nodes - Only those that are leaves/roots had to be considered. This should be fairly easy to pr...
by kelvin yang
Wed Apr 02, 2008 8:11 pm
Forum: Volume 114 (11400-11499)
Topic: 11446 - Where is the 'back' button?
Replies: 17
Views: 3373

Re: 11446 - Where is the 'back' button?

Yes, it should be 2. and the output of my program is 2 for the testcase above. I think maybe you forget to search on the root? dunno.. oh, and the answer to the question.. A more general question, for P=2 and L=2, and if we have edge (0,0) and (0,1). Is the solution 0, since you can never leave vert...
by kelvin yang
Tue Apr 01, 2008 4:09 am
Forum: Volume 114 (11400-11499)
Topic: 11446 - Where is the 'back' button?
Replies: 17
Views: 3373

Re: 11446 - Where is the 'back' button?

No...... I do understand your algorithm. Sorry if I was too implicit. What I meant is that for those nodes in the cycles, they don't necessary need additional links even if they are roots/leaves. I already tried to emphasize that point and I think you should try reading the constraints more carefully.
by kelvin yang
Mon Mar 31, 2008 10:34 am
Forum: Volume 114 (11400-11499)
Topic: 11446 - Where is the 'back' button?
Replies: 17
Views: 3373

Mind that while you contract your graph into an DAG, you contracted the cycles into single vertices.
and if the contracted vertices happen to be the leaf/root of your DAG, you might requre less edges added than max(c1, c2).
(since the nodes in the cycle are actually already linked to itselfs)
by kelvin yang
Mon Mar 31, 2008 6:27 am
Forum: Volume 114 (11400-11499)
Topic: 11446 - Where is the 'back' button?
Replies: 17
Views: 3373

The algorithm you described is not exactly right for this problem. In this problem the requirement is: "every node can click one or more links and then return to itself" so there are actually two requirements: 1) by clicking one or more links 2) return to the node itself And the intention of your al...
by kelvin yang
Fri Feb 01, 2008 5:00 pm
Forum: Volume 6 (600-699)
Topic: 649 - You Who?
Replies: 4
Views: 2806

649 - You Who?

649 You who? I was trying to understand this problem but seemed to have some difficulties. My understanding of the problem is as below: Given a graph G, divide its vertices into two groups such that 1) the number of vertices in two group differ by at most 1 2) the maximum number of not-acquainted cl...

Go to advanced search