Passport Control
InterviewTime limit0.2sMemory limit512 MB
Decide whether a given exit permutation can arise from a FIFO arrival line feeding k desk queues, each holding an arrival-ordered subsequence.
- Level
Medium5 of 10
- Topics
- Queue, Stack, Greedy, Implementation
- Solved
- No attempts yet
Problem
Figure G.1: Each of the N arriving passengers must pass through one of the k passport control desks {Q**k}.
N arriving passengers wait for passport control in the arrival queue in the order [1, 2, … , N − 1, N], as shown in Figure G.1. A passenger can leave the airport after passing through one of the k passport control desks. If the order of passengers waiting in line at arrival is [1, 2, … , N − 1, N], the order [π1, π2, … π**N−1, π**N] in which they pass through the k passport control desks and leave the arrival hall can differ from the original order. Given k passport control desks, you must determine whether a given exiting order is possible.
Consider an example. If N = 3 and k = 2, then among the orders for leaving the arrival hall, [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], and [3, 1, 2] are possible, but [3, 2, 1] is not. Given an order [π1, … , π**N] for leaving the arrival hall as input, you must print YES if the order is possible, and NO otherwise. Note that once passengers are lined up in a particular queue, their order cannot be changed arbitrarily. Also assume that the queue at each passport control desk is large enough to hold all N passengers.
Input
Input is read from standard input. The first line gives two integers N and k. N is the number of arriving passengers and k is the number of passport control desks. Here, 2 ≤ k ≤ N ≤ 100. The second line gives the order [π1, … , π**N] in which passengers leave the arrival hall.
Output
Output is written to standard output. If it is possible for passengers to leave the arrival hall in the given order [π1, … , π**N], print YES; otherwise, print NO.