Nastya Is Buying Lunch | Editorial by mynk322

Solution 1: Let's solve the proiblem, iterating from the end, adding pupils one by one. I. e for every suffix we are solving original problem without pupils, which don't belong to this suffix. What happens when we add pupil i to the suffix?

By the time when we add pupil i we have answer for the previous suffix. In this answer there are, probably, pupils, which Nastya can't overtake. Let this subset of pupils be P. Then, if i-th pupil can give place for Nastya and all pupils from P, we will swap them. Otherwise, we can add this pupil to P. In order to check this condition we can iterate through pupils, who can swap with i-th pupil, and calculate how many are contained in P. This solution works in O(n+m). Obviously, when we consider all suffixes, answer will be n−1−|P|.

Solution 2: Let's build directed graph, where i-th vertex corresponds i-th pupil and edge from u to v exists if and only if pupil v can't give place to pupil u and v is closer to the beginning of queue than u. We can note that answer is number of vertexes in this graph, which are unreachable from Nastya's vertex. Proof:

(1) Obviously, if edge from u to v exists, pupil v will always be in front of u.

(2) If vertex v is reachable from vertex u, the same condition is true.

Let's prove that Nastya can overtake pupils, who are unreachable in graph by giving an algorithm how to do it. Let there are unreachable vertexes in front of Nastya, u - the closest from them. If u is directly in front of Nastya, they can swap and number of such vertexes will decrease.

Otherwise, let v be the next pupil after u (further from the beginning). Because u is the closest unreachable vertex, v is reachable. So, there is no edge from u to v and they can change their places. We can similarly move v further and then swap him with Nastya.

Using this algorithm, Nastya can overtake all pupils, which correspond unreachable vertexes.

Fine, now we just have to calculate number of such vertexes. It can be done with standard algorithm "DFS by complement graph".

Nastya Is Buying Lunch | Editorial by mynk322

Download submission

All caught up!

View submission

Is your resume even shortlisted?