ICPC Dhaka Preli 2017: Problem D - Connecting To One solution

সমস্যাঃ

$N$ নোড ও $E$ এজ বিশিষ্ট একটি গ্রাফ দেয়া আছে, যার প্রতিটা এজের ওয়েট (cost) বলে দেয়া আছে ।

এরপরে $Q$ সংখ্যক কুয়েরি দেয়া আছে । প্রতিটা কুয়েরিতে একটি নাম্বার $C$ দেয়া আছে । বলতে হবে, যেসব এজের ওয়েট $C$ এর কম, সেই এজগুলিকে যদি গ্রাফ থেকে মুছে দেয়া হয়, তবে ১ নাম্বার নোড থেকে কতগুলি নোডে যাওয়া সম্ভব ।

Constraints:

1. ইনপুটে সর্বোচ্চ ১০ টি টেস্ট কেস দেয়া থাকবে ।
2. $1\leq \space N \space \leq 40,000 $
3. $1\leq \space E \space \leq 150,000 $
4. $1\leq \space |W| \space \leq 10^9 $, W বলতে এজের ওয়েট বুঝানো হচ্ছে ।
5. $1\leq \space Q \space \leq 10^5 $
6. $1\leq \space |C| \space \leq 10^9 $

সমাধানঃ

আমরা কোন গ্রাফ তৈরি করব না । 

এজগুলি ইনপুট নিয়ে ওয়েটের Descending order এ সর্ট করব ।

এরপরে সবগুলো কুয়েরি ইনপুট নিয়ে তাদেরকেও Descending order এ সর্ট করব । এরপরে আমরা কুয়েরি গুলি অফলাইনে প্রসেস করব । এক্ষেত্রে পরে যেহেতু আমাদের কুয়েরির ইন্ডেক্স প্রয়োজন হবে, তাই ইন্ডেক্স সহ রেখে ( যেমন pair<int, int> হিসেবে ) সর্ট করতে হবে ।

এখন সর্ট করা এজগুলি থেকে একটি করে এজ নিয়ে ঐ এজের নোড দুটিকে ডিসজয়েন্ট সেটে যুক্ত করব। সাথে এখন পর্যন্ত সেটে রাখা এজগুলির মাঝে সবচেয়ে কম ওয়েট কত তা একটি ভেরিয়েবলে (minCost) রাখব ।

আর পাশাপাশি সর্টেড কুয়েরি লিস্টের কোন কুয়েরিকে প্রসেস করছি, তার ইন্ডেক্স একটা ভেরিয়েবলে (curQ)রাখব ।

প্রতিটা এজ থেকে নোড দুটিকে ডিসজয়েন্ট সেটে যুক্ত করার পরে যদি এই এজের ওয়েট টা minCost এর চেয়ে ছোট হয়, তবে minCost এর ভ্যালুকে এই ওয়েট দিয়ে আপডেট করব ।

এরপরে দেখব, যদি minCost এর ভ্যালু curQ তম কুয়েরি তে C এর মান এর চেয়েও ছোট হয়, তবে যতক্ষণ curQ < Q এবং minCost বর্তমান যে কুয়েরিকে প্রসেস করছি তার C এর মানের চেয়ে ছোট হয়, ততক্ষণ curQ এর মান কে 1 করে বাড়াব, মানে কুয়েরির ইন্ডেক্স কে এক বাড়াব এবং আরো ডানে যাব ।

কেন ?

কারণ, এখন পর্যন্ত যুক্ত করা এজ গুলির মাঝে সর্বনিম্ন ওয়েট হলো minCost.

কিন্তু যেসব কুয়েরিতে এর চেয়েও বড় ওয়েট(C) দিয়ে কুয়েরি করা হয়েছে, সেখানে C এর চেয়ে ছোট সব এজ গ্রাফ থেকে মুছে যাবে । তাই কুয়েরির জন্য উত্তর হবে ০ (শুণ্য) । যেহেতু কুয়েরি গুলিকে Descending order এ সাজানো আছে, তাই C এর চেয়ে ছোট ভ্যালু দিয়ে কুয়েরি করা হয়েছে সেরকম কুয়েরি পেতে আমাদেরকে আরো ডান দিকে যেতে হবে ।

