Part 2: Playing With Math

Updated on November 11, 2019 in Competitive Programming
0 on November 8, 2019

আমার lightOJ সিরিজ এর দ্বিতীয় পার্ট। আজকের প্রধান বিষয় হল Math এবং Number Theory.

আগের পর্বে lightOJ সম্পর্কে একটা জিনিস বলা হয় নি, এখানে cin/cout use করলে TLE খাওয়ার সম্ভাবনা অনেক বেশি। কাজেই সবসময় (atleast lightOJ তে) scanf/printf use করবে। 

1015 – Brush (I)
একসারি সংখ্যা দেয়া আছে, তাদের যোগফল বের করতে হবে। পর পর দুই পার্ট এর প্রথম প্রবলেম শুধু যোগ করার প্রবলেম LOL.

1053 – Higher Math
একটা ত্রিভুজের তিনটা বাহুর দৈর্ঘ্য দেয়া আছে, বলতে হবে এটা সমকোণী ত্রিভুজ কিনা। সহজ পিথাগোরাস প্রবলেম।

এই প্রবলেম অনেক সময় বলে যে ত্রিভুজ স্থুলকোণী/সূক্ষ্মকোণী কিনা বের করতে। সেটাও পিথাগোরাস থেকে বের করা যায়। কোন ত্রিভুজ স্থুলকোণী হলে স্থুলকোণ এর বিপরীত বাহু c এর জন্য, c^2 > a^2 + b^2 আর সূক্ষ্মকোণী হলে c^2 < a^2 + b^2 
[Proof? Cosine Law/Pythagoras]
আর যদি কোণগুলোই বের করতে হয়? তাহলেও Cosine Law লাগবে তোমার। 

