Time Limit: 2 sec / Memory Limit: 1024 MB Score: 425 points Problem Statement You are…
- User
Time Limit: 2 sec / Memory Limit: 1024 MB
Score: 425 points
Problem Statement You are given a permutation P=(P 1 ,P 2 ,…,P N ) of (1,2,…,N).
A length- K sequence of indices (i 1 ,i 2 ,…,i K ) is called a good index sequence if it satisfies both of the following conditions:
1≤i 1 <i 2 <⋯<i K ≤N. The subsequence (P i 1
,P i 2
,…,P i K
) can be obtained by rearranging some consecutive K integers. Formally, there exists an integer a such that {P i 1
,P i 2
,…,P i K
}={a,a+1,…,a+K−1}. Find the minimum value of i K −i 1 among all good index sequences. It can be shown that at least one good index sequence exists under the constraints of this problem.
Constraints 1≤K≤N≤2×10 5
1≤P i ≤N P i
=P j if i =j. All input values are integers. Input The input is given from Standard Input in the following format:
N K P 1
P 2
… P N
Output Print the minimum value of i K −i 1 among all good index sequences.
Sample Input 1 Copy 4 2 2 3 1 4 Sample Output 1 Copy 1 The good index sequences are (1,2),(1,3),(2,4). For example, (i 1 ,i 2 )=(1,3) is a good index sequence because 1≤i 1 <i 2 ≤N and (P i 1
,P i 2
)=(2,1) is a rearrangement of two consecutive integers 1,2.
Among these good index sequences, the smallest value of i K −i 1 is for (1,2), which is 2−1=1.
Sample Input 2 Copy 4 1 2 3 1 4 Sample Output 2 Copy 0 i K −i 1 =i 1 −i 1 =0 in all good index sequences.
Sample Input 3 Copy 10 5 10 1 6 8 7 2 5 9 3 4 Sample Output 3 Copy 5
- Assistant
To solve the problem of finding the minimum value of ( i_K - i_1 ) among all good index sequences in the given permutation ( P ), follow these steps:
Step-by-Step Reasoning:
-
Understanding the Problem:
- You are given a permutation ( P = (P_1, P_2, \ldots, P_N) ) of ((1, 2, \ldots, N)).
- A good index sequence is a sequence of ( K ) indices ( (i_1, i_2, \ldots, i_K) ) such that the corresponding elements in ( P ) form a set of ( K ) consecutive integers.
- The goal is to minimize the difference ( i_K - i_1 ), where ( i_1 ) is the smallest index and ( i_K ) is the largest index in the sequence.
-
Mapping Positions:
- First, map each value in ( P ) to its position. This means creating an array
poswherepos[x]gives the position of the value ( x ) in ( P ).
- First, map each value in ( P ) to its position. This means creating an array
-
Sliding Window Technique:
- We need to find a window of ( K ) consecutive values such that their positions in the permutation ( P ) have the smallest range (i.e., ( \text{max(pos)} - \text{min(pos)} )).
- To efficiently compute the minimum and maximum within each window of size ( K ), use two deques (
min_dequefor minimums andmax_dequefor maximums).
-
Iterative Process:
- Iterate over the
posarray and maintain the deques to always have the current window's minimum and maximum. - For each window from ( a ) to ( a + K - 1 ):
- Update the deques by removing elements that are out of the current window.
- Compute the cost as ( \text{max(pos)} - \text{min(pos)} ).
- Track the minimum cost across all windows.
- Iterate over the
-
Edge Cases:
- If ( K = 1 ), the cost is always ( 0 ) since the window contains only one element.
- Handle cases where ( K = N ) by simply computing the range from the entire array.
Implementation:
Below is the implementation based on the above reasoning:
import sys import collections def main(): import sys import threading def solve(): import sys N_K = sys.stdin.readline().split() while len(N_K) <2: N_K += sys.stdin.readline().split() N, K = map(int, N_K) P = [] while len(P) < N: P += list(map(int, sys.stdin.readline().split())) pos = [0]*(N+1) for idx, val in enumerate(P): pos[val] = idx +1 # 1-based min_deque = collections.deque() max_deque = collections.deque() min_cost = float('inf') for x in range(1, N+1): # Update min_deque while min_deque and pos[x] <= pos[min_deque[-1]]: min_deque.pop() min_deque.append(x) # Update max_deque while max_deque and pos[x] >= pos[max_deque[-1]]: max_deque.pop() max_deque.append(x) # When window is filled if x >= K: a = x - K +1 # Remove out of window from deques while min_deque and min_deque[0] < a: min_deque.popleft() while max_deque and max_deque[0] < a: max_deque.popleft() current_min = pos[min_deque[0]] current_max = pos[max_deque[0]] cost = current_max - current_min if cost < min_cost: min_cost = cost print(min_cost) threading.Thread(target=solve).start() if __name__ == "__main__": main()Explanation of the Code:
-
Input Handling:
- The input is read efficiently using
sys.stdin.read. - The permutation ( P ) is read and the positions are mapped.
- The input is read efficiently using
-
Deque Initialization:
- Two deques (
min_dequeandmax_deque) are used to track the minimum and maximum positions within the current window of size ( K ).
- Two deques (
-
Main Loop:
- For each value ( x ) from ( 1 ) to ( N ):
- Update
min_dequeto maintain the minimum position. - Update
max_dequeto maintain the maximum position. - Once the first window of size ( K ) is reached, compute the cost and update the minimum cost found.
- Update
- For each value ( x ) from ( 1 ) to ( N ):
-
Output:
- Finally, the minimum cost is printed.
Conclusion:
This approach ensures that we efficiently compute the minimum ( i_K - i_1 ) over all possible good index sequences by leveraging a sliding window technique with deques to maintain the necessary minimum and maximum values within each window.
-