چهارشنبه, مهر 18. 1386
Paratroopers
توضيح و بررسی راه حل: ابتدا برای ساده تر کردن مساله، به جای کمينه کردن حاصل ضرب هزينه ها، لگاريتم حاصل ضرب هزينه ها را کمينه می کنيم. در نتيجه مساله تبديل می شود به: زيرمجموعه ای از اين تفنگ ها را انتخاب کنيد به طوری که تمام درختان را قطع کنند و حاصل جمع لگاريتم هزينه ها را کمينه شود. پس می خواهيم عبارت زير را کمينه کنيم:
و در انتها جواب مساله ی اصلی برابر خواهد بود با:
خوب، برای حل کردن اين مساله، گرافی به شکل زير می سازيم:
که در گراف بالا r1 … r6 متناظر با سطرها می باشند و c1 … c9 متناظر با ستون ها می باشند. از s به هر کدام از سطرها يالی وصل می کنيم که وزن اين يال برابر با لگاريتم هزينه ی تفنگ آن سطر می باشد، و از هر کدام از ستون به t يالی وصل می کنيم که وزن اين يال برابر با لگاريتم هزينه ی تفنگ آن ستون می باشد. همچنين بين ri و cj يالی به وزن بی نهايت متصل می کنيم در صورتيکه در مکان [i,j] جدول درختی موجود باشد.
همچنين عمل انتخاب تفنگ يک سطر را متناظر با حذف کردن يال بين s و آن سطر در نظر می گيريم و عمل انتخاب تفنگ يک ستون را متناظر با حذف کردن يال بين آن ستون و t در نظر می گيريم.
حالا انتخابی از تفنگ ها را در نظر بگيريد که تمام درخت ها را قطع کند. خاصيت اين انتخاب چيست؟ خاصيت اين انتخاب اين است که به ازای هر يال ri به cj (که متناظر با يک درخت می باشد) بايد حداقل يکی از يال های s به ri (که متناظر با تفنگ سطر می باشد) و cj به t (که متناظر با تفنگ ستون می باشد) حذف شده باشد (که متناظر با انتخاب شدن آن تفنگ می باشد). نتيجه ی اين عمل چيست؟ نتيجه ی اين عمل اين است که هيچ مسيری از s به t وجود نخواهد داشت که از اين يال ri به cj عبور کند (چون فقط يک مسير اين چنين داشتيم، و حال با حذف حداقل يک يال از آن، اين تنها مسير را هم از بين می بريم.)
پس اگر بخواهيم تمام درخت ها را از بين ببريم، نبايد هيچ مسيری بين s و t باشد.
بنابراين مساله ی ما تبديل شد به حذف کردن تعدادی از يال های گراف مذکور به طريقی که هيچ مسيری بين s و t نباشد و مجموع وزن های اين يال های انتخاب شده کمينه باشد. اين جمله شما را به ياد چه مساله ی مشهوری می اندازد؟
احتمالا اکثر شما با مساله ی مشهور Minimum Cut آشنا هستيد. اگر آشنا نيستيد:
مساله ی Minimum Cut: می خواهيم تعدادی از يال های يک گراف را حذف کنيم به طوری که هيچ مسيری بين مبدا و مقصد نباشد و مجموع هزينه های يال های حذف شده می نيمم باشد.
و اگر با روش حل اين مسال آشنا نيستيد، بايد عرض کنم که جواب اين مساله (کمترين هزينه) با جواب مساله ی Maximum Flow يکی می باشد. اگر با اين مساله و طريقه ی حل آن آشنا نيستيد، به لينک 1 و لينک 2 مراجعه کنيد.
بنابراين برای حل کردن مساله، پس از ساختن گراف مذکور، با يکی از الگوريتم های معروف Maximum Flow، جواب مساله را بدست می آوريم! به همين سادگی و زيبايي!
سه شنبه, اردیبهشت 25. 1386
Ivan and the bugs
امروز به بررسی مساله Collecting Bugs که یکی از سوالات ACM/ICPC 2004 NEERC Northern Subregional و همچنین یکی از سوالات آخرین مسابقه هفتگی ما بود می پرازم.
صورت سوال: n نوع شیء آبی و از هر کدام به اندازه ی بی نهایت و s نوع شیء زرد و از هر کدام به اندازه ی بی نهایت داریم. هر روز یک شیء آبی و یک شیء قرمز را به تصادف انتخاب می کنیم. هنگامی که از هر نوع شیء آبی حداقل یکی و هر نوع شیء قرمز حداقل یکی انتخاب کرده باشیم دیگر ادامه نمی دهیم. می خواهیم امید ریاضی تعداد روزهایی که به آخر کار می رسیم را پیدا کنیم.
طبق تجربه، در چنین مواردی که حداکثر تعداد روزها معلوم نیست، نباید به راه حلی که به ازای هر مقداری احتمال رخداد آن را حساب کرد و جمع حاصل ضرب مقادیر در احتمالات نتیجه را حساب کرد. و باز هم طبق چندین سوال احتمالاتی که تا حالا دیده ام، این گونه مسائل اکثر با برنامه سازی پویا قابل حل شدن می باشند. برای آشنایی و یادگیری بیشتر در باره ی مسائل احتمالاتی در مسابقات برنامه نویسی و دیدن چندین مثال دیگر به مقاله ی Understanding Probabilitiesسایت Topcoder مراجعه کنید.
فرض کنید Fi,j امید ریاضی حالتی باشد که در آن تعداد اشیاء آبی که تا به حال هیچ وقت انتخاب نشده اند i و تعداد اشیاء قرمز که تا به حال هیچ وقت انتخاب نشده اند برابر j باشد. چندین حال برای جفت i و j داریم:
1- i = 0 و j = 0: در این صورت دیگر لازم نیست هیچ روزی ادامه دهیم و جواب برابر با 0 خواهد بود.
2- i = 0 و j != 0: به هر حال باید یک روز انتخاب را انجام دهیم. در این روز به احتمال j/s شیء زردی که قبلا هیچ وقت انتخاب نکردیم را انتخاب می کنیم و در روز های بعد باید با j-1 شی انتخاب نشده ی زرد ادامه دهیم، و با احتمال s-j)/s) یکی از اشیاء زردی را که قبلا انتخاب کردیم را انتخاب می کنیم و در روز های بعد باید با j شی انتخاب نشده ی زرد ادامه دهیم. بنابراین Fi,j در این حالت برابر خواهد بود با:
که با ساده کردن معادله ی بالا برای F0,j بدست می آوریم:
3- حالت سوم وقتی i != 0 و j = 0. با استدلالی مشابه حالت قبلی برای این حالت بدست خواهیم آورد:
4- حالتی که i != 0 و j != 0: در این صورت با احتمال i/n \* j/s شیء آبی جدید و شیء زرد جدیدی انتخاب خواهیم کرد، با احتمال n-i)/n \* j/s) شیء زرد جدید انتخاب خواهیم کرد ولی شیء آبی جدیدی انتخاب نمی کنیم، ... که در این صورت Fi,j برابر خواهد بود با:
که با ساده کردن معادله ی بالا خواهیم داشت:
و کد من برای حل این مساله:
- #include <iostream>
- #include <string>
- #include <iomanip>
- usingnamespace std;
- int n, s;
- double mat[1002][1002];
- int main()
- {
- cin>> n >> s;
- for(int i = 0; i <= n; i++)
- for(int j = 0; j <= s; j++)
- if(i == 0&& j == 0)
- mat[i][j] = 0;
- elseif(i == 0)
- mat[i][j] = mat[i][j-1] + (double)s / j;
- elseif(j == 0)
- mat[i][j] = mat[i-1][j] + (double)n / i;
- else
- {
- mat[i][j] = 1 + (mat[i-1][j-1] \* (double)(i \* j) +
- mat[i-1][j] \* i \* (double)(s - j) +
- mat[i][j-1] \* (double)(n - i) \* j) / (double)(s \* n);
- mat[i][j] /= 1 - (double)(n - i) \* (double)(s - j) / (s \* n);
- }
- cout.precision(4);
- cout.setf(ios::fixed | ios::showpoint);
- cout<< mat[n][s]<< endl;
- return0;
- }
At the data-structure department of Macrohard!
امروز به بررسی مساله ی 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(log2 n پاسخ داد. در نتیجه با استفاده از پاسخ این پرسش و جستجوی دودوئی می توان هر پرسش را در زمان (O(log3 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(log2 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
- elseif[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 های مربوط به یک آرایه. برای تمرین بیشتر توصیه می کنم مسائل ساده تر زیر را نیز حل کنید:
- Unreal Story : که البته این سوال یک راه حل خیلی ساده تر و تمیزتر هم دارد. ولی به هر حال آن را می توان با این روش نیز حل کرد.
سه شنبه, فروردین 14. 1386
Base -1 + i
با استفاده از 1- + i به عنوان مبنای دستگاه اعداد، که در آن i برابر با می باشد، تمام اعداد صحيح مختلط (اعدادی که دارای يک قسمت حقيقی و يک قسمت موهومی می باشند) را می توان به صورت اعداد بدون علامت متشکل از دنباله ای از يک و صفر نمايش داد. و اين [...]
می باشد، تمام اعداد صحيح مختلط (اعدادی که دارای يک قسمت حقيقی و يک قسمت موهومی می باشند) را می توان به صورت اعداد بدون علامت متشکل از دنباله ای از يک و صفر نمايش داد. و اين نمايش برای هر عددی يکتا می باشد. در ادامه به اثبات اين قضايا نخواهيم پرداخت، بلکه به توضيح مختصری درباره ی اين مبنا و روش بدست آوردن نمايش معادل يک عدد در اين دستگاه اعداد خواهيم پرداخت.qi = (-a - b + r) / 2
در ادامه از روش بالا برای پيدا کردن نمايش عدد 2 در اين مبنا استفاده می کنيم:
مرحله ی اول: a = 2 و b = 0. در نتيجه qr = -1 و qi = -1 و r = 0.
مرحله ی دوم: a = -1 و b = -1. در نتيجه qr = 0 و qi = 1 و r = 0.
مرحله ی سوم: a = 0 و b = 1. در نتيجه qr = 1 و qi = 0 و r = 1.
مرحله ی چهارم: a = 1 و b = 0. در نتيجه qr = 0 و qi = 0 و r = 1.
مرحله ی پنجم: a = 0 و b = 0. پايان!
اگر باقيمانده ها را پشت سر هم بگذاريم، نتيجه را که برابر 1100 می باشد را بدست می آوريم.
يادداشت: منبع مطالبی که خوانديد، کتاب Hacker’s Delight از انتشارات Addison Wesley می باشد. علت اينکه اين بخش از کتاب توجه مرا جلب کرد اين بود که اين مطلب مرتبط با سوال UVa #11180 می باشد که قبلا با همکاری هم تيمی های عزيز با استفاده از يک راه حل ديگر حل کرده بوديم، ولی روش ما به سادگی اين روش نبود. البته اين نشان گر اين است که اگر روابط مربوط به مساله را با دقت بررسی کنيم، معمولا به راحتی به راه حل های ساده تر و تميز تر می رسيم.
روشی که ما استفاده کرده بوديم، حاصل از بررسی توان های مختلف 1- + i و Pattern هايي بود که در آن وجود داشت.
چهارشنبه, فروردین 8. 1386
Histograms - Part 1
"يک سری مستطيل با عرض واحد و ارتفاع های مختلف داريم که کنار هم قرار گرفته اند. الگوريتمی پيشنهاد دهديد که مساحت بزرگترين مستطيلی که درون اين مستطيل ها جا می شود را پيدا کند."
فرض کنيد می خواهيم جواب را برای مستطيل a-ام تا b-ام پيدا کنيم. اين مستطيل ها را از وسط به دو قسمت تقسيم می کنيم. جواب يا کاملا در قسمت سمت چپ است يا کاملا در قسمت سمت راست يا اينکه قسمتی از آن در سمت راست است و قسمتی از آن در سمت چپ. دو حالت اول را به صورت بازگشتی پيدا می کنيم و برای پيدا کردن بهترين جواب در حالت سوم، به روش زير عمل می کنيم:
در هر مرحله مستطيل را با ارتفاع جاری گسترش می دهيم. حالا، از سمت چپ و راست به دو مستطيل مختلف مماس می شود. ارتفاع جاری را به ماکزيمم ارتفاع اين دو مستطيل تغيير می دهيم و ادامه می دهيم. در هر مرحله مساحت مستطيل جاری را پيدا کرده و جواب را بروز می کنيم. اين کارها را تا زمانی انجام می دهيم که از سمت چپ به مستطيل a-ام و از سمت راست به مستطيل b-ام برسيم.
برای اينکه منظور من را دقيق تر بفهميد، به pseudo-code زير توجه کنيد:
function FindLargestRectangle(a, b):
if a == b:
return Heights[a]
mid = (a+b) / 2
Result = max(FindLargestRectangle(a, mid), FindLargestRectangle(mid+1, b))
Left = mid
Right = mid+1
CurrentHeight = min(Heights[Left], Heights[Right])
while Left != a or Right != b do:
if Left == a:
# We cannot go to left anymore
Right += 1
CurrentHeight = min(CurrentHeight, Heights[Right])
elif Right == b:
# We cannot go to right anymore
Left -= 1
CurrentHeight = min(CurrentHeight, Heights[Left])
elif Heights[Left-1] >= CurrentHeight:
# We can go to Left with CurrentHeight
Left -= 1
elif Heights[Right+1] >= CurrentHeight:
# We can go to right with CurrentHeight
Right += 1
else:
# Choose the next CurrentHeight
CurrentHeight = max(Heights[Left-1], Heights[Right+1])
Result = max(Result, (Right - Left + 1) * CurrentHeight)
end
return Result
print FindLargestRectangle(0, len(Heights)-1)
رابطه ی بازگشتی زمان اين الگوريتم:
که اگر آن را حل کنيم، بدست می آوريم که پيچيدگی زمانی اين الگوريتم از مرتبه ی ((O(n*log(n می باشد.
Me
Me = {
"Name": "Hadi",
"Job": "Programmer",
"Hobbies": [
"Thinking",
"Reading",
"Walking",
"Living" ],
... }
Favorite Links
Friends
Categories
Syndicate This Blog
Blog Administration
Powered by
