Monday, September 29, 2014

Game Theory ( Sprague Grundy Theorem )


 Sprague Grundy আসলে Nim game এর এই একটা variant . Nim Game এ কি থাকে অনেক গুলা পাইপ/বাক্স এমনসব জিনিস একটা row তে থাকে এবং তাদের মধ্যে কিছু সংখ্যক জিনিসপাতি থাকে ( কার্ড , বল এইসব হাবিজাবি ) একটা single move এ কোন player যে কোন সংখ্যক জিনিসপাতি একটা নিদিষ্ট  পাইপ/ বাক্স থেকে তুলে ফেলতে পারে । যদি কোন player কোন move এ কোন item  তুলতে না পারি তাহলে ও এই গেম হেরে যাবে । solution টা কি আমি চোখ বন্ধ করে পাইপে যা কিছু আসে এই ভ্যালু গুলারে xor করতে  থাকি  যদি Ans non zero কিছু হয় তাহলে আমার প্রথম player জিতে যাবে যদি তা না হয় তাহলে জয় লাভ করবে আমার second player . এইটা কেন হয় একটু ব্যাখ্যা করে নেই । ধরে নেই আমার কাছে ১৬টা কার্ড আছে । এইগুলা বিভিন্ন row তে আছে । ধরলাম ৪টা row তে আছে ।
  • ১ নাম্বার row এ আছে ১টা কার্ড
  • ২ নাম্বার row এ আছে ৩টা কার্ড
  • ৩ নাম্বার row এ আছে ৫টা কার্ড
  • ৭ নাম্বার row এ আছে ৭টা কার্ড
আমি যে কোন move এ যে  কোন সংখ্যক কার্ড যে কোন row থেকে তুলে নিতে পারি । আমি বলতে আসলে এইখানে যে দুই জন player খেলছেন । যখন কোন player কোন কার্ড তুলতে পারবে না তিনি হেরে যাবেন । এর solution process এ প্রতিটি row যে যত সংখ্যক কার্ড আছে তাদেরকে binary number এ represent করা হয় । তাদের প্রতিটা পজিশন এর xor value calculate করা হয় । এদের ভ্যালু হচ্ছে আমার সেই state এর Nim sum .যদি কোন state এর Nim sum non zero কোন কিছু হয় তাহলে এইটা হল winning state ( মানে এই state এ যে player আছেন তিনি optimal game খেললে জিতবেন ) আর zero থাকলে losing state ( হেরে যাবেন ) । যেমন এইখানে লক্ষ্য করি


for 1st row here is one card   -->  001
for 2nd row 3 cards so          --->  011
for 3rd                                   ->  101
And for 4th row                  ----- >111
                                    _________________
                                                  000 ( xor each position bit , if even numbers of 1 or o its o other wise its 1 )
এই অবস্থায় প্রথম player যাই দেন না কেন second player always Nim sum zero করে তার কাছে next move পাঠাবে । এতে দেখা যায় এমন কিছু থাকলে কখনই প্রথম player win করতে পারে না ।
wiki তে এর একটা proof দেখানো হইছে লিঙ্ক

এখন যদি আমাকে restriction দিয়ে দেয় যে না ভাই তুমি যা খুশী চাইলেই তুলে নিতে পারবা না । কিছু রুল থাকবে । ঐ সংখ্যক নেওয়া যাবে ( যদি যায় ) তাহলে কোন state এর Nim sum 0 থাকলেও দেখা যেতে পারে যে player restricted rule এর কারণে win করছে । তাহলে আমরা কিভাবে বুঝব যে কে জিততে যাচ্ছে । এর উত্তর নিয়ে আসে Sprague grundy theorem । এইখানে বলা হয় কোন state এর grundy value হচ্ছে সেই state থেকে যে সব state এ যাওয়া যায় তাদের ভ্যালুর মধ্যে যে সর্বনিম্ন ভ্যালুটা নেই ওটা । মানে হইল ধরি কোন state A থেকে B , C , D তিনটা state এ যাওয়া যায় যাদের grundy value হল যথাক্রমে {০,১,৪} তাহলে A state এর grundy value কত ? এইখানে A এর grundy value হবে ২ , কারণ A থেকে যাদের কাছে যাওয়া যায় তাদের কারো কাছে নেই এমন সব থেকে ছোট  ২  । কোন state এর grundy value 0 হওয়া মানে হইল এই state টা হচ্ছে হারার state . ০ বাদে যে কোন স্টেটই হচ্ছে আমার জিতার state . এইভাবে Sprague grundy solution এ আমার সবগুলা পাইপ এর grundy value বের করে Nim এর মত xor করা হয় যদি পজিটিভ কিছু থাকে তাহলে প্রথম player জিতবে নতুবা হারবে । যে কোন জিনিস বুঝার সব থেকে ভাল উপায় হল এর কোন প্রবলেম দেখা । আমরা এখন একটা basic problem দেখি ।  

