DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Erase the Minimum

Back to problem

Editorial

Which elements can be deleted? If xxx is the minimum in a segment of length at least two, it has an immediate neighbor inside that segment, and that neighbor is larger. Conversely, a larger immediate neighbor allows us to choose that pair and delete xxx. Thus an element can be deleted exactly when its current left or right neighbor is larger.

Order of retained positions Operations only delete elements, so AAA must be a subsequence of PPP. Let pos[v]\mathrm{pos}[v]pos[v] be the original position of value vvv. Check

pos[A1]<pos[A2]<⋯<pos[AM].\mathrm{pos}[A_1]<\mathrm{pos}[A_2]<\cdots<\mathrm{pos}[A_M].pos[A1​]<pos[A2​

This also rejects repeated values in AAA.

Condition for a gap Retained elements are never deleted. The elements to delete therefore form independent gaps: before the first retained element, between consecutive retained elements, and after the last one. Elements from different gaps cannot become adjacent across a retained element.

For a nonempty gap, let ggg be its maximum and bbb the larger of its adjacent retained boundary values. An end gap has only one boundary. The gap can be completely deleted if and only if g<bg<bg<b.

Necessity: deleting ggg requires a larger neighbor. None exists inside the gap, so such a neighbor must be a retained boundary, implying b>gb>gb>g.

Sufficiency: delete gap elements in increasing order. While at least two remain, the smallest remaining element has a larger neighbor in the same gap and can be deleted. When only ggg remains, it is adjacent to a boundary of value b>gb>gb>g and can also be deleted. Empty gaps automatically satisfy the condition.

Implementation Visit retained elements in order and scan each preceding gap once to find its maximum. Use zero as the missing left boundary and as the maximum of an empty gap. Since real values are positive, the same comparison handles these cases. Check the final suffix separately.

Print YES exactly when the position order and every gap condition hold. The global maximum NNN cannot be deleted, so an AAA missing NNN is always rejected. However, neither containing NNN nor being a subsequence is sufficient. For example, P=[6,1,5,2,3,4]P=[6,1,5,2,3,4]P= and satisfy both properties but cannot delete between boundaries .

Time and space are O(N+M)O(N+M)O(N+M). All positions, values, and gap maxima are at most 200 000200\,000200000; no large arithmetic is needed.

Subtask 1 represents retained positions by a bitmask and uses BFS over all legal segment operations. There are at most 2N2^N2N states. Incrementally maintaining each interval minimum enumerates the operations of one state in O(N2)O(N^2)O(N2) time. Total time is O(2NN2)O(2^N N^2)O(2 and space is , sufficient for . Subtask 2 uses the linear check above.

Solution written by GPT6

]
<
⋯<
pos[AM​].
[6,1,5,2,3,4]
A=[6,1,2,3,4]A=[6,1,2,3,4]A=[6,1,2,3,4]
555
1,21,21,2
N
N2
)
O(2N+N)O(2^N+N)O(2N+N)
N≤10N\leq10N≤10