১ম যে পজিশনে কুয়েরির ভ্যালু(C), minCost এর চেয়ে ছোট বা সমান হবে, সেই কুয়েরির উত্তর হবে আমাদের ১ নাম্বার নোডের সাথে যুক্ত থাকা নোড গুলোর সেটের সাইজ ।

curQ তম ইন্ডেক্সের ans যত, যতক্ষণ curQ কে বাড়াচ্ছি, তার মাঝের এই ইন্ডেক্স গুলির ans ও হবে তাই ।

তাই তাদের ans কেও আপডেট করে দেব ।

কেন ?

কারণ, ৬ এর চেয়ে ছোট ওয়েটের এজ ডিলেট করলে ans যত হবে ৫ এর চেয়ে ছোট এজগুলিকে ডিলেট করলেও ans হয় তাই হবে, না হয় তার চেয়ে বেশি হবে, কিন্তু কম হবে না কখনো । কিন্তু এখানে মাঝের এসব ইন্ডেক্সের জন্য ans  বেশি হতে পারবে না, কারণ তাদের কুয়েরির ভ্যালু minCost এর চেয়ে ছোট না । 

১ম যেই কুয়েরি ইন্ডেক্সের ভ্যালু minCost এর চেয়ে ছোট বা সমান হবে সেই কুয়েরিতে এই বাড়তি এজ টা থাকতে পারবে । তার আগের গুলোতে এই জন্য আগের কুয়েরির ans টাই থাকবে । ans রাখার সময় কুয়েরি এর অরিজিনাল ইন্ডেক্সে ans টা ব্যবহার করে সেই ইন্ডেক্সে ans টা রাখব ।

এই অংশটা বুঝতে একটু খাতা কলম নিয়ে বসতে হবে, একটু চিন্তা করতে হবে । আর তাও না বুঝলে কমেন্টে জানালে আমি ব্যাখ্যা করব ।

সব এজ গুলোকে প্রসেস করা হয়ে গেলে আমাদের সব কুয়েরির জন্য ans পেয়ে যাব ।

এরপরে শুধু প্রতি টা কুয়েরির ans ইনপুট এর অর্ডারে প্রিন্ট করব - ব্যাস হয়ে গেল !!

কমপ্লেক্সিটি :  $O(E log E + Q log Q)$

কোডঃ

Read More

[tutorial] SPOJ QUEEN - Wandering Queen solution

Problem description:

n x m সাইজের একটি দাবার বোর্ড আছে । বোর্ডে একটি Queen (মন্ত্রী) এর বর্তমান পজিশন ও টার্গেট পজিশন দেয়া আছে । বোর্ডে বিভিন্ন cell এ 4 ধরণের ক্যারেকটার আছে - 

1) S দিয়ে বুঝানো হয়েছে Queen (মন্ত্রী) এর starting পজিশন, 

2) F দিয়ে বুঝানো হয়েছে Queen (মন্ত্রী) এর Final পজিশন, 

3) .(dot) বুঝানো হয়েছে ফাকা cell, যেখানে মুভ দেয়া যাবে ।

4) X দিয়ে বুঝানো হয়েছে নিষিদ্ধ cell ।

আউটপুটে বলতে হবে, Queen টা মিনিমিমাম কতটা মুভ দিয়ে starting cell থেকে final পজিশনে যেতে পারবে ।

Problem Link

সমাধান:

Queen যে কোন cell থেকে ৮ দিকে মুভ দিতে পারে এবং একটি মুভে যে কোন দিকে যত দূর ইচ্ছা যেতে পারে, যতক্ষণ না কোন নিষিদ্ধ cell না পায় ।

