K-th number

K-th number

امروز به بررسی مساله ی K-th number که یکی از سوالات ACM/ICPC 2004 NEERC Northern Subregional و همچنین آخرین مسابقه ی هفتگی ما بوده می پردازم.

صورت مساله

صورت مساله این است که n تا عدد داریم و می خواهیم پرسش هایی از نوع: “k-امین کوچکترین عدد در بین اعداد i-ام تا j-ام چیست؟”

مثلا اگر n عدد ما عبارت باشند از: {1,5,2,6,3,7,4} ، سومین کوچکترین عدد بین اعداد 2-ام تا 5-ام (یعنی {5,2,6,3} ) برابر 5 می باشد و اولین کوچکترین عدد بین اعداد 4-ام تا 4-ام برابر 6 می باشد.

بدیهی ترین راه این است که برای هر پرسش اعداد i-ام تا j-ام را مرتب کنیم و k-امین کوچکترین را به عنوان خروجی چاپ کنیم. ولی در این صورت برای پاسخ به هر پرسش زمانی از مرتبه ی O(n log n) صرف خواهیم کرد که با توجه به اینکه حداکثر 5000 پرسش از این نوع را می خواهیم پاسخ دهیم این راه حل چندان مناسب نمی باشد.

کلید اصلی حل این سوال این است که می توانیم به پرسش “چند عدد کوچکتر یا مساوی عدد m در بین اعداد a-ام تا b-ام وجود دارد؟” در زمان O(log^2 n) پاسخ داد. در نتیجه با استفاده از پاسخ این پرسش و جستجوی دودوئی می توان هر پرسش را در زمان O(log^3 n) پاسخ داد. در زیر شبه-کد مربوط به این قسمت را مشاهده می کنید:

# arr[0..n-1] is the sorted version of input array
# We want to answer: Find k-th smallest number among a-th to b-th numbers
Left = 0
Right = n-1
Result = arr[Right]
while Left <= Right:
    Mid = (Left + Right) / 2
    if Count(a, b, arr[Mid])< k:
        Left = Mid + 1
    else:
        Result = arr[Mid]
        Right = Mid - 1

حال، به بررسی اینکه چگونه می توان تعداد اعداد کوچکتر یا مساوی یک عدد را بین اعداد a-ام تا b-ام به دست آورد می پردازیم. برای این کار، از درختی دودوئی استفاده می کنیم. مثلا برای مثال بالا این درخت به شکل زیر خواهد بود:

ریشه ی این درخت نماینده ی کل اعداد می باشد. فرزند سمت چپ هر گره نماینده ی نیمه ی اول بازه ی مربوط به آن گره و فرزند سمت راست نماینده ی نیمه ی دوم بازه ی مربوط به آن گره می باشد. همچنین برای هر کدام از گره ها اعداد موجود در بازه ی مربوط به آن را به صورت مرتب شده داریم.

بدیهی است که می توان هر بازه را معادل با یک سری گره در این درخت در نظر گرفت که تعداد آن گره ها از مرتبه O(log n) می باشد. مثلا برای بازه ی 2 تا 7، گره های 3-2 و 7-4، برای بازه ی 3 تا 5 گره های 3-3 و 5-4 و …

با استفاده از جستجوی دودوئی می توان مشخص کرد که در یک آرایه ی مرتب چند عدد کوچکتر یا مساوی یک عدد خاص وجود دارد. پس برای مشخص کردن تعداد اعداد کوچکتر مساوی یک عدد در بازه ای خاص، گره های مربوط به آن بازه را در درخت پیدا می کنیم و با استفاده از جستجوی دودوئی در آرایه ی مربوط به هر گره تعداد اعداد کوچکتر مساوی در کل بازه را بدست می آوریم. پیچیدگی زمانی این مرحله از مرتبه ی O(log^2 n) می باشد.

حالا توضیح می دهیم که درخت بالا را چگونه می سازیم. برای ساختن درخت بالا از یک آرایه استفاده می کنیم که عنصر با اندیس یک ریشه ی درخت می باشد و فرزندان گره با اندیس i گره هایی با اندیس های 2i و 2i+1 می باشند. در این آرایه، برای هر گره نگه می داریم که آرایه ی مرتب شده مربوط به آن گره در کجا قرار دارد. من در راه حل خودم آرایه های مرتب شده را در یک آرایه ی دیگر ذخیره کرده ام و در آرایه ی اصلی برای هر گره اندیس شروع و طول مکانی که آرایه ی مرتب شده مربوط به آن گره در آن قرار دارد را نگهداری می کنیم.

در زیر تابع مربوط به ایجاد این درخت را مشاهده می کنید:

int arr[100000]; // Contains the original information
int mem[2000000]; // Container for node sorted-arrays
int heap[250000][2]; // The Actual Tree
int cnt = 0; // Shows how many items has been inserted into Len till now
void Create(int idx, int Len, int root)
{
      if(Len == 0)
              return;
      for(int i = 0; i < Len; i++)
              mem[cnt+i] = arr[idx+i];
      sort(mem+cnt, mem+cnt+Len);
      heap[root][0] = cnt;
      heap[root][1] = Len;
      cnt += Len;
      if(Len == 1)
              return;
      Create(idx, Len / 2, root * 2);
      Create(idx + Len / 2, Len - Len / 2, root * 2 + 1);
 
}

