K-th Smallest Number in a Running Window

Problem definition

Given a sequence of integers, your program should identify the K-th smallest number in a running window of M integers.

I/O formats

• Input format
  • Line#1: Three integers N, M, K, seperated by space.
    • N is the total length of the input sequence (1<=N<=200000).
    • M is the size of the running window (1<=M<=100000, M<=N)
    • K is the interger such that your program can find the the K-th smallest integer in a running window (1<=K<=M)
  • Line#2: A sequence of N integers a1, a2,... , an, (1<=ai<=2147483647)
• Output format

  When the running window is moving from left to right, output the K-th smallest integer in one line. The first running window should contain the first M elements of the sequence. Eventually there should be N-M+1 output, with each output in a line.

I/O Examples

• Sample input file 9 5 3 3 4 2 1 5 5 1 1 5
• Sample Output file 3 4 2 1 5
• Hints Sample example works as follows: 3 4 2 1 5 5 1 1 5 3 4 2 1 5 --sorted-> 1 2 3 4 5 -> ans=3 4 2 1 5 5 --sorted-> 1 2 4 5 5 -> ans=4 2 1 5 5 1 --sorted-> 1 1 2 5 5 -> ans=2 1 5 5 1 1 --sorted-> 1 1 1 5 5 -> ans=1 5 5 1 1 5 --sorted-> 1 1 5 5 5 -> ans=5

Open Test Sets

• Please refer to the link of "Test data generator" show below.
• TA will run your program on a workstation, like this:

  ./myProgram < inputFile > outputFile
  

• Time/memory limits for each test set are listed on our judge system.

Hints and Suggestions

• Material provided by TA
  1. Slides for this homework
  2. Test data generator
• Suggested basic method:
  1. Use a sorting method on the first window.
  2. For each running window afterwards, remove the first element and insert the incoming new element in the correct position using binary search. Output the k-th smallest number.
• Summary of methods for finding the k-th smallest element in a vector