প্রবলেম link এই প্রবলেম এ বলা হইছে দুই জন player খেলছে little chef আর head chef . তাদের সামনে অনেকগুলা piles আছে যেসব pile এ stone আছে । একটা single move এ একজন n^n আকারে stone কোন pile থেকে রিমুভ করতে পারে । মানে ( 1^1 ==1 , 2^2 == 4 , 3^3 == 27 , 4^4 == 256 ..... ) এমন সংখ্যক । আমাকে বলতে হবে যদি তারা optimal খেলে তাহলে কে জিতবে এবং little chef first move টা দেয় । এইখানে constrain থেকে দেখা যায় প্রতিটা pile এ highest stone থাকতে পারে 100000 মানে আমি highest 6^6 = 46656 টা stone নিতে পারি । এখন আমি কোডটা দেখি 
কোড

এইখানে আমি প্রতিটা pile এর grundy value বের করে xor করে দেখব । positive হলে little chef আর না হলে head chef জিতবে । প্রায় একই রকম একটা প্রবলেম হচ্ছে light oj 1315 - Game of Hyper Knights .
এইখানে pile এর বদলে আমাকে দাবা খেলার ঘোড়া দিয়েছে এবং তাদের মুভ restricted করে দিয়েছে । আমাকে বলতে হবে কে জিতবে Bob ভাইয়া না Alice আপু । এইখানেও base case হচ্ছে (০,০) নাম্বার পজিশন যার grundy value হচ্ছে ০ ( হারার স্টেট বলে ) । উপরের প্রসেসটা বুঝা গিয়ে থাকলে এই প্রবলেমটা এখন সবার পারা উচিত ।

যাই হোক এইটুকুই আসলে আমি জানি  Sprague Grundy  সম্পর্কে । এর জন্য আমি বিশেষ ধন্যবাদ দিতে চাই one and only halfo কে :D যার কাছ থেকে আমি এই সুন্দর জিনিসটা শিখছিলাম । এখন আর একটু নেট ঘাটাঘাটি করে সবাইকে বাকিটুকু শিখতে হবে ।


[ বিদ্রঃ আমি নিজে খুবই বাজে কোডার । আমার কোন লেখাই অন্ধ বিশ্বাসে ঠিক ধরে নেওয়া বোকামি । আমি তো নিজেকে নিজেই ভুলবাল বুঝাই :P তাই এইখানেও অনেক ভুল জিনিস থাকতে পারে । সব সময়ই সব কিছু নেট থেকে যাচাই করে নিতে হবে ] 









Wednesday, September 24, 2014

Binary Search part - 1

 বাইনারি সার্চ কি ? 
বাইনারি সার্চ হচ্ছে একটা sorted array তে কোন Key value (  যেইটা আমি খুঁজে বের করতে চাচ্ছি ) এর position বের করা । অধিকাংশ  ভার্সিটিতেই ফাস্ট ইয়ারের কোন না কোন কোর্সে ( আমি প্রথম জানতে পারি আমার ১/২ এর ডিসক্রিট ম্যাথ কোর্সে ) পড়ানো হয় তাই  আল্গরিথম নিয়ে কারো কোন প্রবলেম থাকে না , প্রবলেম হয় এর Use এ । কখন কোথায় আমার বাইনারি সার্চ লাগবে এইটা ধরতে । পৃথিবীর অনেক সুন্দর আল্গরিথম এর মধ্যে আমার মনে বাইনারি সার্চ একটি । কত কঠিন দেখতে লাগা প্রবলেম গুলাকে কত easy করে দেয় ।
আমি ধরে নিচ্ছি যারা এইটা পড়ছে সবারই Binary search নিয়ে idea আছে । কিভাবে code হয় । যদি তাও কারো না থেকে থাকে তাহলে নিচের দুইটা লিঙ্ক দেখলেই সবার ক্লিয়ার হয়ে যাবে । 

(১) টপ কোডার বাইনারি সার্চ                                                                                                              
(২)আসিফের হ-য-ব-র-ল ( Painless Binary Search )                                                                        
আমার এই লেখাটার উদ্দেশ্য হচ্ছে কিছু interesting problem এ আমি যদি binary search চালাই তাহলে  কিভাবে solution আমি খুব সহজেই পেয়ে যাই তা আলোচনা করা । আমি নিজে খুবই বাজে কোডার হয়ত আমার প্রসেস গুলা থেকেও ভাল প্রসেস আছে আমি এই প্রসেস এ AC পাইছিলাম তা আলোচনা করার চেস্টা করতেছি । লিখাটা আমার অনেক গুলা পার্ট এ করার ইচ্ছা আছে কারণ binary search এর এত এত সুন্দর problem আছে একটা পার্ট লিখা সম্ভব না :D

