المپیاد ساختار داده ها (Data Structures)

[daneshvar.amrollahi]

سلام. احساس کردم تاپیکی برای مطلب ساختار داده ها نداریم. ساختمش. چون برای برنامه نویسی تو المپیاد کامپیوتر مهمه.

اولین سوال هم می پرسم: ساختار داده ای طراحی کنید که برای بزرگترین عدد از بین i-j تا i را با اردر 1 جواب دهد. محدوده ی عدد ها از 1 تا n هستش و n خیلی برزگ نیست. یعنی میشه حافظه ی n تا یی گرفت.

 

[rezaezio]

پاسخ : ساختار داده ها (Data Structures)

سوال رو دقیق‌تر بگو ! j عدد ثابته الان ؟

 

[daneshvar.amrollahi]

پاسخ : ساختار داده ها (Data Structures)

سوال رو دقیق‌تر بگو ! j عدد ثابته الان ؟

آره j یه عدد ثابت هستش. در واقع صورت کلی تر سوال اینه: n تا عدد بهمون میدن. بعدش یه عدد تابت j ورودی میدهند. بعدش m تا سوال ازمون می پرسن که هر سوال یه عدد i بهمون ورودی میده. ما باید بزگترین عدد بین بازه ی i-j تا i رو با اردر ۱ جواب بدیم.

میشه همچنین ساختار داده طراحی کرد؟ اگر آره بگید چحوری...

 

[rezaezio]

پاسخ : ساختار داده ها (Data Structures)

ببین با پیش‌پردازش (O(n و حافظه (O(n میشه واسه هر i، عدد خواسته شده رو پیدا کرد و توی یک آرایه ریخت ! حالا هر کوئری رو از (O(1 میشه جواب داد.
راهنمایی : از داده‌ساختار deque استفاده میشه!
سوال E. Watching Fireworks is Fun هم با استفاده از همین داده ساختار حل میشه !

 

[daneshvar.amrollahi]

پاسخ : ساختار داده ها (Data Structures)

ببین با پیش‌پردازش (O(n و حافظه (O(n میشه واسه هر i، عدد خواسته شده رو پیدا کرد و توی یک آرایه ریخت ! حالا هر کوئری رو از (O(1 میشه جواب داد.
راهنمایی : از داده‌ساختار deque استفاده میشه!
سوال E. Watching Fireworks is Fun هم با استفاده از همین داده ساختار حل میشه !

یه چیزایی به ذهنم میاد نمیدونم درسته یا نه. برای تولید اون ارایه نهایی (اسمش رو بذاریم ans) که بتونیم با اون با اردر ۱ به سوالات جواب بدیم، این رابطه بازگشتی به ذهنم میرسه:

ans[i] = max(ans[i-j+1],a[i])

میشه دی پی اجراش کرد. اما اصلا درسته این رابطه؟ یعنی با این رابطه داریم هر سری ۱ دونه ۱ دونه میریم جلو (آغاز از خانه j+1 ام - j خانه ی اول قبلا مقدار دهی اولیه شده اند) و جواب اون سوال رو می سازیم برای همه ی i ها. بعدش آخر کار میریم راحت با اردر ۱ جواب میدیم.

 

[rezaezio]

پاسخ : ساختار داده ها (Data Structures)

نه خُب واضحه این غلطه ! به دو دلیل، اول این که از deque استفاده نکردی دوم اینکه هر مثالی بزنی این آرایه ای که پر میکنی اشتباهه واسش ! یعنی اصن درک نمیکنم منطق این رابطه بازگشتی رو

 

[daneshvar.amrollahi]

پاسخ : ساختار داده ها (Data Structures)

نه خُب واضحه این غلطه ! به دو دلیل، اول این که از deque استفاده نکردی دوم اینکه هر مثالی بزنی این آرایه ای که پر میکنی اشتباهه واسش ! یعنی اصن درک نمیکنم منطق این رابطه بازگشتی رو

از dequeue که معلوم بود استفاده نکردم! اما حس کردم شاید بدون اون هم بشه! منطقش هم اینطوری به ذهنم اومد: مثلا فرض کنید j = 4 هستش. ۴ تا خونه ی متوالی رو درنظر بگیرید. هر سری یدونه شیفت میدیم راست. میخوایم هر دفعه که شیفت دادیم بیایم بزرگترین توی بازه ی جدید تولید شده (شیفت داده شده) رو پیدا کنیم. دیدم که یه عنصر i امی داره اضافه میشه که ممکنه ماکسیمم باشه. پس ماکسیمم گرفتمش با بهترین حالتی که تا قبل پیدا شده بود!

شبیه این نیست؟

 

[Anita H]

پاسخ : ساختار داده ها (Data Structures)

این درسته؟
http://paste.ubuntu.com/9428497/
توضیح میخاد؟

سوال قشنگیه

 

[daneshvar.amrollahi]

پاسخ : ساختار داده ها (Data Structures)

این درسته؟
http://paste.ubuntu.com/9428497/
توضیح میخاد؟

سوال قشنگیه

آره یه توضیحی بده لطفا!

 

[rezaezio]

پاسخ : ساختار داده ها (Data Structures)

این درسته؟
http://paste.ubuntu.com/9428497/
توضیح میخاد؟

سوال قشنگیه

توضیح می‌خواد!

اینم کد من، امیدوارم درست زده باشم. ؛؛)
http://paste.ubuntu.com/9431468/

 

[Anita H]

پاسخ : ساختار داده ها (Data Structures)

آقا من توضیح دادن بلد نیستم
اولن واضحه که خونه ی اول هر کدوم از pair های D یه عدد از آرایه A هست
ثانین فرض میکنیم جمع خونه های دوم هر کدوم از Pair های D برابر j هست!
وقتی فور توی مرحله ی i ام هست خونه های i – j تا i ام آرایه ی A رو در نظر بگیر؛ توی این مرحله از فور، مولفه های اول D توی همین بازه هستن، حالا مولفه های دوممون چین؟ فرض کن توی یه خونه از D عدد A[k] رو ذخیره کرده باشیم. مولفه ی دوم این pair، ماکزیمم عدد x هست به طوری که:

Max( a[i], a[i – 1], …, a[k], a[k - 1], ..., a[k - x] ) = a[k]		( x <= j - i + k )

همه دستورات توی for برای آپدیت کردن این دیکیو ئه هستن!
ans[ i] با این فرض که توی مرحله ی i ام for هستیم، برابر یکی از خونه های ابتدایی یا انتهایی(بسته به مدل پر کردنمون) D هستش

پ.ن: یه جوری توضیح دادم علاوه بر این که هیچی نفهمید، جرئت سوال کردنم نداشته باشید