1010 – Knights in Chessboard
“কিন্তু আমি তো দাবা খেলি না, পারিও না।” :’( 

প্রবলেম solving এর এই একটা মজা, অনেক সময়ই দেখবে এরকম কোন game নিয়ে প্রবলেম দিয়েছে। এমন প্রবলেম দিলে সবসময়ই statement এ খেলা কিভাবে খেলা হয়, বা যেটুকু info লাগে তা দিয়ে দেয়া থাকে, যাতে যে খেলাটার নাম আগে শুনে নাই, সেও চেষ্টা করতে পারে। তবে মাঝেমাঝে, যারা দেখা যায় আগে থেকেই খেলাটা সম্পর্কে জানে, তারা হয়ত একটু বাড়তি experience এর সুবিধা পায়।

তো প্রবলেমটা হল, একটা n x m size এর দাবার board এ সর্বোচ্চ কতগুলো ঘোড়া(Knight) বসানো যায়, যাতে কেউ কাউকে attack না করে। 

এই প্রবলেমটা solve করার key observation হল, একটা ঘোড়া যদি তুমি সাদা ঘরে বসাও, তাহলে সেটা অন্য কোন সাদা ঘরে attack করে না। (এবং বিপরীতটাও সত্য)

তাহলে n x m board এ সাদা আর কালো এর মধ্যে যেটা বেশি সেটাই উত্তর।
কিন্তু max(\lfloor \frac{nm}{2} \rfloor, \lceil \frac{nm}{2} \rceil) Submit করলে দেখবে WA.

এমন করে অনেকসময় একটা observation বের করে আনন্দে আত্তহারা হয়ে গেলে দেখা যায় এই কান্ড ঘটে। আমাদের উপরের ওই ফর্মুলা ঠিকই আছে, কিন্তু আমরা একটা জিনিস খেয়াল করিনি, তাহলো এটি n, m > 2 এর ক্ষেত্রে প্রযোজ্য। 1 x n Board আর 2 x n Board এর জন্য নিচের মত করে বসাতে হবে।

1045 – Digits of Factorial
খুবই important একটা প্রবলেম number theory এর। প্রবলেমটা আমরা ছোট ছোট ধাপে solve করব (সব সময়কার মত)।

Tutorial: এইটা Topcoder এর tutorial এর page. এখান থেকে “Mathematics for Topcoders” টা পড়ে ফেলতে পার। এই প্রবলেম solve করতে ওগুলো জানা লাগবে না। কিন্তু পরে কাজে আসবে। কমপক্ষে Prime Numbers, GCD, Bases এই তিনটা section ভাল মত বুঝে ফেল। যেহেতু এই প্রবলেমেও আমাদের base নিয়ে খেলতে হবে, তাই কাজে লাগতে পারে। 

ধর, শুধুমাত্র 10 Base এর জন্য আমরা প্রবলেমটা solve করতে চাচ্ছি। প্রথমে আমরা দেখি, কিভাবে একটা সংখ্যা কয় অঙ্কের তা বুঝা যায়। একটা 10 Base সংখ্যায় 10 এর power যত বেশি হয়, তত বেশি digit থাকবে তাতে (দশমিকের পরের গুলো গুনতে যেও না আবার)। যেমন, 10^2 = 100, 10^{2.6} \approx 398.11, 10^3 = 1000. দেখ, 10 এর power পূর্ণসংখ্যা হলে, তার সাথে 1 যোগ করে digit সংখ্যা পাওয়া যায়। আর দশমিক power হলে, তার floor এর সাথে 1 যোগ করলে হয়। তাহলে আমরা একটা ফর্মুলা পাই। 

যেকোনো সংখ্যা n এর digit সংখ্যা = \lfloor \log_{10}n \rfloor + 1.
তাহলে n! এর digit সংখ্যার জন্য কি করা যায়? এক্ষেত্রে \log এর ভিতরে n! থাকবে। 
\log_{10}n! = \log_{10}({1*2*...*n}) = \log_{10}1 + \log_{10}2 + ... + \log_{10}n
ব্যাস, এবার এটা ব্যবহার করেই, Base 10 খুব সহজে solve করা যাবে।

তো অন্য Base এর জন্য কি হবে? আচ্ছা ভাবোতো, যদি Base 10 এর জন্য 10 based log লাগে, তাহলে, base B এর জন্য কি B based log করলেই হবে না? আসলেই তাই, শুধু log এর base change করলেই, অন্যান্য base এর জন্য solve করা যাবে। (কেন? চিন্তা কর) 

তবে প্রবলেমটাতে এখনো একটু সমস্যা আছে। যদি তুমি প্রতি Test Case এ n পর্যন্ত সব \log যোগ করতে করতে যাও, তাহলে তোমার code এর complexity হবে O(TN) যেটা TLE হবে। এজন্য যা করতে পার, তাহলো, আগেই একটা array তে, 1 থেকে 10^6 পর্যন্ত সব value এর 10 based log বের করে এর prefix sum array বানিয়ে ফেল। তাহলে এখন O(1) এই তুমি \log_{10}n! বের করতে পারবে। আর \log_{10}n! জানলে, এটা থেকে \log_{b}n! বের করা তো খুব সহজ। তাহলে O(T) তেই প্রবলেমটা solve করা যাচ্ছে।

Bonus 1: n! এর শেষে কয়টি 0 আছে বের কর। খুবই common প্রবলেম এটা। “প্রোগ্রামিং কন্টেস্ট ডাটা স্ট্রাকচার ও অ্যালগোরিদম/Dawn of Programming Contest” (শান্ত স্যার) এর বইয়ে এইটার solution দেয়া আছে। চাইলে এখানেও পড়তে পার।

Bonus 2: n! এর সর্বডানের (least significant) non-zero digit টি কত তা বের কর। প্রবলেমটা আমি USACO Training এর Chapter 3 Section 3.2 – Factorials থেকে নিয়েছি। কেউ যদি আগের section এর প্রবলেম গুলো solve না করে থাকে তাহলে সে এটাতে access পাবে না। এই site টাও বেশ ভাল training এর জন্য। Modular arithmetic সম্বন্ধে একটু জানলেই পারার কথা। না পারলে google তো আছেই। 

1354 – IP Checking
এটা সাধারন Base conversion প্রবলেম। আগের প্রবলেমে দেয়া topcoder tutorial এর Base অংশ পড়ে থাকলে এটা পারা খুবই সহজ। তাই আমি solution নিয়ে আর কোন কথা বলব না। 

তবে এখানে যেটা বলা যায় সেটা হল input নেয়ার কৌশল। অনেক প্রবলেম এই দেখবে ইনপুটে এমন এমন জিনিস দিচ্ছে যা তোমার লাগবে না, কিন্তু input নিতে সমস্যা করছে। যেমন ধর, ঘন্টা মিনিট সেকেন্ড এভাবে দিচ্ছে, 12:30:11 বা DD/MM/YYYY format. তো এইসব ক্ষেত্রে scanf দিয়ে খুব সহজেই input নেয়া যায় (string/getchar/ওইরকম কিছু ব্যবহার না করে)। যেমনঃ

int h, m, s;
scanf(“%d:%d:%d”, &h, &m, &s); // notice those colons
int D, M, Y;
scanf(“%d/%d/%d”, &D, &M, &Y); // they mean to ignore those symbols in input

এই forum টা পড়ে ফেল, Advanced scanf

1182 – Parity
একটা number এর বাইনারিতে কয়টা 1 আছে তা বের করতে হবে। এটার সাদামাটা solution হল number টাকে binary তে convert করার সময় কয়বার 1 আসে তা গুনে ফেলা। তবে এই প্রবলেম এক লাইনে solve করা সম্ভব। আমি পুরোপুরি বলে দিব না, এই লিঙ্কে চারটা builtin function দেয়া আছে (তুমি google করলে আরো অনেক builtin function পাবে, তবে ঐ চারটাই সাধারনত লাগে)। এগুলো জানা খুবই প্রয়োজন যদি তুমি তোমার code আরো ছোট করতে চাও। এর একটা দিয়ে তুমি প্রবলেমটি solve করে ফেল।

  • Liked by
  • NonirPotol
  • abusayed
  • Srijon kumar
  • ZooHire
  • Parenchyma
  • +2
Reply
Loading more replies