این تابع اندیس شروع و طول قسمتی از آرایه را که می خواهیم به درخت اضافه کنیم و همچنین اندیس گرهی از درخت که این قسمت از آرایه به آن اضافه خواهد شد را می گیرد. برای درست کردن کل درخت، آن را با پارامترهای (Create(0,n,1 صدا می کنیم.

و بالاخره، به بررسی روش انتخاب گره های مناسب برای بدست آوردن جواب مساله می پردازیم. فرض کنید می خواهیم گره هایی از زیردرخت با ریشه ی root را انتخاب کنیم که بازه ی مربوط به هر کدام از این گره ها کاملا زیر مجموعه ای از بازه ی مورد نظر باشند و هیچ دو گرهی وجود نداشته باشد که پدرشان یکی باشد و بازه ی مربوط به پدرشان نیز زیر مجموعه ی بازه ی مورد نظر باشد. برای این کار، چند حالت وجود دارد:

1- بازه ی مربوط به root هیچ اشتراکی با بازه ی مورد نظر ندارد. در این صورت هیچ کدام از فرزندان root عضو مجموعه گره های مورد نظر نیست. و نیازی نیست فرزندانش را بررسی کنیم.

2- بازه ی مربوط به root زیرمجموعه ی بازه ی مورد نظر می باشد. در این صورت خود گره root داخل مجموعه گره های مورد نظر می باشد. و نیازی نیست فرزندانش را بررسی کنیم.

3- بازه ی مربوط به root زیر مجموعه ی بازه ی مورد نظر نمی باشد، ولی با بازه ی مورد نظر اشتراک دارد. در این صورت خود گره root داخل مجموعه ی گره های مورد نظر نمی باشد ولی تعدادی از گره های موجود در زیر درخت آن متعلق به این مجموعه می باشد. در این صورت فرزندان root را باید بررسی کنیم.

شبه کد تابع مربوط به انتخاب گره ها به شکل زیر خواهد بود:

function Select(root, Left, Right):
   if [Left, Right] is subset of [a, b]:
          # A new node has been found
          # which is useful for us
   elif [Left, Right] intersects [a, b]:
          Length = Right - Left + 1
          Select(2 * root, Left + Length / 2 - 1, Right)
          Select(2 * root + 1, Left + Length / 2, Right)

گمان کنم توضیحات بالا برای حل مساله ی مورد نظر کافی باشد. ولی اگر همچنان مشکلی داشتید یا پیشنهادی داشتید comment بگذارید!

تمرین بیشتر

این مساله مثال خوبی بود برای یادگیری کار کردن با درخت های دودوئی برای پاسخ دادن به query های مربوط به یک آرایه. برای تمرین بیشتر توصیه می کنم مسائل ساده تر زیر را نیز حل کنید:

Potentiometers

Unreal Story : که البته این سوال یک راه حل خیلی ساده تر و تمیزتر هم دارد. ولی به هر حال آن را می توان با این روش نیز حل کرد.

Cryptography

کد من برای حل این مساله

#include <iostream>
#include <ctime>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdio>
 
using namespace std;
 
#define P pair<int, int>
 
int arr[120000];
int mem[2200000];
int heap[600000][2];
int cnt, n, m;
int a, b, c;
 
void Insert(int idx, int Len, int root)
{
	if(Len == 0)
		return;
	memcpy(mem+cnt, arr+idx, sizeof(int)*Len);
	sort(mem+cnt, mem+cnt+Len);
	heap[root][0] = cnt;
	heap[root][1] = Len;
	cnt += Len;
	if(Len == 1)
		return;
	Insert(idx, Len / 2, root * 2);
	Insert(idx + Len / 2, Len - Len / 2, root * 2 + 1);
}
 
bool Inside(int a, int b, int c, int d)
{
	return a >= c && b <= d;
}
 
bool Intersect(int a, int b, int c, int d)
{
	a >?= c;
	b <?= d;
	return a <= b;
}
 
int Count(int a, int b, int c, int root, int L, int R)
{
	if(Inside(L, R, a, b))
	{
		int Left = heap[root][0];
		int Right = heap[root][0] + heap[root][1]-1;
		int Result = Left-1;
		while(Left <= Right)
		{
			int Mid = (Left + Right) / 2;
			if(mem[Mid] > c)
			{
				Right = Mid-1;
			}
			else
			{
				Result = Mid;
				Left = Mid+1;
			}
		}
		return Result - heap[root][0] + 1;
	}
	else if(R > L && Intersect(a, b, L, R))
	{
		int Len = R - L + 1;
		int result = Count(a, b, c, 2 * root, L, L + Len / 2 - 1);
		result += Count(a, b, c, 2 * root + 1, L + Len / 2, R);
		return result;
	}
	return 0;
}
 
int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
		scanf("%d", arr + i);
	cnt = 0;
	Insert(0, n, 1);
	sort(arr, arr + n);
	for(int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		a--;b--;
		int Left = 0, Right = 1;
		while(true && Right < n)
		{
			int count = Count(a, b, arr[Right], 1, 0, n-1);
			if(count >= c)
				break;
			Left = Right+1;
			Right *= 2;
			if(Right > n)
				break;
		}
		Left <?= n - 1;
		Right <?= n - 1;
		int Result = arr[Right];
		while(Left <= Right)
		{
			int Mid = (Left + Right) / 2;
			int value = arr[Mid];
			int count = Count(a, b, value, 1, 0, n-1);
			if(count < c)
				Left = Mid + 1;
			else
			{
				Result = value;
				Right = Mid - 1;
			}
		}
		printf("%d\n",Result);
	}
	return 0;
}

K-th number

صورت مساله

توضیح و بررسی راه حل

تمرین بیشتر

کد من برای حل این مساله