যেসব জিনিসপাতি সবাই জানি :
আচ্ছা যদিও আমরা সবাই জানি তাও কয়েকটা বিষয় আগে রিভাইস দিয়ে নেই বাইনারি সার্চ এর প্রবলেম দেখার আগে । 
  •  কোন sorted array binary search চালানো মানে lg(n) এর calculation করা । lg(n) এর মানে আমি কিছুটা এমন কল্পনা করতে পারি যদি n এর value  ১০০ হয় তাহলে  ১০০  < ২ ^  ( এর যে পাওয়ার use করলে এর মান বড় হয় তত গুলা অপারেশন ) যেমন এইখানে ৭ ,  ১০০ < ২ ^ ৭ ( ১২৮ ) । অর্থাৎ যদি ১০০ length এর কোন array এর উপর আমার বাইনারি সার্চ চালানো হয় তাহলে আমার মাত্র ৭টা অপারেশন করা লাগবে । 
  • বাইনারি সার্চ আমি শুধু মাত্র sorted value এর উপর করতে পারব । 
  • lower_bound ( আমাকে একই value এর অনেক গুলা জিনিস থাকলে এদের সবার প্রথমের value এর index return করবে ) ও upper_bound  ( almost same as lower_bound this time we will get the highest index of the key value + 1 , if there is no match then we will get immediate highest index ) 
Light Oj 1048 - Conquering Keokradong :::
এই প্রবলেমটা অনেক interesting . আমি  Keokradong climb করতে যাচ্ছি এর জন্য আমাকে  বিভিন্ন ক্যাম্পের distance দেওয়া আছে । ( এইখানে একটা ক্যাম্পের distance আর আগের ক্যাম্পের সাপেক্ষে ) . এখন আমাকে একটা লিমিট দেওয়া হইছে ( K ) এর মানে হইল আমাকে আমার পুরা tripটা k+1 camp এ নিয়ে আসতে হবে ( যেখানে আমি K night থাকব ) কিন্তু এমন ভাবে যেন আমার দুইটা ক্যাম্পের distance এর maximum value minimum হয় , আসলে এইখানে বলা হইছে আমি highest আমার trip কে k+1 এ ভাগ করতে পারি কিভাবে যেখানে পর পর ক্যাম্পের মধ্যে distance সব থেকে কম হয় । 
এখন দেখি প্রবলেমটা পড়ার সাথে সাথে আমার মাথায় কি কি চিন্তা আসতে পারে । প্রথমত আমাকে আসলে এমন কোন value নিতে হবে যাতে আমার পর পর ক্যাম্পের মধ্যে Distance কম হয় যদি দেখি এইটা কম আছে তাহলে আমি ওই ক্যাম্পটা skip করে Ans generate করার চেস্টা করব । আমাকে এমন sample case দেওয়া হইছে আমি Idea পাওয়ার সাথে সাথে মনে হবে আরে এমনই । ইয়েস পাইছি Idea । কোড করে সাথে সাথে submit এমন সুন্দর একটা verdict "Wrong Answer"  । ও আচ্ছা আমি এইটা মিস করছি আমাকে N এর value 1000 দেওয়া হইতে পারে এমন K এর মান হইতে পারে min ( N , 300 ) । তাহলে skipটা N-k শুধু একটা value এর উপরও হয়ত থাকতেছে না আমাকে অনেক গুলা position এই এমন কাজ করতে হয়ত হইতে পারে । মানে এমন অনেক কেস এই থাকবে যেখানে আমাকে এমন করে দেখতে হবে । আচ্ছা তাইলে বুঝছি DP করে করত হবে , অর্থাৎ আমাকে খালি বের করতে হবে skip পয়েন্ট গুলা কোনগুলা । normal sense এ যখন দেখি N এর মান 10000 হয়( মানে একটা ক্যাম্প থেকে অন্য ক্যাম্পের distance ) হইতে পারে মানে যদি আমি Dp করতে যাই তাহলে worst case এ N-k == 999*10000 == 9990000 লাগতেছে আর position er junno 1000 তো আছেই । অর্থাৎ যদি কোন compiler dp[1000][9990000] এমন কিছু declear করার permission আমাকে দেয় এবং অভয় দেয় পাগলা কোড কর আমি দ্রুতই Ans generate করে দিব তাহলে আমি একটা try দেওয়ার হইলেও দিতে পারতাম । যেইটা বর্তমান সময়ে কেউ দিচ্ছি না so dp এর চিন্তা বাদ । এতক্ষণ আমি খালি value skip এর পয়েন্ট নিয়েই চিন্তা ভাবনা করছি এখন এইটা বাদ দিয়ে দেখি অন্য কিছু ভাবা যায় নাকি । আসলে আমার main concern এর ব্যাপাটা হইল max value । আমি যদি max value ঠিক করে দেখি এমন কিছু করা possible কিনা মানে এই Max value এর জন্য আমার পুরা tripটাকে K part এ ভাগ করা যায় কিনা । যদি যায় তাহলে আমি Max value কমাইয়া দেখব এইভাবে possible হচ্ছে কিনা যদি হয় তাহলে কম Max value এর আমার Ans . এই কাজটাই আমি খুব সহজেই binary search এ করতে পারি । এইখানে Max value এর highest value  কি হইতে পারে সবগুলা ক্যাম্পের distance এর যোগফল কারণ এর চেয়ে বেশি কিছু আমার লাগতেছে না । আর lowest অবশ্যই পর পর দুইটা ক্যাম্পের মধ্যে যে distance তাদের মধ্যে highest টা ( কারণ K <= min ( n , 3000 ) ) .এখন All possible এর মধ্যে আমি lowest possibleটা নিব মানে এইখানে আমার lower_bound এর concept লাগতেছে । 




