Düzelt Kendini

FJ'nin satır halinde dizilmiş $n$ ineği var (farklı ID'lere sahip 1, \ldots, n). FJ, ineklerinin ID'lerine göre artan sırada sıralanmış olmasından hoşlanır, ancak ne yazık ki şu anda sırasız durumdalar. Geçmişte FJ, ineklerini sıralamak için "kabarcık sıralaması" gibi çığır açan algoritmalar kullanmış olsa da, bugün oldukça tembel hissediyor. Bunun yerine, belirli ineklere tek tek "düzelt kendini" diye bağıracak. Kendisine bağırıldığında, bir inek (kendi bakış açısından) sırasız olmadığından emin olur. Sağındaki inek daha küçük bir ID'ye sahip olduğu sürece, yer değiştirirler. Ardından, solundaki inek daha büyük bir ID'ye sahip olduğu sürece, yer değiştirirler. Bundan sonra, inek "düzelt kendini" işlemini tamamlamış olur: solundaki inek daha küçük bir ID'ye, sağındaki inek ise daha büyük bir ID'ye sahiptir.

FJ, ineklerden bir alt küme seçmek ve ardından bu alt kümedeki her ineğe sırayla (artan ID sırasına göre) bağırarak, $n$ ineğin tamamı sıralanana kadar bunu tekrar tekrar yapmak istiyor. Örneğin, eğer \{2, 4, 5\} ID'lerine sahip inek alt kümesini seçerse, önce inek $2$'ye, sonra inek $4$'e, sonra da inek $5$'e bağıracaktır. Eğer $n$ inek hâlâ sıralanmamışsa, aynı ineklere gerektiği kadar tekrar tekrar bağıracaktır.

FJ hangi ineklerin dikkat ettiğinden emin olmadığı için, bu alt kümenin boyutunu en aza indirmek istiyor. Ayrıca, FJ $k$ sayısını çok şanslı buluyor. Bu alt kümesine tekrar tekrar bağırmanın sonunda tüm ineklerin sıralanmasıyla sonuçlanacağı, minimum boyuttaki alt kümeler arasında sözlüksel olarak $k$-inci en küçük alt kümeyi bulmasına yardım edin.

\{1, \ldots, n\} kümesinin bir $S$ alt kümesi, elemanlarının (artan sırada) listesi $T$ alt kümesinin elemanlarının (artan sırada) listesinden sözlüksel olarak daha küçükse, $S$ alt kümesi $T$ alt kümesinden sözlüksel olarak daha küçüktür. Örneğin, \{1, 3, 6\} kümesi \{1, 4, 5\} kümesinden sözlüksel olarak daha küçüktür.