10546 - The Eagle's Nest

[Pupirev Sergei]

I can't understand, why my algorythm is wrong. I've checked it many times. Can somebody give me test cases.

I used the following algo:
Let K-the maximum number of mission for one game. I find first increasing subsequense of length K, delete it from original sequense. Then repeat it.

[kmhasan]

Greedy choice works for this problem. But not all greedy choice will work. If you start tracing from the back you always need to find the parent element which is closest (in terms of placement in the sequence) to the element at hand.

To feel even safer, you can always run max flow on the vertex splitted network. That's the way I solved the problem.

[Whinii F.]

Tomal:
Wow was that so? I thought I should just select the mission with the lowest difficulty and has a K-length increasing sequence ending with it.

Because the following part of the problem statement:

A player can only play the missions that are harder than all the missions that he/she has completed.

made me to think that I cannot play missions easier than what I completed even after I clear the game once.

For instance, if there are missions with difficulties 4 5 2 3 and I should always choose 3, because I cannot play mission 2 and 3 after completing 4 and 5, "EVEN AFTER I CLEAR THE GAME ONCE".

Am I wrong in here? Your post seems to intend that we can play 4 5 after choosing 2 and 3 to clear the game once. (I didn't need any choosing when I looked at the problem at my perspective)

Regards,

[Dominik Michniewski]

Whinii F., for your input:
1. player can play game and completed maximum number of missions (2):
2 and 3 or 4 and 5
2. player can play again and complete rest of missions ....

I also think that for input like "1 1 2 2 3 3" (without names) it's still possible to complete all the missions ...

I solve this problem used LIS algorithm.

Best regards
DM

[Pupirev Sergei]

Hm, i do the same thing, but still WA.
Can somebody prove that greedy method give the correct answer?

[kmhasan]

Whinii:
Yes, once you complete the game, you can play the game again with a fresh start. So you can actually play games that are easier than the missions that you completed in the previous time you played the game. But now when I read the problem statement again, I understand your point -- it's a bit confusing, I admit. It didn't really came up to my mind. In that paragraph I was talking about what happens when you play the game once....

So you can play either 2,3 then 4,5 or 4,5 and then 2,3 in both the case your answer is 4.

Pupirev:
I am writing a paper on counting disjoint LISs . Among other things the proof that a certain greedy strategy would give you the optimal result would be there. I'd send you a PM when I'm done.

[carneiro]

I'm still trying to understand the problem statement. During the contest I was convinced that once I played mission X, I couldn't play any mission < X anymore. But now it's explained that I can if I restart the game. Ok.

Now I try to figure out some strange things:

- What's the use of the mission names ?
- What do the constraints really constrain ??? Do they imply that the missions should be completed in that order ? Or that only these missions should be completed (if that's the option, how many missions are there then?)
- If the missions should be completed in the given order, and the output should be the maximum number of missions that can be completed, and YES, I CAN play missions again if i simply restart the game, why isn't this number just equal to all missions ? I will always be able to play all missions if I can restart and play lower missions at will.

Please, help me understand this problem.

[kmhasan]

- What's the use of the mission names ?

It makes mission with same difficulty different entity. Otherwise for a sequence 1,1,3,2 I could not say 1,3 and 1,2 are disjoint LIS as it would be ambiguous whether I treat two numbers different on their value or on their place in the sequence.

What do the constraints really constrain ??? Do they imply that the missions should be completed in that order ? Or that only these missions should be completed (if that's the option, how many missions are there then?)

The order of the missions are based on the storyline, so the missions cannot be reordered to increase the sequence length. If that were to happen then the answer would always be equal to the total number of missions. And the constraint also means that when you're playing the game for the i th time, you can only play a mission that's harder than the missions you played in this i th time.

If the missions should be completed in the given order, and the output should be the maximum number of missions that can be completed, and YES, I CAN play missions again if i simply restart the game, why isn't this number just equal to all missions ? I will always be able to play all missions if I can restart and play lower missions at will.

Because once you play a mission, it would be deleted, you cannot play it again. It is not going to appear in the list of mission when you play the game for the (i+1)th time. The only exception to this rule were the first and the final mission which would not be in the input, and would never be counted. You need to play |length of LIS| missions every time, so it can be the case that you cannot play all the missions. The 2nd sample given with the problem statement shows that.

I hope it is clear now.

[kmhasan]

Some greedy approaches will fail the following case:

Code: Select all

9
a1	7
a2	5
a3	1
a4	15
a5	13
a6	8
a7	16
a8	10
a9	9
0

If we greedily choose a3,a6,a7(1,8,16) then we cannot choose any other LIS of length 3. But as you'd see we could easily play 6 missions in two games a1,a4,a7(7,15,16) and then a2,a6,a9(5,8,9).

[windows2k]

To feel even safer, you can always run max flow on the vertex splitted network. That's the way I solved the problem.

Hello kmhasan,
I tried to solve the problem with max flow
First create a source and a sink, create a edge from source to indegree of node , create a edge from outdegree of node to sink , then according to his diffculties , creates a edge from an outdegree i to an indegree j
Then find a path from source to sink which length is exackly K , run until
no argument path exist.
But I get WA .
Could you say your thought about solving the problem? thx:)
Sorry for my poor English

[kmhasan]

Did you split each of the vertices into two parts and put an unit edge between them? This is necessary to ensure that a mission is a part of only one game.

[windows2k]

Did you split each of the vertices into two parts and put an unit edge between them? This is necessary to ensure that a mission is a part of only one game.

Yes , I did.
But I thought my method is wrong.
Could you explain your thought clearly?

[kmhasan]

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.

[junjieliang]

Just for curiosity, is this the method for min path cover?

[kmhasan]

Umm...so far as I understand, "No". Because you are not trying to take up all the edges in the DAG. Here the idea is to find the maximum number of vertex disjoint paths in the DAG/Multistage graph.