যদি কোন Queen (x, y) পজিশনে থাকে, তবেঃ

 ১) সে ডান দিকে (x, y+1), (x, y+2), (x, y+3), ... এভাবে (x, m-1) পজিশন পর্যন্ত যে কোন  cell এ যেতে পারে, যতক্ষণ  না কোন নিষিদ্ধ cell পায় ।

 ২) সে বাম দিকে (x, y-1), (x, y-2), (x, y-3), ... এভাবে (x, 0) পজিশন পর্যন্ত যে কোন  cell  এ যেতে পারে, যতক্ষণ  না কোন নিষিদ্ধ cell পায় ।

 ৩) সে উপর দিকে (x-1, y), (x-2, y), (x-3, y), ... এভাবে (0, y) পজিশন পর্যন্ত যে কোন  cell  এ যেতে পারে, যতক্ষণ  না কোন নিষিদ্ধ cell পায় ।

 ৪) সে নিচ দিকে (x+1, y), (x+2, y), (x+3, y), ... এভাবে (n-1, y) পজিশন পর্যন্ত যে কোন  cell এ যেতে পারে, যতক্ষণ  না কোন নিষিদ্ধ cell পায় ।

 ৫) সে lower right corner বরাবর (x+1, y+1), (x+2, y+2), (x+3, y+3), ... এভাবে যতক্ষণ  না board এর বাইরে চলে যায় বা নিষিদ্ধ cell পায়, যে কোন  cell এ যেতে পারে ।

 ৬) সে lower left corner বরাবর (x+1, y-1), (x+2, y-2), (x+3, y-3), ... এভাবে যতক্ষণ  না board এর বাইরে চলে যায় বা নিষিদ্ধ cell পায়, যে কোন  cell এ যেতে পারে ।

 ৭) সে upper right corner বরাবর (x-1, y+1), (x-2, y+2), (x-3, y+3), ... এভাবে যতক্ষণ  না board এর বাইরে চলে যায় বা নিষিদ্ধ cell পায়, যে কোন  cell এ যেতে পারে ।

 ৮) সে upper left corner বরাবর (x-1, y-1), (x-2, y-2), (x-3, y-3), ... এভাবে যতক্ষণ  না board এর বাইরে চলে যায় বা নিষিদ্ধ cell পায়, যে কোন  cell এ যেতে পারে ।

তাহলে আমরা প্রতি মুভে কারেন্ট পজিশন থেকে ৮ দিকে যত গুলো possible মুভ দেয়া সম্ভব তা এক চালেই দিতে পারি ।

এজন্য আমরা যে cell এ S আছে, সেখান থেকে একটি BFS চালাতে পারি । এখান থেকে এক মুভ দিয়ে ৮ দিকে যে সব cell এ যাওয়া সব cell গুলোকে Queue তে push করে রাখব । শুধু ৮ দিকের adjacent cell গুলো নয়, যত গুলো cell এ যাওয়া যায়, সবগুলোকেই Queue তে পুশ করে রাখব ।

এরপরে সেই একই কাজ । প্রতিবার Queue এর front cell টা নেব, এবং সেখান থেকে এক মুভ দিয়ে ৮ দিকে যে সব cell এ যাওয়া সব cell গুলোকে Queue তে push করে রাখব ।

যখন Target cell পাব, তখন তার distance রিটার্ণ করে দেব ।

কিন্ত এখানে একটি ঝামেলা আছে, তা হলো visited cell কে কন্ট্রোল করা । 

কিরকম ঝামেল ? একটা উদাহরণ দেই - 

উপরের চিত্রে, ৮ x ৮ সাইজের একটি দাবা বোর্ড দেখানো হয়েছে । ডান দিকে row এর নাম্বার, আর নিচে column এর নাম্বার দেয়া আছে ।

মনে কর, শুরুতে Queen টি (৪, ৩) পজিশনে আছে । এখান থেকে সে এক মুভে লাল রেখা চিহ্নিত ঘরগুলোর যে কোন ঘরে যেতে পারে ।

ধর, সে ডান দিকে (৪, ৪) পজিশনে গেল । এখান থেকে নীল রেখা চিহ্নিত ঘরগুলোর যে কোন ঘরে যেতে পারে ।

খেয়াল কর, আমি বামে বা ডানে রেখা টানিনি । কারণ, বামে এবং ডানে সব ঘরই visited হয়ে আছে ।

কিন্তু, (৪, ৫) ঘরটি আগে visited হলেও আবার visit করেছে, কারণ তার নিচের ঘর গুলো এখনো unvisited আছে । সে গুলো visit করতে হলে (৪, ৫) ঘরের উপর দিয়ে নিচে যেতে হবে ।

