Wednesday, June 24, 2015

Light OJ ( DP part - 2 )


এইটা এই সিরিজের দ্বিতীয় লিখা । এই পর্বে কিছু  interesting problem এর solution process নিয়ে লিখার চেস্টা করতেছি ।

Lighted Panels :::

এই প্রবলেম এ আমাদের একটা লাইট প্যানেল এর অবস্থা দেওয়া  হয়েছে , কোন অবস্থার '*' এর মানে হচ্ছে লাইট জ্বলে আছে , '.' মানে হচ্ছে লাইটা নিভে আছে । আমাদেরকে মিনিমাম মুভে প্যানেল এর সবগুলা লাইট জ্বালাতে হবে । এইখানে যখন কোন পয়েন্ট  toggle করা হয় ( মানে এইটা যে অবস্থায় আছে জ্বলা থাকলে নিভা , নিভা থাকলে জ্বলে উঠবে ) ঐ পয়েন্ট এর সাথে adjacent যে পয়েন্টগুলা থাকে ( diagonal সহ ) তারাও toggle করবে। 


  • যে কোন প্রবলেম solution process বের করার একটা way হচ্ছে constrain গুলা চেক করা । শুধু মাত্র ইনপুট এর লিমিট দেখেই আমরা কোন সল্যুশন প্রসেস চিন্তা করা শুরু করব আবার কোন প্রসেস চিন্তা করা বাদ দিব ।  এইখানে Row <= 8 and Column <= 8 দেওয়া আছে । স্বাভাবিক ভাবেই  লিমিট কম হলে আমাদের জন্য ভাল । আমরা যদি dp solution develop করতে চাই তাইলে মনের খুশী মত state ও বাড়াইয়া ফেলতে পারব যেটা লিমিট অনেক বড় হইলে সম্ভব হইত না । 
  • এই প্রবলেমটা যদি দেখি আমরা যখন কোন পয়েন্ট toggle করি তাহলে কি হবে আমরা যে row তে আছি তার আগের row এবং পরের row এর আমরা যে column এ আছি তার আগের column এবং পরের column নিয়ে কাজ করব । অর্থাৎ আমরা যদি row wise করে লাইটগুলা জ্বালাতে থাকি তাহলে আমাদের main concern হইল আগের column , এখন যে column এ আসি এ column এবং পরের column নিয়ে । একই জিনিস column wise করে এগানোর জন্য প্রযোজ্য । তবে আমরা row wise solution process টা দেখব । 
  • আমারা আমাদের solution process develop করব row wise , একটা জিনিস দেখি আমরা যখন যে row নিয়ে কাজ করছি এই row এর information তার আগের row এবং পরের row এর উপর নির্ভর করে । তাই কোনভাবে আমি এখন যে row তে আসি তার কিঅবস্থা ( মানে কোন কোন পয়েন্ট জ্বলে আসে কি নিভে আসে ) যে row থেকে আসলাম তার কি অবস্থা ছিল এবং যে row তে যাব তার কি অবস্থা আছে আমাদের তা জানা থাকা দরকার । 
  • এই প্রবলেম এর একটা ভাল দিক ছিল এইখানে লিমিট অনেক কম । লিমিট কম থাকলে আমরা অনেক state নিয়ে ভাবতে পারি খুব একটা difference হয় না । যেহেতু আমরা row wise কাজ করতেছি অবশ্যই আমরা কোন row তে আসি তা একটা state , আমরা যে row থেকে আসলাম তার কি অবস্থা ( কোন কিছু যার মাধ্যমে আমরা বুঝতে পারি কোন কোন পজিশনের লাইট কি অবস্থায় আছে ) , এবং এখন যে অবস্থায় আসি তার কি অবস্থা আমাদের জানা থাকতে হবে । মানে এই ইনফরমেশনগুলা আমাদের state এ থাকা লাগবে । এখন কোন লাইট জ্বলে আসে কি নিভে আসে তা আমরা খুব সহজেই বিট  দিয়ে বুঝতে পারি , যেহেতু column highest হতে পারে ৮টা তাই আমাদের শুধুমাত্র ( ১ << ৮ ) সাইজের কোন state থাকলেই আমরা বুঝে যাব কোন  কোন পজিশনে কি কি আছে । তাই আমাদের dp table হবে । dp [ number_of_row ] [ bit_position_of_previous_row] [ bit_position_of_current_row ] অর্থাৎ dp[ 8 ] [ ( 1 << 8 ) ] [ ( 1 << 8 ) ] . আসলে তাইলে আমাদের লাগতেছে  8 * ( 1 << 8 ) * ( 1 << 8 ) == 524288 size এর dp array । 
  • আমাদের ক্যালকুলেশন এর জন্য আমাদের পরের row ও দরকার হবে এইটা আমরা কোথায় পাব । আমরা প্রথমেই ইনপুট নেওয়ার সময় একটা array তে রেখে দিতে পারি কোন কোন লাইট এখন জ্বলে আসে ।  
  • যে  row তে আসি এর প্রতিটা combination করে আমরা আমাদের store value গুলা change করে দেখব । এর জন্য আমরা subset mask use করতে পারি । যেহেতু column এর highest limit 8 .তাই ( 1 << 8 ) == 256 খুব সহজেই আমরা আমাদের dp এর ভিতর তা চালাতে পারি । 
  • যখন আমরা নেক্সড row তে যাব যদি না আমরা প্রথম কলামে থাকি তাহলে অবশ্যই আমাদের sure করতে হবে আমাদের আগের row এর সবগুলা লাইটা জ্বালানো আছে ( যদি না থাকে তাহলে আর কোন ভাবেই ঐ লাইটাকে আর জ্বালানো সম্ভব হবে না  কিন্তু প্রথম রো থেকে এই জন্যই যাব কারণ আমি দ্বিতীয় রো থেকেও প্রথম রো এর সব লাইট নিভাতে পারি । ) ।

    কোড :