ক্যাম্প সাইট পিন্ট এর কাজটা এর পর অনেক সোজা । তাই আর আলোচনা করতেছি না । সবাই এখনই বুঝে গেছে না গেলে খাতা কলমে চিন্তা করে বের করতে হবে :D সব তো বলা ঠিক না :D 
প্রিন্ট এর কাজ বাদ দিয়ে same concept এ একটা প্রবলেম আছে এই প্রবলেম এর solution process বুঝা হয়ে গেলে  এইটাও সবার Try করা উচিত ।
 Light Oj 1076

Renting Bikes :::: 
এইটা আরেকটা খুবই চমৎকার binary search এর প্রবলেম । এই প্রবলেম এ কি বলা হইছে বলি । এইখানে বলা আছে N টা school boy আছে যাদের কোন bike নাই তারা bike রেন্ট নিতে পারে । যে site bike rent দেয় তাদের M টা bike আছে । প্রতিটা bike rent এর জন্য আলাদা আলাদা ফিক্সড প্রাইজ আছে । school boy গ্রুপ এর কিছু কমন মানি আছে ( সবার চাঁদা ধরতে পারি ) যেই টাকা তারা bike rent এ use করতে পারে কিন্তু কেউ নিজের টাকা থেকে অন্যকে টারা ধার দিতে পারে না এবং তারা রেন্ট নেওয়া বাইক শেয়ার ও করে না । আমাকে বলতে হবে maximum কয়টা boy bike রেন্ট নিতে পারবে এবং তাদের মিনিমাম কতটা খরচ করতে হইতে পারে ( মানে নিজেদের টাকা ) । 


প্রবলেমটা পড়ার সাথে সাথে মাথায় Idea আসে এইটা অবশ্যই greedy problem এমন কোন না কোন ভাবে sorting করে value গুলা use করতে হবে এবং অবশ্যই আমি যার নিজের টাকা বেশী তাকে বাইক দিতে চেস্টা করব । যদি আমি আরো একটু ভাবি যদি আমি ঠিক করে ফেলি আমি ৩জন কে bike দিব তাহলে অবশ্যই এইটা সবথেকে ভাল যার সবথেকে বেশী টাকা পয়সা আছে ও কিনবে ৩ নাম্বার সব থেকে কম cost এর বাইক , তারপরের জন্য ২ নাম্বার , এবং শেষজন সবথেকে কম cost এর বাইক । এই যে 3 জন ফিক্সড করে চেক করা এইটাই তো বাইনারি সার্চ :D আর যদি আরও একটু ভাবি code টা হবে upper_bound এর মত অর্থাৎ আমি সব সময় চেস্টা করব যেন আমি সব থেকে বেশী জন নিতে পারি । আর একটা পয়েন্ট আমি সব সময়ই আমার common money এর পুরাটাই use করব । 
    কোড

Present  :::: 
এইটা ও খুব চমৎকার প্রবলেম । এইখানে বলা হইছে beaver নামে এক পিচ্চি নতুন প্রোগ্রামিং শিখতেছে । ও তার প্রিয় ম্যামকে ম্যামের বার্থডে তার বাগানের ফুল গিফট করতে চায় ( ছেলে চালু পাবলিক :P ) । কিন্তু এইটা bad manners to present little flowers কিন্ত্ তার বাগানের ফুলগুলা হঠাৎ করে আর বড় হচ্ছে না এখন এর m days বাকি আছে বার্ডে থেকে । ও স্পেশাল একটা water পাইছে যেইটা দিলে next day তে ফুল গুলা 1 unit height বাড়ে । কিন্ত্ প্রবলেম হইল এই special water ও w wide এর contiguous flower কে শুধু মাত্র স্প্রে করতে পারে একদিনে  । আমাকে বলতে হবে ফুলগুলার minimum height কত হবে gift এর সময় মানে গিফট দেওয়া ফুলাগুলার মধ্যে কোন ফুলের height সব থেকে কম হবে ।  

    আমি যখনই দেখব আমাকে Min বা Max এর কোন ক্যালকুলেশন এর প্রয়োজন হচ্ছে আমি চেস্টা করে দেখব যে এইটা কোনভাবে binary search এ ফেলা যাচ্ছে কিনা । অধিকাংশ ক্ষেত্রেই দেখা যাবে Ans আসসে বা যদি দেখি Ans আসতেছে আমি binary search করার চেস্টা করব । এই প্রবলেমটা দেখি আমাকে কি করতে হবে । আমি ফুলগুলার highest min value calculation করব for sure এইটা করতে হবে binary search এ । আর যদি একটু ভাবি এতে upper_bound এর একটা ভাব আছে । all possible Ans থেকে আমি ম্যাক্স নিব । এখন দেখি কিভাবে । 
টানা লিখা আসলে অনেক ধৈর্যের  ব্যাপার :P আর পারতেছি না এখন লিখলেও খারাপ হবে । Next part এ আরও কিছু interesting প্রসেস লিখার চেস্টা করব । আর কেউ ভাল কোন প্রবলেম করে থাকলে কমেন্ট এ সবার জন্য suggest করতে পারেন যাতে আমরা সবাই এইখান থেকে শিখতে পারি ।




















