Reading Time: 1 minute

Lightoj 1054 Efficient Pseudocode:

Tag:  Number Theory, Modular Arithmetic

Algorithm:

n^m

= (p1 ^ (a1) *  p2^(a2) * p3 ^ (a3) …………………………..)^m

= p1 ^ (a1 * m)  *  p2 ^ (a2 * m) * p3 ^ (a3 * m)……………………………

মানে প্রথমে আমরা n কে ফ্যাক্টোরাইজ করলাম তারপরে যথারীতি আমরা প্রত্যেক প্রাইম এর পাওয়ারের সাথে m গুণ করে দিলাম । যেখানে p1,p2,…..pn প্রত্যেকটি একেকটি ডিফরেন্ট প্রাইম ।

আর আমরা জানি sum of divisors(SOD) = p ^ a = ( P ^(a+1) – 1) / (p – 1)

আর প্রত্যেকটি আলাদা আলাদা প্রাইমের Sum of Divisors এর গুনফল ,যেটি একত্রে পুরো সংখ্যাটির SOD, কারণ,

সাপোজ

(p1^a1) * (p2 * a2) = n^m

SOD(n^m)  = SOD(p1^a1 * p2 ^ a2)

= SOD(p1 ^a1)  * SOD(p2 ^ a2)  কারণ এরা সহমৌলিক, এদের কোন ইন্টারসেক্টিং অংশ পাওয়া যাবে না ।

তাই আমরা প্রত্যেক পার্ট এর SOD বার করব তারপরে গুণ করে রেজাল্ট দিব ।

আর যেহেতু মান অনেক বড় হতে পারে তাই আমরা ব্যবহার করব, modular arithmetic প্রত্যেকটি পার্ট এর SOD বার করার জন্য ।

এর জন্য আমরা এক্সটেণ্ডেড ইউক্লিড অথবা ফার্মেটের লিটল থিওরেম ব্যবহার করতে পারব ।

আমার সলিউশনঃ  https://ideone.com/nw2KGX

Lightoj 1067 Combinations:

Tag: Number Theory, Modular arithmetic

Algorithm:

nCr = n ! (r ! * (n-r)!)

তাহলে আমাদের আগে থেকেই  n! এর মান আমরা মড করে করে প্রিক্যালকুলেট করে রাখব ।

তা থেকে আমরা r! , (n-r)! এর মান ও পেয়ে যাব . এর পরে আমরা এদের মডিউলার ইনভার্স বের করব । আর সেম জিনিস যাতে বারবার হিসেব করতে না হয় আমরা প্রিক্যালকুলেট করে রাখতে পারি অথবা একবার বের করা হলে সেভ করে রাখতে পারি ।

আমার সলিউশনঃhttps://ideone.com/7k9opq

Codeforces 722D Generating Sets:

এই প্রবলেমটাতে মূলত বলা হয়েছে, একটা অ্যারে দেয়া আছে (Y)  । আমাকে আরেকটা অ্যারে তৈরী করতে হবে (X), যা থেকে আমি নিম্নরূপ অপারেশন চালিয়ে Y অ্যারেকে আউটপুট দিতে পারি ।

যে কোন নাম্বারকে (xi) কে আমি চাইলে (2 * xi) অথবা (২ * xi + 1)  বানাতে পারি । আর এভাবে করে বানিয়ে যাতে আমার রেজাল্ট অ্যারে থেকে আমি আমার মেইন অ্যারে (Y) কে যাতে বানাতে পারি । আর এই X অ্যারের মানগুলো মিনিমাইজ করতে হবে ।

এখন আমি যদি আমাদের দুইটা অপারেশন কে মার্জ করি তাহলে বলতে পারি, যে কোন নাম্বারকে মূলত (yi) , floor(yi/2), floor(yi/4),…., floor(yi/2^i),……1 এদের মধ্যের যে কোন একটা দিয়ে বানানো সম্ভব । তো এই হিসেবে আমাদের গিভেন অ্যারে ও একটা সলিউশন । আমাদের কাজ এটাকে মিনিমাইজ করা আর এমন ভাবে করা যাতে সবগুলো এলিমেন্ট ডিসটিঙ্কট হয় ।

