10546 - The Eagle's Nest

Farid Ahmadov · Post by **Farid Ahmadov** » Tue Sep 23, 2003 2:30 pm

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.

kmhasan · Post by **kmhasan** » Tue Sep 23, 2003 7:50 pm

quite simple. you always have to play K (2 in this case) missions.

.. · Post by .. » Sun Sep 05, 2004 4:56 pm

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!

kmhasan · Post by **kmhasan** » Sun Sep 05, 2004 6:12 pm

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:

Code: Select all

A = <7,5,1,15,13,8,16,10,9>

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.

.. · Post by .. » Sun Sep 05, 2004 6:26 pm

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?

kmhasan · Post by **kmhasan** » Sun Sep 05, 2004 7:16 pm

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?

.. · Post by .. » Mon Sep 06, 2004 6:39 pm

Agree

So, before constructing the network, you have to use the LIS algorithm
to decide putting each mission at which stage, right?

kmhasan · Post by **kmhasan** » Mon Sep 06, 2004 7:18 pm

Right.

Khaled_912 · Post by **Khaled_912** » Wed Aug 23, 2006 4:01 am

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]).