এই প্রবলেমটা আমরা itterative ভাবেও  করতে পারি , subset mask এর মাধ্যমে ।

Tiles (II) :
এইটা একটু বিরক্তি কর bitmask প্রবলেম । আমাদের ছয়টা বিভিন্ন সাইজের টাইলস দেওয়া আছে । আমাদের বলতে হবে এই বিভিন্ন টাইলজ দিয়ে ( n x m ) সাইজের একটা গ্রীড কতভাবে পূরণ করা যাবে । দুইটা বোর্ড different হবে যদি এদের মধ্যে কোন cell এর কালার different হয় ।

  • ইনপুট লিমিট এ দেওয়া দেওয়া আছে ( 1 <= n , m <= 100 but min( n , m ) <= 8 ) । এর মানে হইল row , column এর মধ্য যে কোন একটা 8 এর চেয়ে কম হবে । এইটার একটা ব্যাপার হইল আমরা চাইলে এই কম পার্টটাকে বিট করে ফেলতে পারি । এইখানে Row/Column দুইটার যে কোনটাই হইতে পারে । যেহেতু আমরা জানি না কোনটা হবে আমরা ধরে নেই column এর পার্টটাতে আমরা বিটমাস্ক করব কিন্তু Row ও হইতে পারে । যদি Row <= 8 হয় তাহলে আমরা given array এর Row এবং Column part টা swap করে দিব । মানে যা input এ ছিল আমাদের column এইটা কে আমরা Row ভ্যালু করে ফেলব  । মানে যদি Row = 8 , Column = 100 হয় তাহলে আমাদের Row হয়ে যাবে ১০০ এবং column হয়ে যাবে ৮ । 
  •  এই প্রবলেমটার সাথে আগের প্রবলেম এর মিল আছে । আমরা যদি given tiles গুলা দেখি প্রতিটাই দুইটা row করে নিয়ে হচ্ছে । অর্থাৎ কোন tiles বসবে কি বসবে না এই জন্য আমাদের কাছে কমপক্ষে দুইটা row এর ইনফরমেশন থাকতে যাবে । 
  • আমরা যখন কোন tiles বসাতে যাব আমাদের দেখতে হবে আমরা এখন যে Row তে আসি তার পরের Row এর যে সব column নিতে টাইলসটা হবে তা খালি আছে কিনা । 
  • আমরা column ফিল করতে করতে next column এ আগাব এবং যেহেতু দুইটা curmask ও nextmask নিয়ে কাজ করছি অবশ্যই আমরা যখন সব Row ফিল করে ফেলব তখন nextmask অবশ্যই ০ থাকবে । 
  • এই কাজটা একটু বিরক্তিকর কারণ আমাদের অনেক চেক রাখতে হবে । সবগুলা tiles নিয়ে ফিল করার জিনিসটা আমরা একটা backtrack function এর মাধ্যমে করতে পারি । এইখানে যেহেতু আমরা column এর basis এ ফিল করব ( backtrack এ ) আর লিমিট যেহেতু কম আমাদের খুব একটা বেশী কল হবে না ।
  • এইখানে রেজাল্ট কে 2^64 mod করে দিতে বলা হইছে তাই আমরা unsigned long long int use করব ।  