তো আমরা –

১. একটা অর্ডার্ড সেট রাখব । সেট এ প্রথমে থাকবে আমাদের দেয়া Y এর মানগুলো ।

২. আমরা সবচেয়ে বড় ভ্যালুগুলোকে নিব আর ২ দিয়ে ভাগ করে করে দেখব যে যেই ছোট মানগুলোকে দিয়ে এটাকে বানানো সম্ভব সেটা অ্যারেতে প্রেসেন্ট কিনা । যদি না হয় তাহলে বুঝলাম আমরা এই ভ্যালুকে আরো কম কোন মান দিয়ে বানাতে পারি । এটাকে সেট এ পুশ করে বড় মানটাকে ইরেজ করব ।

৩.এভাবে প্রতি কলে আমরা একটা ডিস্টিঙ্কট আর মিনিমাইজড সেট পেতে থাকব । যদি কোন ধাপে দেখি এমন কোন ছোট মান পাওয়া যায় নাই যেটা সেটে নেই । তাহলে বুঝব আমাদের কাজ শেষ । আমরা এক্সিকিউট করব । কারণ সব থেকে বড়টাকে যদি ছোট করতে না পারি, তাহলে আর বাকি কোনটাকে ছোট করা সম্ভব না ।

আমার সলিউশনঃ https://ideone.com/lsjW9Z

Lightoj 1301 Monitoring Process:

Tag: Greedy, Data Structure

প্রথম প্রসেসঃ (গ্রিডি)

সবগুলো সময়কে একটা অ্যারেতে সর্ট করে রাখি আর কোনটা কি ধরণের সময় সেটা রাখি, সেম সময় হলে শুরুর সময় কে আগে রাখি ।

এরপরে ২টা ভ্যারিয়েবল রাখি, এখন পর্যন্ত ফ্রী কয়জন আর ইমপ্লয় করেছি কয়জনকে । যখন আমি একটা সময় পাব যদি সেটা শুরু হয় তাহলে দেখব কেও ফ্রী আছে কিনা, ফ্রি থাকলে ফ্রি থাকা লোক এক কমাবো আর ফ্রী না থাকলে নতুন লোককে এমপ্লয় করব । এভাবে এমপ্লয় সংখ্যাই আমার সলিউশন ।

আমার সলিউশনঃ https://ideone.com/2iCKhH

দ্বিতীয় প্রসেসঃ (ডাটা স্ট্রাকচার)

একটা প্রায়োরিটি কিউ রাখব যেটা সবসময় মিনিমাম এন্ডিটাইম গুলোকে সামনে রাখবে যাদের চেক করা হয়েছে তার বেসিসে ।

কোন স্টার্টিং টাইম চেক করার সময় যদি দেখে এখন পর্যন্ত মিনিমাম শেষ সময় থেকে এটা বড় তাহলে ঐ কাজ যে করছিল তার কাজ শেষ সে এখন এই কাজ করতে পারবে । নতুন কাউন্ট বাড়াতে হবে না । আর এই প্রসেসের ফিনিশিং টাইম প্রায়োরিটি কিউতে পুশ করে রাখব । এভাবে অলটাইম দেখব এখন পর্যন্ত মিনিমাম শেষ সময় থেকে স্টার্টিং সময় যদি ছোট হয় তাহলে আগের ওই ব্যক্তিই কাজ করতে পারবে । আর এই প্রসেস এক্সিকিউট হচ্ছে বিধায় তাকে প্রায়োরিটি কিউতে পুশ করে রাখব । আর না হলে কাউন্ট ++ করে আমি কিউতে পুশ করব ।

আমার সলিউশনঃ https://ideone.com/uWAJTY