Lightoj 1289 solution in Bangla

Lightoj 1289 - LCM from 1 to n solution in Bangla

Problem Link: Lightoj 1289

Click here to see the discussion in English 

প্রবলেমটিতে আমাদেরকে একটি সংখ্যা  n দেয়া থাকবে । আমাদেরকে ১ হতে সেই সংখ্যা অবধি ল.সা.গু (LCM) বের করতে হবে। প্রবলেমটি সমাধান করার শুরুতেই আমরা Constrains এর দিকে যদি দেখি , সেখানে  n হতে পারে 10^8 । আর টেস্টকেসের সংখ্যা হতে পারে 10^4 । তো আমরা যদি সাধারণ ভাবে লুপ চালিয়ে LCM বের করতে যাই তাহলে আমরা TLE খেয়ে যাবো সেটা নিশ্চিত । তো এখন আমরা কি করতে পারি ?? 🤔 

আচ্ছা এবার আমরা ২টো সংখ্যার মধ্যে LCM এবং GCD বের করা শিখি (আসলে আমরা সবাই সেটা জানি । 😜 

তো মনে করি দুটো সংখ্যা a এবং b । আমরা জানি যে , যেকোনো সংখ্যাকে prime সংখ্যার গুনাকারে প্রকাশ করা যায় । 

তাহলে আমরা a এবং b  কে লিখতে পারি ,

a = p1^x1 * p2^x2 * ......

b = p1^y1 * p2^y2 * ......

এখন gcd_of_x_y = p1^min(x1,y1) * p2^min(x2,y2) * ......

এবং lcm_of_x_y = p1^max(x1,y1) * p2^max(x2,y2) * ......

উদাহরণ হিসেবে ১৬ এবং ২০ এর gcd এবং lcm বের করি, 

Prime factorization of 20 = 2^2 * 5

Prime factorization of 14 = 2 * 7

gcd_of (20,14) = 2^min(1,2) * 5^min(1,0) * 7^min(0,1)

                        =2^1 * 5^0 * 7^0

    

                        =2

lcm_of(20,14)= 2^max(1,2) * 5^max(1,0) * 7^max(0,1)

                        =2^2 * 5^1 * 7^1

                        =4*5*7

                        =140

তো আমরা দুটো সংখ্যার কিভাবে lcm এবং gcd বের করতে হয় শিখে গেলাম। এখন অনেক গুলো সংখ্যার জন্যও সেইম টেকনিক ।

a = p1^x1 * p2^x2 * ......

b = p1^y1 * p2^y2 * ......

c = p1^z1 * p2^z2 * ......

b = p1^m1 * p2^m2 * ......

gcd_of(a,b,c,d) = p1^min(x1,y1,z1,m1) * p2^min(x2,y2,z2,m2) * ......

lcm_of(a,b,c,d) = p1^max(x1,y1,z1,m1) * p2^max(x2,y2,z2,m2) * ......

তো আমাদের প্রবলেমটিতে আমাদের lcm বের করতে হবে । সেইজন্য আমাদের ১ থেকে n অবধি সব সংখ্যার প্রাইম গুলোর ম্যাক্সিমাম পাওয়ার জানতে পারলেই আমরা এটা বের করতে পারবো ।সেইজন্য তো আবার সব সংখ্যাগুলোকে prime factorize করে দেখতে হবে । সেটাও তো অনেক সময়ের ব্যাপার মানে TLE । এখন কি করা যায় 🤔।

আচ্ছা আমরা n =10  এর জন্য একটু চেষ্টা করে দেখি তো , 

1 = 2^0 * 3^0 *...😜 

2 = 2^1

3 = 3^1

4 = 2^2

5 = 5^1

6 = 2*3

7 = 7^1

8 = 2^3

9 = 3^2

10 = 2*5

LCM_of(1,2,....,10)  = 2^3 * 3^2 * 5 * 7

                                = 2520

১০ এর থেকে ছোট বা সমান প্রাইম আছে  ৪ টি (২,৩,৫,৭)

এবার যদি lcm  এর দিকে থাকাই , lcm এ ২,৩,৫,৭ মিনিমাম ১ বার করে আছেই ।

তাহলে আমরা বলতে পারি lcm এ তার থেকে ছোট বা সমান প্রাইম সংখ্যা গুলো একবার অন্তত থাকবেই । সেইজন্য আমরা এটাকে  precalculate করে রাখতে পারি ।

কিন্তু  lcm_of (1,2,..10) তে তো 2^3 এবং 3^2 আছে । আমরা সেটা কিভাবে পাবো 🤔।

আচ্ছা আমরা ১০ কে ২ দিয়ে কয়বার ভাগ করতে পারি ??

১০/২=৫

৫/২=২

২/২=১

মানে ১০ কে আমরা ৩ বার ভাগ করতে পারি ২ দিয়ে । 

এবার ১০ কে ৩ দিয়ে ভাগ কয়বার ভাগ করতে পারি ।

১০/৩=৩

৩/৩=১

তাহলে ১০ কে ৩ দিয়ে ২ বার ভাগ করা যাচ্ছে । 

আমরা কি এর পরের প্রাইম গুলো দিয়ে চেক করবো??

নাহ , করবো নাহ। কারণ আমরা ১০ থেকে ছোট বা সমান প্রাইমগুলো আগেই precalculate করে রাখবো আর সেখান থেকে ব্যবহার করবো ।

তো কত অবধি প্রাইম গুলো দিয়ে চেক করবো সেটা কতবার ভাগ যাচ্ছে??

সেটা হবে sqrt(n) । কারণ এর চেয়ে বড় কোন প্রাইমের পাওয়ার ২ হলেই সেটা n থেকে বড় হয়ে যাবে ।  

এবার দেখি Precalculate  করছি টা কি

প্রথমেই আমরা 10^8  অবধি সব প্রাইম বের করে নিবো ।

তারপর একটা অ্যারেতে প্রাইম গুলোকে গুনকারে রাখবো , তাহলে প্রতিটি প্রাইম একবার করে গুনাকারে পেয়ে যাবো।

    store[i]=store[i-1]*prime[i]; 

  

যেহেতু আমরা একবার করে প্রাইম রেখে দিচ্ছি , তাই পরে যখন আবার sqrt(n)  এর আগের প্রাইম গুলো দিয়ে চেক করবো , তখন একবার ভাগ করে নিবো । 

প্রবলেমে আমাদেরকে  2^32  দিয়ে mod  করতে বলেছে । সেটা আমরা  unsigned int  নিলে অটোমেটিক হয়ে যাবে । 

আশা করি প্রবলেমটি এবার সমাধান করতে পারবো । 

বুঝতে পারলেও কমেন্ট করতে পারেন , বুঝতে না পারলেও কমেন্ট করতে পারেন কি বুঝেন নি সেটা । 

'

null

Read More

Lightoj 1004 Solution in Bangla

Lightoj 1004 Solution in Bangla

Problem Link: Lightoj 1004

Click here to see the discussion in English

প্রথমেই বলে নেই এটা একটি সহজ DP (Dynamic প্রব্লেম)। Rock Climbing জেনে থাকলে সহজেই এটি করতে পারবে । আর না জেনে থাকলে আগে পড়ে আসলে ভালো  হয় ।  বাংলায় এটা নিয়ে ব্লগ আছে হয়তো । যাই হোক  প্রব্লেম নিয়ে আলোচনায় আসি । এখানে একটি ডায়মন্ড শেপের একটি 2d অ্যারে দেয়া আছে । অ্যারের সেল গুলোতে কলা রাখা আছে ।  একটি বানর তার নিচের দিকের adjacent cell গুলোতে যেতে পারে ।  একটি সেল থেকে অন্য সেলে যাওয়ার সময় বানরটি সেই সেলের সব গুলো কলা খেয়ে নিবে । 

নিচের ছবিতে বুঝা যাচ্ছে বিষয়টা । এখন আমাদের কাজ হলো বানরটি সবচেয়ে বেশি কতটি কলা খেতে পারে সেটি বের করা । আমাদের মনে রাখতে হবে বানরটি নিচের দিকে adjacent সেলেই যেতে পারে শুধু । 

                                                             

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

এখন মনে করি আমরা এখন [1,1] সেলে আছি । যেখানে ৭টি কলা আছে । এখন এই সেল থেকে আমরা দুটো সেলে যেতে পারবো ([২,১] ,[২,২]) । এখন আমরা যদি কোন ভাবে বের করতে পারি আমাদের [২,১] এ গেলে লাভ হবে নাকি [২,২] গেলে লাভ হবে ,যেহেতু এখন আমাদের যেকোনো একটি পথে যেতে হবে কারণ আমাদের প্রব্লেমে বলাই আছে আমরা শুধু নিচের দিকের adjacent সেলে যেতে পারবো । তাই আমরা আমাদের সেলের নিচের adjacent সব গুল দিয়েই চেক করবো তবেই তো আমরা বের করতে পারবো আমাদের কোন পথে বেশি কলা আছে।   

এটা recursion দিয়েই করা যাবে ।  আশা করি  recursion জানো । না জানলে আগে recursion জেনে আসো ।
Function:

এখানে ডায়মন্ড শেপের জন্য দুটি কন্ডিশন ব্যবহার করতে হয়েছে । আশা করি সেটা বুঝতে পারছো ।  এই ফাংশনটি দিয়ে যদি আমরা প্রদত্ত টেস্ট কেস রান করি আমাদের সঠিক আউটপুট দিবে । কিন্তু এটা দিয়ে যদি তুমি সাবমিট দাও সুন্দর করে একটা TLE খাবে ।  এর কারণ বুঝার জন্য তুমি প্রবলেমটি আবার পড়ো।
এই TLE থেকে মুক্তি পাওয়ার  জন্যই আমাদের DP অ্যারে ব্যবহার করতে হবে । আমরা একই কাজ বারবার করবো নাহ,বলেই DP ব্যবহার করবো । এখানে recursion ব্যবহার করে যে কোড দেখানো আছে সেখানে আমরা প্রতিটি সেলে বার বার যাচ্ছি ।  শুরুতেই , রো আর কলাম প্রিন্ট করে দেখতে পারো । তাই আমরা ফাংশনে আগেই দেখে নিবো এই সেলে আমরা এসেছি কিনা । এসে থাকলে আমরা আর নিচের দিকে যাবো নাহ । কারণ আমরা যদি এই সেলে আগেই একবার ঘুরে থাকি তাহলে এর নিচের সেল গুলোতেও ঘুরে এসেছি এবং আমরা জানি কি পরিমাণ কলা আমরা পেতে পারই এই পথে ।আর  এই জানাটা মনে রাখবো আমরা DP  অ্যারে দিয়ে । নিচের সোর্সকোড দিয়ে দিলাম ।

Read More

Lightoj 1072 solution in bangla

Lightoj 1072 solution in bangla

Problem Link: Lightoj 1072

Click here to see the discussion in English

প্রবেলমটিতে আমাদেরকে বাইরের বৃত্তের ব্যাসার্ধ এবং কতটি  বৃত্ত  আছে বাইরের বড় বৃত্তের ভিতরে সেই বৃত্তের সংখ্যা  দেয়া আছে । আমাদেরকে  ভিতরের ছোট  বৃত্তটির ব্যাসার্ধ বের করতে হবে।

আমরা জানি যে, একটি পূর্ণ বৃত্ত ৩৬০ ডিগ্রি হয়ে থাকে। 
উদাহরণ থেকেই জানা যাক,

ভিতরের ছয়টি বৃত্ত বাইরের বড় বৃত্তটিকে ৬ টি ভাগে ভাগ করেছে।  

তাহলে ভিতরের একটি বৃত্তের পরিধির সাথে বাইরের বড় বৃত্তের কেন্দ্র কত ডিগ্রী কোণ তৈরি করে??

তা হবে ৩৬০ কে n  দিয়ে ভাগ করলে যতো হয় ততো। 

আর আমরা যদি বলি  ভিতরের বৃত্তের কেন্দ্র এবং পরিধির সাথে  বাইরের বড় বৃত্তের কেন্দ্রটি কত ডিগ্রী কোণ তৈরি করে??

360

2*n

or, 180/n

or,   π/n

 এখন শুধু একটি ত্রিকোণোমিতি জানলেই হবে ।
আমরা কোণ পেয়ে গেলাম , θ = π/n;
Sin θ কে লিখা যায় লম্ব / অতিভুজ হিসেবে ।
এখানে লম্ব  r, আর অতিভুজ  R-r, 
R হলো বাইরের বৃত্তের ব্যাসার্ধ আর r হলো ভিতরের বৃত্তের ব্যাসার্ধ ।

Sin θ = r/(R-r)
or, Sin(PI/n) = r/(R-r)
or,  r = sin(PI/n)*(R-r) 
or,  r= (R*sin(PI/n)) – (r*sin(PI/n))
or,  r + r*sin(PI/n)  = R*sin(PI/n)
or,  r(1+sin(PI/n)) =R*sin(PI/n)
or,  r=(R*sin(PI/n)) / (1+sin(PI/n))
তাহলে আমরা পেয়ে ভিতরের ছোট বৃত্তের ব্যাসার্ধ ।

Source Code:

এই প্রবলেমটির মতো একই রকম আরেকটি প্রবলেম ।
Problem Link :  codeforces 1100 C

Source Code : SourceCodeLink

Read More

Lightoj 1331 solution in bangla

 

Lightoj 1331 Ajent J 

Problem Link

Click here to see the discussion in English

হৃতিক রোশানের ধুম ২ সিনেমাতে ডায়মন্ড চুরির  দৃশ্যটি অনেকেই দেখেছো । Lightoj এর 1331 নাম্বার প্রবলেমটি একটি ডায়মন্ড চুরি নিয়ে। 

এখানে একজন এজেন্ট 'J ' আছে, যে কিনা মিউজিয়াম ডায়মন্ডটি চুরি করতে চায় । যদিও এই চুরিটা করা এতোটা সহজ নয়। কারণ,এখানে ৩টি বৃত্তাকার লেজার স্ক্যানার আছে, যেগুলো অনবরত ঘুরছে।স্ক্যানার ৩টি এমনভাবে বসানো যাতে বৃত্তাকার স্ক্যানার ৩টি চিত্রের মতো প্রতিটিই বাহ্যিকভাবে এক অপরকে স্পর্শ করে। আর ডায়মন্ড আছে সেই ৩টি বৃত্তাকার স্ক্যানার এর মাঝখানে রাখা হয়েছে।এখন আমাদেরকে সেই আবদ্ধ স্থানটি (রঙিন এরিয়া) পরিমাপ করতে হবে।যেখানে আমাকে ৩টি বৃত্তাকার স্ক্যানার এর ব্যাসার্ধ দেয়া আছে R1,R2,R3 ।

তো আমরা কিভাবে সমস্যাটি সমাধান করবো  ?

এই সমাধানের জন্য আমাদেরকে একটুখানি জ্যামিতির জ্ঞান থাকলেই হবে ।

প্রথমত ,আমরা যদি প্রতিটি বৃত্তের কেন্দ্রকে অপর দুটি বৃত্তের কেন্দ্রের সাথে যোগ করি ,তবে আমরা একটি ত্রিভুজ পাবো নিচের চিত্রের মতো । এখন শুধু ত্রিভুজের ক্ষেত্রফল থেকে , ত্রিভুজের মধ্যে অবস্থিত বৃত্তের অংশগুলো বাদ দিয়ে দেই তাহলেই আমরা ডায়মন্ডের  এরিয়া পেয়ে যাবো ।
এখন ,
    R1 ও R2 বৃত্তের মধ্যকার বাহুকে ধরি , a
    R2 ও R3 বৃত্তের মধ্যকার বাহুকে ধরি , b
    R1 ও R3 বৃত্তের মধ্যকার বাহুকে ধরি , c
 
 
    

           

           তাহলে,

                    a=r1+r2
b=r2+r3
c=r3+r1

এখন তিনটি বাহুর দৈর্ঘ্য দেয়া থাকলে আমরা
ত্রিভুজটির ক্ষেত্রফল বের করতে পারি ,এর
জন্য প্রথমেই আমাদের পরিসীমা বের করতে
হবে ।

 

পরিসীমা P=a+b+c

তাহলে ত্রিভুজটির ক্ষেত্রফল হবে,

area=sqrt(s*(s-a)*(s-b)*(s-c))

যেখানে s হচ্ছে পরিসীমার অর্ধেক ।

s= p/2

এখন আমরা ত্রিভুজটির ক্ষেত্রফল জানি ।

মাধ্যমিক শ্রেণির জ্যামিতি থেকে আমরা বৃত্তকলার
ক্ষেত্রফল সম্পর্কে জানি । এখানে বৃত্তকলার
ক্ষেত্রফল দিয়ে আমরা ত্রিভুজের অন্তর্গত বৃত্তের
অংশের ক্ষেত্রফল জানতে পারি ,

সে জন্য আমাদের সুত্র হলো,

বৃত্তকলার ক্ষেত্রফল = (১/২)* ব্যাসার্ধ * ব্যাসার্ধ * বৃত্তকলার অন্তর্ভুক্ত কোণ

এখন আমাদের প্রতিটি বৃত্তের জন্য বৃত্তকলার
ক্ষেত্রফল বের করতে হলে ,আমাদের বাহুগুলির
অন্তর্ভুক্ত কোণগুলি জানতে হবে । আর সেজন্য
আমরা জানি,

cos(C) = a² + b² − c²2ab

cos(A) = b² + c² − a²2bc

cos(B) = c² + a² − b²2ca

তাহলে ,
                 area1=.5*r1*r1*acos((c*c+a*a-b*b)/(2*c*a))
এখানে
acos((c*c+a*a-b*b)/(2*c*a))
দ্বারা cos^-1((c*c+a*a-b*b)/(2*c*a))কে
বুঝানো হয়েছে।

acos সি/সি প্লাস প্লাস প্রোগ্রমিং এর ফাংশন ।

area2=.5*r2*r2*acos((b*b+a*a-c*c)/(2*a*b))

area3=.5*r3*r3*acos((c*c+b*b-a*a)/(2*b*c))

এখন , ত্রিভুজের ক্ষেত্রফল থেকে বৃত্তকলার
ক্ষেত্রফলগুলো বিয়োগ করলেই আমাদের
ডায়মন্ডের এরিয়াটুকু পেয়ে যাবো।


For source code: Source code

Read More