Friday, September 19, 2014

Greedy Method


Greedy কি ? 

 প্রথমেই আসা যাক , greedy কি ? greedy হল ভবিষ্যতের এর কথা চিন্তা না করে বর্তমান অবস্থা গুলা বিবেচনা করে বেস্ট একশনটা নেওয়া । হয়ত এইটা পরবর্তীতে সবথেকে optimal নাও  হতে পারে । greedy solution তো optimal না তাহলে কেনই বা আমি greedy solution নিতে চাব । প্রথমত greedy solution time efficient । এমন অনেক ক্ষেত্রেই ধরে নেওয়া হয় greedy solution টাই best possible Ans . greedy solution যেহেতু  implement করা সহজ তাই অনেক optimized problem এর solution এর জন্য greedy use করা হয় । 
কিছু পরিচিত greedy process Change Making , kruskal Algorithm , Activity Selection . 

Change Making : 
        Change Making problem এ বলা হয় আমার কাছে অনেক গুলা বিভিন্ন মানের মুদ্রা আছে । আমাকে কোন সব থেকে কম মুদ্রা ব্যবহার করে Change দিতে হবে । আমি কিভাবে কাজটা করব । 
      এর প্রসেস হচ্ছে আমি সবসময় সবথেকে বড় মুদ্রাটা থেকে স্টার্ট করব এবং যতক্ষণ পর্যন্ত না এর ভ্যালু আমার change  ( একটা নিয়ে Total change  ভ্যালু থেকে subtract করা তো আছেই ) এর amount থেকে বড় হয়ে যাবে আমি নিতে থাকব , যদি তা বড় হয়ে cross হয়ে যায় তাহলে এর পরের value দিয়ে কাজ করার চেস্টা করতে থাকব । 
Code টা কিছুটা এমন

 আবারও বলে থাকা ভাল coin change এর জন্য greedy solution optimal না , optimal হল  dp   solution . কিন্তু  টাইম লিমিট অনেক সময় dp solution এর থেকে greedy solution      টাকেই optimal ধরে নেওয়া হয় । যদি এমন দেখা যায় coin গুলোকে ascending order এ সর্ট করার পর 2*coin[i] <= coin[i+1] তাহলে দেখা যাবে greedy solution best optimal result এই দিচ্ছি । 
Activity Selection Problem :
      Activity selection problem টা এমন আমাকে অনেক গুলা কাজ দেওয়া আছে । start time ও end time সহ । আমি একটা সময় শুধু মাত্র একটা কাজ এই করতে পারি । আমাকে যদি Nটা কাজ দেওয়া হয় তাহলে আমি সব চেয়ে বেশী  কয়টা কাজ করতে পারব । এইখানে overlapping possible না মানে একটা কাজ শেষ না করে কোন কাজ শুরু করতে পারব না  । এই প্রবলেম এর solutionটা অনেক সুন্দর । আমি কাজগুলাকে তাদের end time এর বেসিস এ sort করব । এর পর আমি যে কাজটা সবার আগে আসবে তা করব । এমন এর পর এ সেই কাজটা শুরু করব যার start time এই কাজের end time এর থেকে বেশী । 


Codeটা কিছুটা এমন
    
          এখন দেখা যাক এইভাবে করলে আমি কেন সব সময় বেস্ট Ans পাচ্ছি । আমি যদি end time  ধরে সর্ট করে
          কাজ স্টার্ট এর জন্য নেই আমি সবসময় সেইসব কাজ এই নিব যাদের end time অন্য কাজগুলা থেকে আগে      শেষ হচ্ছে   মানে আমি best option পাচ্ছি আরো বেশী কাজ স্টার্ট  করার ।
Active selection problem থেকে বুঝা যায় আসলে greedy কেন আসলে মাঝে মধ্যে dp থেকে ভাল ।  ধরুন আমার N টা কাজ এর লিস্ট আছে যাদের থেকে আমার বেস্ট লিস্ট করতে হবে যাতে আমি সবথেকে বেশী কাজ শেষ করতে পারি । DP এর জন্য আমার possible option 2^N . এখন N এর মান যদি অনেক বড় হয় তাহলে তা strict time limit জন্য খুব একটা ভাল উপায় না । আমি TLE খাব অনেক code এই । তাই মাঝে মধ্যে greedy is good .
Interval scheduling  problem :
 Interval scheduling ( Greedy ) problem এ আমাকে  অনেক গুলা কাজ এর start এবং end time দেওয়া হইছে । আমাকে প্রতিটা কাজ এর জন্য একটা  program assign করতে হবে । আমাকে বলতে হবে কিভাবে করলে সব থেকে কম  program assign করতে হবে । এইখানে overlapping possible না মানে একটা কাজ শেষ না করে কোন প্রোগ্রাম ফ্রী হবে না । মানে ৬ মিনিট এ যদি কোন কাজ শেষ হয় আর অন্য একটা কাজ ৬ মিনিট থেকে start হয় তাহলে ৬ মিনিট এর কাজ না শেষ করে যেহেতু অন্য কাজ শুরু করা যাবে না তাই এইখানে দুইটা প্রোগ্রাম লাগবে । আমি এইখানে sort করব । sort করার সময় end point , start point কে আলাদা ভাবে mark করব । start point priority পাবে মানে sorting এ সেম পয়েন্ট এ end , start থাকলে start আগে থাকবে । 
          


   কোডিং এ আমি চেক করব current position maximum কয়টা program স্টার্ট আছে , এইটাই আমার Ans . কারন এই সময় এই আমার সব থেকে প্রোগ্রাম রান করে রাখতে হবে । এর চেয়ে কম নিলেও আমার হবে না বেশী নিলে এক্সট্রা প্রোগ্রামগুলা বসে থাকবে ।

   Minimum Spanning Tree ( kruskal ) : 
  minimum spanning tree ও greedy problem এর জন্য ভাল উদারন । শাফায়াত ভাইয়া অনেক ভাল টিউটরিয়াল লিখছে kruskal . আশা রাখি এইখান থেকে একটু দেখলেই সবার clear হয়ে যাবে ।


