topcoder srm530 div.2 1000pt

还是topcoder的题目有水平！

GogoXReimuHakurai

Used as: Division Two - Level Three:

Value	1000
Submission Rate	257 / 844 (30.45%)
Success Rate	0 / 257 (0.00%)
High Score	nullfor null points (NONE)
Average Score	No correct submissions

The solution is exactly the same with D1-medium. In the D1-medium, the graph is a general graph instead of a Directed Acyclic Graph as in this problem.Also, the actor is not "Reimu Hakurai" but "Marisa Kirisame".Aside from that, they are the same and so, please see the editorial for D1-medium instead. However, it is arguably easier to come up with the solution if the graph is assumed to be a directed acyclic graph and hence, we differ the D1-med and D2-hard.

Remarks

Pretty amazingly, even though 100+ coders submitted solution to this problem, none is correct. I think this is thanks to the weak examples. I deliberately used weak examples in greedy problems in Division 2 since most Division 2 coders tend to use whatever greedy algorithm that comes to their mind without proofing its correctness. Hence, if we design the examples to be too strong, we are afraid that coders will use the "While not pass example, try another algorithm" algorithm to solve this problem. I don't like that algorithm very much.

Note that since the solution to this problem is exactly the same with the D1-medium, it is very unlikely that the author's intended solution is wrong.

Alternative solutions and additional comments.

GogoXMarisaKirisima

Used as: Division One - Level Two:

Value	500
Submission Rate	162 / 590 (27.46%)
Success Rate	56 / 162 (34.57%)
High Score	Gassafor 390.07 points (16 mins 3 secs)
Average Score	251.79 (for 56 correct submissions)

Nice graph

If stage N-1 is not reachable from stage 0, the answer is clearly 0. Also, if we can't reach a stage i or if stage N-1 is not reachable from stage i, then clearly any of our playthroughs will never visit stage i.

So, in the following discussions, we assume that:

• All stages are reachable from Stage 0.
• Stage N-1 is reachable from all stages.

Trivia: admins call this a "nice graph".

Finally, assume that our nice graph has at least 3 nodes. C'mon, the N=2 case is pretty obvious.

Nice solution

Okay, so under our assumption, the solution is one line. Suppose the number of stages is N and the number of choices is M. Then, the algorithm would be:

return M - N + 2

Um.. yeah... um.. okay... um... why?

Uh proof

There are (N-2) other stages aside from stage 0 and stage N-1. Since we want to maximize the number of playthroughs, at the end of all playthroughs, all these (N-2) stages must be visited in at least one playthrough. We will now assign each stage a state of either "visited" or "not visited". Initially, all stages are "not visited". If a playthrough consists of visiting a stage, then that stage becomes "visited".

M, the number of choices, is an obvious upper bound on our answer. The reason that we cannot have exactly M playthroughs is because of the N-2 stages. If a stage is "not visited", then a playthrough that visits this stage for the first time will use a new choice to lead to this stage, and another new choice that leads out of this stage.

Claim: We can have M - (N-2) playthroughs

To see this, imagine the (N-2) loss in the number of playthroughs as "cost" to turn a "not-visited" stage into "visited" stage. That is, we claim that there exists a series of playthroughs that can transform all "not visited" stages into "visited" stages by losing only (N-2) choices. It's as follows.

While there are a "not visited" stage, pick one that is reachable from a "visited" stageVISthrough exactly one new choice (there must exist such stage since we assume our graph to be nice). BecauseVISis "visited", we can reach this stage using only used choices. Then, we use this choice to move to our "not visited" stage. From here, we pick any simple path that leads from this stage to either stage N-1 or another "visited" stage such that the stages in our simple path (except the last) are all "not visited". There must exist such path since our graph is nice. From the last node, since it's "visited" or N-1, there exists a path from that stage to stage N-1 that uses only used choices. And this completes our playthrough.

What is the result of that playthrough? The only place where we used new choices is in the simple path. Furthermore, since all nodes in the simple path except the first and the last node are "not visited", all choices are new. Suppose there are K "not visited" nodes in this simple path. Then, our playthrough used exactly K+1 new choices. However, as a consequence, K "not visited" stages are transformed into "visited" stages. Hence, this is in line with what we claim, since we are able to turn K "not visited" stages into K "visited" stages by losing only K new choices (remember that this is a playthrough and hence, we deduct 1 from the K+1 new choices we make).

After we are done, all stages are "visited". We can then proceed to create a new playthrough for every new choices left, and since we only lost (N-2) new choices, we have M - (N-2) playthroughs.

We must have at least M - (N-2) playthroughs

This is a consequence of the fact that if we perform the maximum number of playthroughs, all stages must be "visited" in the end. Initially, we have N-2 "not visited" stages. The first time a playthrough visits this stage, it must use a new choice. Furthermore, it must still use at least one new choice to lead it out from this stage. Hence, each "not visited" stage lost at least one new choice and hence, the maximum number of playthroughs possible is M - (N-2), since (N-2) is the initial number of "not visited" stages.

And that's it!

So, because there may be at most M - (N-2) playthroughs, and we have shown the existance of that playthroughs, we can safely say that the answer is M - (N-2).pieguy'ssolutionclearly illustrates this short solution.

Harder version

Assume the graph is nice. Suppose that the playthroughs may begin not in stage 0, but in any stage given in an array. Furthermore, the playthroughs may end not in stage N-1, but in any stage given in another array (not necessarily disjoint with the first array). What is the maximum number of playthroughs possible?

For example, suppose the available choices are:

0->1
1->2
2->0
3->4

The possible starting stages are:

{stage 0, stage 3}

The possible finishing stages are:

{stage 0, stage 1, stage 4}

Then, the maximum number of playthroughs are 3:

0->1
0->1->2->0
3->4

Not a hint: This is harder to proof and no longer 1 line.

Remarks

The original problem proposed has this graph nice-ness in the statement. However, we decided that one-line answer is too crazy (literally) for a D2-hard and D1-medium. I mean, c'mon...

For all die-hardTouhoufans, the names is an intentional typo to avoid copyright infringement. So it's not a mistake :). Reimu Hakurei and Marisa Kirisame are the main "protagonists" of Touhou and have a rather... eccentric personality and reasons to "fight".

By the way, Touhou Project is a very infamous game that asks players to dodge umm... bullets. But the amount of bullets is huge that it was given the name "Bullet Hell". I personally like to call it "Firework" (officially, they call it "Spell cards"). Oh okay, why are we suddenly talking about this game?

Trivia: Everything in Touhou Project (music, graphics, code) is developed by one man only.

Alternative solutions and additional comments.