Page 2 of 2
Posted: Tue Sep 23, 2003 2:30 pm
by Farid Ahmadov
Hello.
kmhasan you said that answer is not always equal to the number of missions. Why?
For example (second sample test case) :
3
Meet_The_Boss 3
Rob_The_Cop 6
A_Petty_Thief 5
1-st I play (3, 5);
I restart and play (6);
As you can see there are three missions that are completed.
Maybe I am wrong. Explain it please.
Thank you.
Posted: Tue Sep 23, 2003 7:50 pm
by kmhasan
quite simple. you always have to play K (2 in this case) missions.
Posted: Sun Sep 05, 2004 4:56 pm
by ..
kmhasan wrote:Construct the network as follows:
For each mission make two vertices. From the 1st vertex connect using a unit edge to the 2nd vertex of the missions that appear before this mission and are easier than the one at hand. Then connect the 2nd vertex of the current mission to the 1st vertex of the current mission. From the source connect to the 2nd vertex of the missions that can be chosen as the K th mission in some LIS. And from the 1st missions of the LISs connect to the sink. Now run a max flow from source to sink.
The answer would be K*max-flow.
Hi Kmhasan,
I don't understand the setence "can be chosen as the K th mission in some LIS", could you please give me an example of the constructed network? Thanks!
Posted: Sun Sep 05, 2004 6:12 pm
by kmhasan
I think my post lacked an illustration. If the following network fails to explain the idea, please let me know. I'd try to elaborate some more.
We can construct this network for the sequence:
As you'd see, the length of the LIS is 3, and there is at most two such LIS that are disjoint. The flow shown in
red highlights them.
Posted: Sun Sep 05, 2004 6:26 pm
by ..
Thanks for your quick response and great picture
But I still have one question, is it that if the length of LIS = 4,
your network will have 2 layers of missions between the start layer and end layer? If no, how can you guarantee that every augmenting path will have length of LIS?
Posted: Sun Sep 05, 2004 7:16 pm
by kmhasan
That actually follows from our construction of the network. Our network is basically a multistage graph that you form for finding all possible LISs of a sequence. Before I start to make it more confusing, let me clarify through a picture:
We construct this multistage graph for the sequece:
Code: Select all
A = <6, 5, 2, 15, 7, 4, 10, 9, 8, 16, 14, 12, 11>
Now, we would only connect the source,
s to the nodes of the final stage. And the sink,
t will only be connected to the nodes of the first stage. For any augmenting path we know that it has to go from the source to the sink. Therefore, it is bound to go through the all the stages -- which actually ensures that we have a path length of LIS for each and every augmenting path. Agreed?
Posted: Mon Sep 06, 2004 6:39 pm
by ..
Agree
So, before constructing the network, you have to use the LIS algorithm
to decide putting each mission at which stage, right?
Posted: Mon Sep 06, 2004 7:18 pm
by kmhasan
Right.
Posted: Wed Aug 23, 2006 4:01 am
by Khaled_912
kmhasan wrote:
From the 1st vertex connect using a unit edge to the 2nd vertex of the missions that appear before this mission and are easier than the one at hand.
Well, this seems not to be correct. Let h
be the length of the maximum sequence of missions ending with 'i'. In this case, 2nd vertex of mission 'j' is connected to the first vertex of mission 'i' iff h = h[j] + 1 (which also implies that difficulty > difficulty[j]).