কিভাবে আইডিয়া পাব এইটা greedy solution হতে পারে ?   যেকোন প্রবলেম এর solution idea পাবার পূর্বশর্ত হল এইরকম প্রবলেম অনেক সল্ভ করা । আমি যদি দেখি Ans গুলা current best option থেকে আসসে তাহলে আমি greedy solution এর কথা ভাবতে পারি । অনেক greedy problem এর সর্টিং , বাইনারি সার্চ এর দরকার হয় মানে সর্টিং , বাইনারি সার্চ করে বেস্ট পসিবল উত্তর পাওয়া যায় । এইসব ব্যাপার মাথায় রাখতে হবে । অনেক Dp প্রবলেম টাইম লিমিট এর মধ্যে করার জন্য code optimized করার প্রয়োজন হয় । তখন অনেক কেস greedy process থেকে বাদ দেওয়া হয় । তাছাড়া কোন প্রবলেম dp ,আর কোনটা  greedy তার মধ্যে difference করার জন্যও আমাদের greedy ভাবনা ভাবতে হবে । greedy মানে আমি নরমাল এই বেস্ট পসিবলের জন্য যা  চিন্তা করি ( human brain current stage থেকে একটা certain stage পর্যন্ত ভ্যালু ভাবতে পারে , তাই আমাদের চিন্তার ধরন greedy ) .  Uva আর Light Oj তে অনেক প্রবলেম আছে greedy এর জন্য । এইগুলা কিছু করলেই আরোও idea clear হবে সবার ।
problem
Uva Problem
Light Oj

সবাইকে অনেক শুভ কামনা :)
   
   

Tuesday, September 16, 2014

Editorial ( AUST ACM Practice Contest - 2 , 16/09/2014)


contest link ::: AUST ACM Practice Contest - 2