কোড :
Software Company :
এই প্রবলেমটা binary search + dp এর । এইখানে একটা software company এর কথা বলা হইছে । তারা দুইটা প্রোজেক্ট শেষ করবে । n জন employee এর ইনফমেশনে দেওয়া আছে তাদের কত মিনিট করে নেয় দুইটা প্রোজেক্ট এর এক unit কাজ করতে । কোন প্রোজেক্ট সম্পূর্ণ শেষ করতে m unit কাজ কমপ্লিট করতে হবে ।

  • এই প্রবলেমটা খুব সম্ভত বুঝাটা এইটা binary search এ হবে এইটাই সব থেকে কঠিন পার্ট । তারপরের কাজ খুব সহজ । আমরা যেকোন একটা employee নিয়ে ও যদি একা দুইটা কাজ করত তাহলে কত সময় লাগতকে high ধরে lower_bound binary seach করব । দেখব lowest কত value এর জন্য আমাদের কাজ দুইটি সম্পূর্ণ করা যাবে । 
  • 3 state এর normal dp , current_employee_number , work_left_for_first_one , work_left_for_second_one . এইখানে লিমিট দেওয়া আছে ( 1 <= n , m <= 100 ) তাই আমাদের dp[101][101][101] size এর dp দিয়েই হয়ে যাবে । 
  • কোড

এই সিরিজের আরো কয়েকটা লিখা ইচ্ছা আছে , যদি লিখার মোটিভেশন বজায় থাকে । ধন্যবাদ পড়ার জন্য ।

10 comments:

  1. This is a good stuff. Keep it up man! :)

    ReplyDelete
  2. please discuss how can I solve TUG OF WAR . I've no idea about it

    ReplyDelete
    Replies
    1. no problem i will in my next DP post . But it may take some times . If you want to solve it now i give you some hints how to solve it . at first we need to concern about two things . as we need to divide them into two teams and difference between two team must not differ by one ( thats the little thing that different it from normal 0/1 knapsack part , if this constrain isn't given we can easily do it with limit ( total_weight/2 ) part , hope you understand it . ) and difference weight between two team is as little as possible . Total weight won't exceed 100000 some how you need to use this information . Say 1 person weight is 3 kg and another personal weight is 4 kg . We need to use this information that 3kg of weight can be one person weight and 4 kg weight is one person weight and 7kg weight is two person weight in an array . think about it .

      Delete
    2. thanks vaiya :) it was really helpful :) i've solved this one :)

      Delete
  3. how can i solve Light oj 1415 ( save the trees) ? :\ please help in details :\

    ReplyDelete
  4. sorry , i haven't seen this comment before . ok i will try to write it down in my next dp blog , It may take time . Right now i am very busy with my stuff . Whenever i get some free times i will write it down .

    ReplyDelete
  5. I see a mistake in line number 24 of the first problem. The condition should be

    if(i&(1<<j)), shouldn't it?

    ReplyDelete
  6. no , it is right . if the j(th) bit in i is 1 then we gonna toggle this otherwise no . actullay its totally upto you what you wanna do , as only 0/1 is here and all combination is fulfill by 1's combination or o's combination nothing is big deal :D you can chose one of the combination
    Say 2bit combination
    00
    01
    10
    11
    what ever you choose 0's combination to toggle or 1's combination both will give you right answer .

    ReplyDelete
  7. Will you explain the time complexity of loj 1092.

    ReplyDelete