তাহলে, ব্যাপার টা কী দাড়ালো ? কোন ঘর visited হলেই থামা যাবে না । আবার কোন দিকে সব ঘরই visited হয়ে থাকলে আর visit করে লাভ নেই, এতে করে শুধু শুধু সময় বেশি নেবে ।

আর শুধু একটি ঘর visited দেখলেও যেহেতু থামা যাবে না, এতে করে আসলে প্রতি বারই visited ঘর গুলো আবার visit করতে হচ্ছে, এতে করে টাইম কমপ্লেক্সিটি বাড়ছে, এমন কি ইনফিনাইট লুপেও পড়ে যেতে পারে ।

তাহলে সারমর্ম এই দাড়ালো যে, visited ঘর পেলেই যদি থামি, তবে এর পরের ঘর গুলো visit করা হচ্ছে না, আর visited ঘর পাওয়া সত্ত্বেও visit করতেই থাকলে টাইম কমপ্লেক্সিটিতে কুলাবে না, বা ইনফিনাইট লুপে পড়ে যাবে ।

তাহলে এর থেকে মুক্তির উপায় কী ?

উপায়টা হলো, ঐ যে বললাম, যদি সব ঘরই ভিজিট হয়ে থাকে, তাহলে ভিজিট করার দরকার নেই । যেমন, (৪, ৪) থেকে বামে আর ডানে যাইনি ।

কিন্তু কিভাবে বুঝব, ঐ বরাবর সব ঘরই ভিজিট করা আছে কিনা ?

খেয়াল কর, কোন রো বামে বা ডানে থেকে visit করা একই কথা, কারণ বাম থেকে ডানে যত গুলো ঘরে যাওয়া যাবে, ডান থেকে বামে তত গুলো ঘরেই যাওয়া যাবে ।

একই ভাবে, কোন কলাম উপরে বা নিচে থেকে visit করা একই কথা, কারণ উপরে থেকে নিচে যত গুলো ঘরে যাওয়া যাবে, নিচ থেকে উপরেও তত গুলো ঘরেই যাওয়া যাবে ।

একই কথা কোণাকুনি যাবার ক্ষেত্রেও প্রযোজ্য ।

তাহলে, কোন ঘর ভিজিট করার দিক ৮ নয়, আসলে ৪ ।

১) বাম-ডান বরাবর,

২) উপর-নিচ বরাবর,

৩) কোণাকুনিভাবে upper left বা lower right বরাবর,

৪) কোণাকুনিভাবে upper right বা lower left বরাবর ।

তাহলে, কোন ঘর visit করার সময় যদি আমরা visited array তে ঘরটি কোন দিক থেকে visited হয়েছে, এই তথ্য রাখি তবেই সমস্যাটির সমাধান হয়ে যাবে ।

যেমন, আমরা (৩, ৪) থেকে যখন বামে বা ডানে কোন ঘর visit করেছি, তখন ঐ ঘরটি ১ নাম্বার উপায়ে visit করা হয়েছে এটা রেখে দিলাম । তাহলে পরবর্তীতে আর ১ নাম্বার উপায়ে এর কোন ঘর visit করব না ।

উদাহরণ হিসেবে ধর, আমরা visited array টা এভাবে নিলামঃ bool visited[1005][1005][5];

তাহলে, (৩, ৪) থেকে ডানের যে কোন ঘর (p, q) ভিজিট করার সময় visited[p][q][1] = 1; করে দেব । এরপরে, (৪, ৪) থেকে যখন ডানে (৪, ৫) ভিজিট করতে চাইব, তখন আগেই দেখব visited[4][5][1] = 1 কিনা । যদি 1 হয়ে থাকে, তার মানে এই ঘরটি বাম-ডান বরাবর visit করাই আছে । তাই আর visit করব না।

আর BFS এর শুরুতেই আমরা starting cell এর ৪ টা দিক বরাবরই visited array এর মান 1 করে দেব, কারণ, starting cell থেকে ১ম বারই ৪ দিকের সব cell ভিজিট করব । তাই এই cell এ আর আসার দরকার নেই ।

Code:

Read More