এই সমস্যাটি sparse table এবং segment tree ব্যবহার করে সমাধান করা যায়।

ধর একজন শিক্ষার্থী A, যে বিন্দুতে যাত্রা শুরু করে সর্বচ্চ ১৬ বিন্দুতে শেষ করতে পারে।
আরেকজন শিক্ষার্থী B, যে ১০ বিন্দুতে শুরু করে সর্বোচ্চ ২০ বিন্দুতে শেষ করতে পারে।
আরেকজন শিক্ষার্থী C, যে বিন্দুতে শুরু করে সর্বচ্চ ৩০ বিন্দুতে শেষ করতে পারে।

এখন তুমি যদি A কে নিয়ে শুরু কর, তাহলে A এর পরে তুমি কাকে নেবে? B নাকি C কে?
উত্তর হল C কে। কারণ সে সবচেয়ে পরে শেষ করতে পারে।

এভাবে, কে কার পরে দৌড় শুরু করলে কম সংখ্যক শিক্ষার্থী দিয়ে দৌড় সম্পন্ন হবে, এটা নির্ণয়ের জন্য একটি segment tree তৈরি করতে হবে, যেখানে তুমি query করতে পারবে, A এর রেঞ্জ (৫ - ১৬) এর মধ্যে কে দৌড় শুরু করে সবচেয়ে পরে দৌড় শেষ করতে পারে।


এভাবে, তুমি যদি জানো একটা দৌড় কাকে দিয়ে শুরু করাবে, তাহলে তার পরে কে এবং তার পরে কে দৌড়াবে নির্ণয় করে তুমি O(n log n) complexity তে নির্ণয় করতে পারবে একটা দৌড় সম্পন্ন করতে সর্বনিম্ন কত জন লাগবে। আর অবশ্যই তাকে দিয়েই তুমি দৌড় শুরু করাবে যে দৌড়ের প্রথম বিন্দু থেকে শুরু করে এবং সবচেয়ে বেশি দৌড়াতে পারে।

কিন্তু সমস্যাটি- সমাধান করতে আরও ভাল complexity দরকার। এই জন্য তোমাকে একটি sparse tree তৈরি করতে হবে, যেখান থেকে তুমি নির্ণয় করতে পারবে, তুমি যদি A কে দিয়ে দৌড় শুরু কর তাহলে 2x2^{x} জন শিক্ষার্থী ব্যবহার করে তুমি সর্বচ্চ কত দূর যেতে পার। এই sparse table এর প্রথম কলামটি তুমি আগের segment tree থেকে তৈরি করে নিতে পার। এভাবে একটা দৌড় এর জন্য তুমি O(log n) complexity থে হিসাব করতে পারবে।

Statistics

64% Solution Ratio
Um_nikEarliest, Jun '21
user.233155Fastest, 0.0s
Deshi_TouristLightest, 21 MB
user.233155Shortest, 1701B
Toph uses cookies. By continuing you agree to our Cookie Policy.