Problem A : 
এইখানে বলা হইছে  X = 0 ,  আমাকে বিভিন্ন pre or post increment or decrement operation দেওয়া হবে আমাকে শেষ X এর ভ্যালু বলতে হবে । এইখানে টেস্টকেস দেওয়া আছে , আমাকে ফাস্ট  এ টেস্ট কেস ইনপুট নিতে হবে তারপর একটা একটা করে srting input নিব এইখানে আমাদের খালি চেক করতে হবে কোন + sign আছে কিনা থাকলে ভ্যালু বাড়াব না হলে কমবে ।
পিয়াস এর কোড
Problem B : 
এইটাও অনেক সহজ প্রবলেম ।এইখানে বলা হইছে আমাকে একটা srting ইনপুট দিবে আমাকে বলতে হবে এইখানে কয়টা word আছে । এইখানে  আমাকে EOF পর্যন্ত ইনপুট নিতে হবে । তারপর আমাকে প্রতিটা ইনপুট এর জন্য Word count করে প্রিন্ট করতে হবে ।
say string inp ;
           getline( cin , inp ) ;
           int i , Ans = 0 , sz = inp.size() ; // string এর সাইজ দেয়
           for ( i = 0 ; i < sz ; i++ )
           {
                  if( i && !isalpha(inp[i]) && isalpha(inp[i-1]) Ans++ ; // এর মানে হইল এই লেটারটা কোন Alphabet না কিন্তু আগের লেটার টা ছিল মানে আমি একটা word পেয়েছি
           }
         print --- > Ans ; 
 Problem C :
  টেস্ট কেস এর প্রবলেম । এইখানে আমাকে একটা বৃত্ত এর ব্যাসার্ধ দিবে যা একটা চতুর্ভুজ এর ভিতর এর সব বাহুকে স্পর্শ করে যাছে আমাকে এর শেড করা জায়গার Area বলতে হবে । ফরমুলাটা হইল যদি  radius --> r then
area = ( 4 * r * r ) - 2 pi r * r ; // proof নিজে নিজে কর ।

Problem D : 
triangle print এর প্রবলেম । ১/১ এ ল্যাবে স্যার এর অনেক প্রিয় Assignment । এই প্রবলেম এ New লাইন এর অনেক প্রবলেম হয় । এইখানে এই ব্যাপারটা সবার খেয়াল করতে হবে ।
NOTE: There is a blank line after each separate waveform, excluding the last one.এর মানে হইল সব কেস এর পর আমি একটা extra new line print দিব কিন্তু লাস্ট কেস এ দিব না । এইটা আমাকে চেক রাখতে হবে ।
সিফাত এর কোড

Problem E : 
এইখানে আমাকে দুইটা নাম্বার দিবে n , m . আমাকে তারপর n টা সংখ্যা দিবে যাদের থেকে আমি m টা সংখ্যা নিব । কিন্তু এমন ভাবে এই m গুলার সংখ্যার মধ্যে maximum আর minimum এর difference হবে minimum .
sorting এর প্রবলেম । আমি nটা নাম্বার sort করব তারপর m টা number এর মধ্যে Ans বের করব।

        int n , m , i  ;
                  cin >> n >> m ;
                  for ( i = 0 ; i < n ; i++ )  cin >> Inp[i] ; // Inp --> Array globally declear
                  sort( Inp , Inp+n ) ; // sort ascending order
                  int Ans = Inp[m-1] - Inp[0] ; // initial value
                  for ( i = 1 ; i + m - 1 < n ; i++ )
                  if ( Inp[i+m-1] - Inp[i] < Ans ) // Value update
                  Ans = Inp[i+m-1] - Inp[i] ;
                  print --- > Ans ; 

 Problem F : 
এইটা DP এর basic state reduction problem । এইখানে চারটা নোড দেওয়া হইছে A , B , C , D . প্রাথমিক ভাবে পিপড়াটা আছে D তে । আমাকে একটা নাম্বার n দেওয়া হবে । আমাকে count করে বলতে হবে n length এর কয়টা cyclic path আছে । cyclic path মানে যেখানে ছিলাম আবার সেখানেই আসব । এইখানে D থেকে D তেই আসব কয়ভাবে ( কয়টা Unique path আছে ) । যেমন n== 2 হলে
  1. D - A - D 
  2. D - B - D 
  3. D - C - D 
এমন ৩টা path আছে । এখন আসি space reduction dp কি ? Dp তে আসলে আমরা কি করি state by state value calculate করি । কোন state এর value তার আগের এক বা একাধিক state থেকে পাই । যদি এমন দেখা যায় একটা state এর ভাল্যু খালি তার আগের এক/দুই/তিন ( মানে fixed অল্প কিছু state ) এর উপর depend করে তাইলে আমি আগের state এর ভ্যালু বাদ দিতে পারি । এই প্রবলেম এর জন্য দেখি কিভাবে ? এইখানে ০ length এর খালি একটা cyclic path এই আছে ।
0 মানে পিপড়া D তে ছিল D তেই আছে । এখন যদি 1 length এর বের করতে চাই তাহলে কিভাবে  । আসলে 1 length এর cyclic path মানে o length এর A তে total cyclic path + 0 length এর B তে total cyclic path + 0 length এর C এর total cyclic path .
মানে আসলে এমন । 2 length এর calculation এর জন্য খালি 1 length এর state এর ভ্যালু দরকার আমার । তাই 2 length এর জন্য 0 length এর ভ্যালু আমার মেমু করে রাখার কোন দরকার নাই ।

dp[now][ node == D here  ]  = (  dp[prev][A] + dp[prev][B] + dp[prev][C] )  % Mod
এখন প্রতি state শেষ এ আমি now , prev এর ভ্যালু চেঞ্জ করব । এইটা কিভাবে কাজ করছে তা খাতা কলমে করে দেখ ।
    long long dp[4][2] ;
    dp[0][0] = dp[1][0] = dp[2][0] = 0 ;
    dp[3][0] = 1 ;
    int n , i ;
    cin >> n ;
    int now = 1 ;
    int prv = 0 ;
    for ( i = 1 ; i <=  n ; i++ )
    {
        dp[0][now] = (dp[1][prv] + dp[2][prv] + dp[3][prv] )%Mod ;
        dp[1][now] = (dp[0][prv] + dp[2][prv] + dp[3][prv] )%Mod ;
        dp[2][now] = (dp[0][prv] + dp[1][prv] + dp[3][prv] )%Mod ;
        dp[3][now] = (dp[0][prv] + dp[2][prv] + dp[1][prv] )%Mod ;
        swap(now,prv);
    }
    cout << dp[3][prv] << endl ;

 Problem G : 
এই প্রবলেমটা কিছুদিন আগেই CF এর কনটেস্ট এর ছিল । আমি প্রবলেমটা ভালমত না পড়ার কারনে মিস করে গেছিলাম ।এইটার Dp এবং Directed graph এর longest path দুইটাই solution আছে ।আমি গ্রাফ এর প্রসেসটা বলি ।  এইখানে আমাকে n length এর m সংখ্যক Array দেওয়া হইছে । আমাকে এই m Array এর মধ্যে longest common subsequence এর বলতে হবে । এইখানে সবচেয়ে Important point
                   " Each of them consists of numbers 1, 2, ..., n in some order."    
 এর মানে হইল n এর যে ভ্যালু থাকবে Array তে 1 - n পর্যন্তই থাকবে যেকোন order এ । এইখানে n এর লিমিট ১০০০ আমি যদি এখন এদের কে directed graph এ convert করতে পারি তাহলে আমার খালি longest path এর lengthটাই আমার উত্তর । ১০০০ যেহেতু লিমিট আমি খুব সহজেই n^2 , m <= 5  এর মধ্যে চেক করতে পারি দুইটা index i & j এর জন্য সব Array তেই i এর পর j আছে কিনা । যদি থাকে তাহলে i --> j path থাকবে । graph বানানো হইলে আমাকে জাস্ট বের করতে  হবে maximum length এর path যেইটা Dfs দিয়ে সবাই পারবে আশা রাখি । 

const int MX = 1005 ;
vector < int > G[MX] ;
int pos[10][MX] , Best[MX] , Inp[10][MX];
int N , K ;
bool used[MX];
int Ans ;
void Dfs(int node)
{
    used[node] = 1 ;
   // Best[node] = 1 ;
    int sz = G[node].size();
    int i ;
    for ( i = 0 ; i < sz ; i++ )
    {
        int u = G[node][i];
        if( !used[u] )  // already visited
        Dfs(u);
        Best[node] = max( Best[node] , Best[u] + 1 ) ;
    }
    Best[node] = max(Best[node] , 1 );
    Ans = max( Ans , Best[node]);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int i , j , k , n ;
    cin >> N >> K ;
    for ( i = 1 ; i <= K ; i++ )
    {
        for ( j = 0 ; j < N ; j++ )
        {
            cin >> Inp[i][j] ;
            pos[i][Inp[i][j]] = j+1 ;
        }
    }
     bool thik ;
    // now graph construct
    for ( i = 1 ; i <= N ; i++ )
    {
        for ( j = 1 ; j <= N ; j++ )
        {
            if ( i == j ) continue ;// no self loop possible
            // now we check if its possible to have a edge for i to j
            // its only possible if j is after i in every set
         thik= 1 ;
            for ( k = 1 ; k <= K && thik ; k++ )
            {
                if ( pos[k][j] <= pos[k][i] )
                thik = 0 ; // not possible t
            }
            if ( thik ) G[i].pb(j);
        }
    }
    Ans = 0 ;
    for ( i = 1 ; i <= N ; i++ )
    {
        if( !used[i] ) Dfs(i);
    }
    cout << Ans << endl ;

Problem H : 

এইটা Interval scheduling ( Greedy ) problem . এইখানে অনেক গুলা কাজ এর start এবং end time দেওয়া হইছে । আমাকে প্রতিটা কাজ এর জন্য একটা wrapper program assign করতে হবে । আমাকে বলতে হবে কিভাবে করলে সব থেকে কম wrapper program assign করতে হবে । এইখানে overlapping possible না মানে একটা কাজ শেষ না করে কোন প্রোগ্রাম ফ্রী হবে না । মানে ৬ মিনিট এ যদি কোন কাজ শেষ হয় আর অন্য একটা কাজ ৬ মিনিট থেকে start হয় তাহলে ৬ মিনিট এর কাজ না শেষ করে যেহেতু অন্য কাজ শুরু করা যাবে না তাই এইখানে দুইটা প্রোগ্রাম লাগবে । আমি এইখানে sort করব । sort করার সময় end point , start point কে আলাদা ভাবে mark করব । start point priority পাবে মানে sorting এ সেম পয়েন্ট এ end , start থাকলে start আগে থাকবে । 
          struct abc
                    {
                            int value , mark ; // mark 0 for start point , 1 for end
                    } Inp [ Mx + Mx ] ;
                     bool cmp ( abc A  , abc B )
                     {
                              if ( A.value == B.value ) return A.mark < B.mark ;  // start mark age thakbe
                              return A.value < B.value ;
                     }

                   int main()
                  {
                           int n , i  , x , y , idx = 0;
                          cin >> n ;
                         for ( i = 0 ; i < n ; i++ )
                        {
                                 cin >> x >> y ;
                                 Inp[idx].value = x ;
                                 Inp[idx++].mark = 0 ;
                                 Inp[idx].value = y ;
                                 Inp[idx++].mark = 1 ;
                        }
                      sort(Inp , Inp+idx , cmp );
                     int Ans = -Inf ;
                    int cur = 0 ; // eita count korbe koyta program ekhon run korche
                    for ( i = 0 ; i < idx ; i++ )
                    {
                                  if( Inp[i].mark == 0 ) // mane notun program start hoiche
                                   cur++;
                                   else cur-- ; // program off hoiche
                                  Ans = max(Ans , cur );
                    }
                   print -- > Ans ;
                   return 0 ;

               }

   কোডিং এ আমি চেক করব current position maximum কয়টা program স্টার্ট আছে , এইটাই আমার Ans .

যে যে প্রবলেম সল্ভ করা যায়নি কনটেস্ট টাইমে তা upsolving ( কনটেস্ট এর পর সল্ভ ) করতে হবে ।  না হলে আসলে কিছুই শিখা হবে না । সবার জন্য শুভ কামনা :)