Bappy's Blog

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে একটি ইন্টিজার অ্যারে দেয়া থাকবে যেখানে দুটি সংখ্যা ব্যাতিত বাকি সংখ্যাগুলো দুইবার করে থাকবে এবং ঐ দুটি সংখ্যা একবার করে থাকবে। বলতে হবে সংখ্যা দুটি কি কি? আমাদেরকে এই কাজ O(n) Time Complexity এবং O(1) Memory Complexity তে করতে হবে।  Solution: আমরা জানি, একই সংখ্যাকে জোড় সংখ্যক বার এক্সর করলে ফলাফল শূন্য হয়। ধরে নেই, অ্যারেতে একবার করে থাকা সংখ্যা দুটি x এবং y । তাহলে, z = a[1] ^ a[2] ^ ... ^ a[n] = x ^ y এখন, যেহেতু সংখ্যা দুটি একবার করে আছে তার মানে x এবং y দুটি ভিন্ন সংখ্যা! সুতরাং, তাদের এক্সর করলে অন্তত এমন একটি বিট থাকবে যে বিট সংখ্যাদ্বয়ের মধ্যে তফাৎ গড়ে দিবে! তাই, z = x ^ y হলে z এর সর্বডানের কোন বিট টি অন আছে সেটি দেখবো। মনে করি, z = x^y এর সর্বডানের অন বিট টি হলো kth Bit এখন, তাহলে অ্যারের যেসব সংখ্যার kth Bit অন তাদের এক্সর করলে সেটি হবে দুটির সংখ্যার একটি সংখ্যা x । কারণ , x ভিন্ন অন্য কোন সংখ্যার kth Bit ON থাকলেও সেটি দুইবার থাকবে যেকারণে সেখানে শুধু x ই থেকে যাবে।  এখন অপর সংখ্যা y...

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে একটি ইন্টিজার অ্যারে দেয়া থাকবে যেখানে একটি সংখ্যা বাদে বাকি সংখ্যাগুলো এক্সেক্টলি দুইবার করে থাকবে এবং ঐ সংখ্যাটি একবার থাকবে।  আমাদেরকে একবার থাকা সংখ্যাটি বের করতে হবে। O(n) Time Complexity এবং O(1) Memory Complexity তে কাজটি করতে হবে।  Solution: বিটওয়াইজ অপারেশনগুলো নিয়ে মোটামুটি ধারণা আছে এমন যেকেউ প্রথম দেখায় প্রব্লেমটি সলভ করতে পারবে। আমরা জানি, 1 XOR 1 = 0 0 XOR 0 = 0 1 XOR 0 = 1 0 XOR 1 = 1 বিটওয়াইজ এক্সর এর ফর্মুলা গুলো জানা থাকলে দেখবে যে একই সংখ্যা দুইবার এক্সর করলে ফলাফল শূন্য! আসলে, দুইবার নয়। যেকোন জোড় সংখ্যকবার একটি সংখ্যাকে এক্সর করলে ফলাফল শূন্য। যেহেতু, অ্যারে তে ১টি সংখ্যা বাদে বাকিসব সংখ্যা ই দুইবার করে আছে সেহেতু অ্যারের সবগুলো সংখ্যা এক্সর করলে যে সংখ্যাটি পাওয়া যায় সেটিই আমাদের কাঙ্ক্ষিত সংখ্যা। 

এই পর্বে আমরা খুবই ইন্টারেস্টিং একটি বিষয় নিয়ে আলোচনা করবো।  মনে করো, তোমাকে একটি  n * m সাইজের গ্রীড দেয়া আছে। গ্রীডের প্রতিটি সেল এর ভ্যালু,   grid[i][j] = i+j তাহলে, একটি ৩ * ৩ সাইজের গ্রীড দেখতে যেমন হবেঃ  একটি মজার বিষয় লক্ষ্য করেছো কী? কোন একটি সেলের ভ্যালু যদি জোড় হয় তবে তার এডজাসেন্ট সেলগুলোর ভ্যালু বিজোড়। আর কোন সেলের ভ্যালু যদি বিজোড় হয় তবে তার এডজাসেন্ট সেলের ভ্যালু জোড়। এখানে দুটি সেল তখনই এডজাসেন্ট বিবেচ্য হবে যখন তারা একটি সাইড শেয়ার করে।  গ্রীডের এই প্রোপার্টি টা খুবই সিম্পল। কিন্তু, আমরা অনেকেই হয়তো খেয়াল করি নি এর আগে। আর এটি কতোটা গুরুত্বপূর্ণ প্রোপার্টি তা  এই প্রব্লেম  সলভ করতে গিয়ে অনুধাবন করেছি 😛 হ্যাপি কোডিং 😊

Problem: এই প্রব্লেমে মূলত আমাকে 100 x 100 সাইজের একটি 2D অ্যারে দেয়া থাকবে। আমাকে ঐ অ্যারে তে এমন একটি আয়ত (Rectangle) নির্বাচন করতে হবে যাতে তার সংখ্যাগুলোর যোগফল সর্বোচ্চ হয়। যেমনঃ উপরোক্ত 3 x 5 সাইজের 2D অ্যারের জন্য সম্ভাব্য সকল আয়তের মধ্যে সবুজ চিহ্নিত আয়তের সংখ্যাগুলোর যোগফল সর্বোচ্চ।  Solution: 1D অ্যারে তে  Maximum Sub-Array Sum  বের করতে পারলে এই প্রব্লেমটি O(n^3) কমপ্লেক্সিটি তে সলভ করা সম্ভব।  আমরা একটি আয়ত নির্বাচন এর জন্য তার Upper & Lower Row দুইটি ফিক্স করবো। এরপর, নতুন একটি অ্যারে তৈরী করবো। ঐ অ্যারের i'th Element হবে i'th Column বরাবর Upper Row to Lower Row এর সংখ্যাগুলোর যোগফল। এখন, এই নতুন অ্যারের  Maximum Sub-Array Sum  বের করে এন্সার কে ম্যাক্সিমাইজ করার চেষ্টা করবো। এভাবে, সম্ভাব্য সকল (Upper Row, Lower Row) = (i , j) কম্বিনেশন এর জন্য কাজ করলেই আমরা আমাদের মূল রেজাল্ট পেয়ে যাবো।  কোডটি দেখতে যেমন হবেঃ  Happy Coding

Problem: এই প্রব্লেমে আমাকে একটি অ্যারে দেয়া থাকবে। ঐ অ্যারের এমন একটি সাব-অ্যারে নির্বাচন করতে হবে যার সংখ্যাগুলোর যোগফল সর্বনিম্ন হয়।  Solution: Maximum Sub-Array Sum  এই পর্বটি পড়ে থাকলে এই প্রব্লেম সলভ করা খুবই সহজ। কীভাবে? ১) অ্যারের প্রতিটি সংখ্যার সাথে -১ গুণ করবো। অর্থাৎ, পজিটিভ সংখ্যাগুলোকে নেগেটিভ বানাবো আর নেগেটিভ গুলোকে পজিটিভ।  ২) তারপর, পরিবর্তিত এই অ্যারের  Maximum Sub-Array Sum  ক্যালকুলেট করবো। ৩) প্রাপ্ত রেজাল্ট কে -১ দ্বারা গুণ করবো। কাজ শেষ 😛

Problem: আমাকে একটি অ্যারে দেয়া থাকবে। ঐ অ্যারের এমন একটি সাব-অ্যারে নির্বাচন করতে হবে যার সংখ্যাগুলোর যোগফল সর্বোচ্চ হবে।  Solution: এটি খুবই কমন একটি প্রব্লেম যার অনেকগুলো সমাধান সম্ভব। তাই বিস্তারিত না বলে সরাসরি কোডে যাচ্ছি। আশা করি কোড দেখেই বুঝতে পারবেঃ 

এই পর্বটি পড়ার আগে  বিটসেট   সম্পর্কে ভালো আইডিয়া থাকা জরুরী।    Problem:  একটি গ্রাফ দেয়া থাকবে n < = 2000 ভার্টেক্স এবং m < = (n*(n-1))/2 এজ এর। গ্রাফটিতে কয়টি ত্রিভুজ আছে? অর্থাৎ, এমন কয়টি ভার্টেক্স সেট {u,v,w} আছে যেখানে u-v, v-w, w-u এজ দ্বারা কানেক্টেড।  Solution: গ্রাফের প্রতিটি ভার্টেক্স এর এডজাসেন্সি লিস্ট টাকে বিটসেট দিয়ে রিপ্রেজেন্ট করতে হবে। অর্থাৎ, প্রতিটি নোডের জন্য একটি করে বিটসেট ডিক্লেয়ার করতে হবে। সেই নোডের সাথে যেসব নোড কানেক্টেড তার সেসব পজিশন এর বিট অন করে দিবো। এরপর, n^2 লুপ চালিয়ে দেখবো প্রতি জোড়া কানেক্টেড নোড (u,v) এর জন্য তাদের বিটসেটে কমন কয়টি পজিশন এর বিট অন আছে যেখানে u<v ।  অর্থাৎ, ঐ কমন নোডগুলো এদের উভয়ের সাথে কানেক্টেড। এবং কানেক্টেড হয়ে ত্রিভুজ উৎপন্ন করেছে। এই সংখ্যা এন্সার এর সাথে যোগ করবো। ভালোভাবে লক্ষ্য করলে দেখবে যে, এই পদ্ধতিতে প্রতিটি ত্রিভুজ ৩বার করে গণনা হয়। তাই এন্সার কে ৩ দ্বারা ভাগ দিলেই কাজ শেষ!  এবার কোড দেখা যাকঃ 

একটি সংখ্যা x কে ০ না হওয়া পর্যন্ত সর্বোচ্চ কতবার অন্য একটি পজিটিভ সংখ্যা(যা ঐ সংখ্যার সমান অথবা ছোট) দ্বারা মড করা যায়?  মনে করি, x = 16 এখন, x কে কোন সংখ্যা দ্বারা ভাগ করলে ভাগশেষ সব থেকে বড় হয়? 9 দ্বারা।  তাহলে, x = 16%9 = 7 এখন, x কে কোন সংখ্যা দ্বারা ভাগ করলে ভাগশেষ সব থেকে বড় হয়? 4 দ্বারা। তাহলে, x = 7%4 = 3 এখন, x কে কোন সংখ্যা দ্বারা ভাগ করলে ভাগশেষ সব থেকে বড় হয়? 2 দ্বারা। তাহলে, x = 3%2 = 1 এখন, x কে কোন সংখ্যা দ্বারা ভাগ করলে ভাগশেষ সব থেকে বড় হয়? 1 দ্বারা। তাহলে, x = 1%1 = 0 ভালোভাবে লক্ষ্য করলে দেখবে যে, প্রতি মডেই সংখ্যাটি অর্ধেক এর থেকেও ছোট হয়ে যাচ্ছে!  তার মানে, একটি সংখ্যাকে ০ না হওয়া পর্যন্ত আমি সর্বোচ্চ Log(X) বার ভাগ করতে পারি! বলে রাখা ভালো এখানে Log এর বেইস ২। এই অবজার্বেশন অনেক সময় বিভিন্ন প্রব্লেমের সাবপ্রব্লেম সলভ করা সহজ করে দেয়।  Happy Coding😀

Problem:   (A * B)%M এর ভ্যালু কত সেটা বের করতে হবে যেখানে A<=1e18 , B<=1e18 , M<=1e18 Solution:  খুব ভালোভাবে বোঝা যাচ্ছে যে, ওভারফ্লো ই এই সমস্যার মূল সমস্যা -_- এখন, একটু ভিন্নভাবে চিন্তা করি প্রব্লেমটাকে।  x + x + x + x + x = 5x ৫ টা x যোগ করে পাওয়া যোগফল আর x এর সাথে ৫ গুণ করে পাওয়া গুণফল সমান। এটিই এই সমস্যা সমাধানের মূল কনসেপ্ট!  তার মানে, A*B হচ্ছে,  B সংখ্যাক A এর যোগফল। এখনো মাথায় না ঢুকলে কোড দেখতে পারোঃ

1. Intersection Of Two Segment: একমাত্রিক তলে দুইটি সেগমেন্ট (l1 , r1) এবং (l2 , r2) হলে, Segment-1:     ------------- Segment-2:               --------------- Intersect:                 ------- l = max(l1 , l2) r = min(r1 , r2) (l > r) হলে, Intersection   = 0 অন্যথায়, Intersection       = [l , r] 2. Intersection Of Two Rectangle: দ্বিমাত্রিক তলে অবস্থিত দুইটি আয়তের Upper Left Corner এবং Lower Right Corner এর স্থানাঙ্ক দেয়া থাকলে তাদের Intersection Area অথবা তাদের মধ্যকার কমন আয়তের জন্য বিন্ধু দুটি বের করতে হবে।  ১ম আয়তের বিন্ধু দুটি (x11 , y11) এবং (x12 , y12) ২য় আয়তের বিন্ধু দুটি (x21 , y21) এবং (x22 , y22) Intersect করা অংশটিকে আয়ত ধরলে সেই আয়তের বিন্ধু দুটি হবে, (x31 = max(x11 , x21) , y31 = min(y11 , y21)) এবং (x32 = min(x12 , x22) , y32 = max(y12 , y22)) IF(x31 > x32 || y31>y32)     No Intersection else     [(x31,y31) - (x32...

Prefix Sum: মনে কর, তোমাকে একটা অ্যারে দেয়া আছে 10^5 সাইজের। এবং 10^5 সংখ্যক কুয়েরী দেয়া থাকবে। প্রতি কুয়েরী তে left এবং right দুইটা ভ্যারিয়েবল দেয়া থাকবে। বলতে হবে,  ara[lft] + ara[lft+1] + --- + ara[rgt-1] + ara[rgt] = কত? মানে, left থেকে right তম ইনডেক্স পর্যন্ত সাবঅ্যারে টার যোগফল কত?  এই কাজটিই আমরা Prefix Sum দ্বারা করতে পারি। যেখানে, PrefixSum[i] =  1 থেকে i তম ইনডেক্স পর্যন্ত অ্যারের এলিমেন্টগুলোর যোগফল। তাহলে, আমরা লিখতে পারি, PrefixSum[i] = PrefixSum[i-1] + ara[i] Sum[l...r] = PrefixSum[r] - PrefixSum[l-1] Prefix XOR: Prefix XOR টার্মটাও মোটামুটি Prefix Sum এর অনুরূপ। এই প্রব্লেমে আমাকে বার বার কুয়েরী করা হবে left থেকে শুরু করে right পর্যন্ত অ্যারের সংখ্যাগুলোর XOR কত?  এই কাজটি আমরা করবো Prefix XOR দিয়ে। যেখানে, PrefixXOR[i] = 1 থেকে i তম ইনডেক্স পর্যন্ত অ্যারের এলিমেন্টগুলোর XOR। তাহলে, PrefixXOR[i] = PrefixXOR[i-1] ^ ara[i] XOR[l...r] = PrefixXOR[r] ^ PrefixXOR[l-1]

একটি ত্রিভুজের শীর্ষত্রয়  A,B,C  এবং অপর একটি বিন্ধু D এর স্থানাঙ্ক দেয়া আছে বের করতে হবে  D  বিন্ধু ত্রিভুজের অভ্যন্তরে অবস্থিত কি না। আইডিয়া-১ঃ  যদি, ত্রিভুজ ক্ষেত্র ABC = ত্রিভুজ  ক্ষেত্র   ABD + ত্রিভুজ  ক্ষেত্র   ADC + ত্রিভুজ  ক্ষেত্র   BCD হয় তবে D বিন্ধু ত্রিভুজ ABC এর অভ্যন্তরে অবস্থিত।     আইডিয়া-২ঃ   A,B,C,D  বিন্ধুদ্বয়ের জন্য  Convex Hull  তৈরী করলে  Convex Hull  এর প্রান্ত বিন্ধু যদি ৩ টি হয় তবে  D  বিন্ধু ত্রিভুজের অভ্যন্তরে অবস্থিত।  যদি প্রান্তবিন্দু ৪ টি হয় তবে তা ত্রিভুজের বাইরে অবস্থিত। আইডিয়া-৩ঃ   D  বিন্ধু যদি  AB,BC,CA  বাহুত্রয়ের বামে অবস্থিত হয় তার মানে এটি ত্রিভুজের অভ্যন্তরে অবস্থিত।

          তিনটি বিন্দুর স্থানাঙ্ক A(x1,y2) , B(x2,y2) , C(x3,y3). C বিন্দুটি AB রেখার বামে, ডানে নাকি      AB বরাবর অবস্থিত?   আইডিয়াঃ  ABC ত্রিভুজের  ক্ষেত্রফল যদি ধনাত্মক হয়(মডুলাস ব্যাবহার না করে) তবে C বিন্ধু AB রেখার বামে অবস্থিত। ক্ষেত্রফল ঋণাত্মক হলে C বিন্ধু AB রেখার ডানে অবস্থিত। আর ক্ষেত্রফল ০ হলে বিন্দুত্রয় একই রেখায় অবস্থিত।

উপরের চিত্রের মতো বিদঘুটে কোন বহুভুজের ক্ষেত্রফল বের করতে ব্যাবহৃত হয় পিক'স থিওরি! যদি বহুভুজটির ভার্টেক্স বা কৌণিক বিন্ধুসমূহ গ্রাফ পেপারের ইন্টিজার পয়েন্টগুলো হয় তবে বহুভুজটির ক্ষেত্রফল হবেঃ Area = i + (b/2) - 1 = (2*i + b - 2)/2 এখানে,      i - Number of points inside the polygon                     b - Number of points on the boundary of the polygon এখন, পিক'স থিওরি টা আসলে যেভাবে আসছেঃ ১) আমি যদি গ্রাফ পেপারে লম্বভাবে অবস্থিত অথবা অনুভুমিকভাবে অবস্থিত ২ টি বিন্দুর মধ্যবর্তী দূরত্ব এক একক ধরি তবে গ্রাফ পেপারে অংকিত ক্ষুদ্রতম ত্রিভূজের ক্ষেত্রফল হবে ১/২।  (এখানে, ক্ষুদ্রতম ত্রিভুজ বলতে বুঝানো হয়েছে এমন একটা ত্রিভুজ যার কৌণিক বিন্ধুগুলো গ্রাফ পেপারের ইন্টিজার পয়েন্ট হবে কিন্তু ত্রিভুজের অভ্যন্তরে কোন ইন্টিজার পয়েন্ট থাকবে না।অর্থাৎ, যার b=3 , i=0 )। এমন সকল ত্রিভুজের ক্ষেত্রফল ই ১/২ হবে শতভাগ নিশ্চিত। ২) এবার আমি বহুভুজটিকে ক্ষুদ্রতম ত্রিভুজে স্প্লিট করবো। ৩) তাহলে, বহুভুজটির ক্ষেত্রফল বের করতে পারবো যদি ...

প্রথমেই জানা দরকার   Planar Graph  কী? Planar Graph হচ্ছে, দ্বিমাত্রিক তলে আঁকা এমন একটা গ্রাফ যেখানে একটা এজ কখনোই অন্য একটা এজকে ছেদ করবে না। একটি গ্রাফের Euler Characteristics বা Euler Number = Vertices - Edges + Faces এখানে, Faces = গ্রাফটির মোট সাইকেল + ১  এখানে, একটা সাইকেল কে তখনই হিসেবে আনবো যখন তার ভিতর অন্য কোন সাইকেল থাকবে না। মজার ব্যাপার হচ্ছে, Planar Graph এর জন্য সবসময় ই Euler Number = 2 ছবিতে, ১ম গ্রাফটি Planar Graph নয়! কারণ, একটা এজ অন্য এজ কে ছেদ করেছে। ২য় গ্রাফের জন্য, Euler Number = 4 - 6 + 4 = 2 ৩য় গ্রাফের জন্য, Euler Number = 4 - 6 +4 = 2 এভাবে, সকল Planar Graph এর জন্যই Euler Number = 2 যা অনেক থিওরিতে এপ্লাই করা লাগে। আশা করি, পরবর্তীতে কোন থিওরি তে এপ্লাই করে দেখাবো Planar Graph এর এই প্রোপার্টি। Happy Coding -_-

সমস্যাঃ  তোমাকে একটি দ্বিমাত্রিক তলের উপর অবস্থিত ২ টি বিন্দু দেয়া আছে। গ্রাফ পেপারে বিন্দু দুটি চিহ্নিত করে তাদের সংযোগ সরলরেখা আকলে ঐ সরলেখার উপর গ্রাফ পেপারের কয়টি বিন্দু পড়েছে সেটা বের করতে হবে। সমাধানঃ মনে করি, বিন্দুদ্বয় P(x1,y1) এবং Q(x2,y2) ।  ১) PQ সরলরেখা যদি X-অক্ষের সমান্তরাল হয় তবে ans = abs(x1 - x2) - 1 ২) PQ সরলরেখা যদি Y-অক্ষের সমান্তরাল হয় তবে ans = abs(y1 - y2) - 1 ৩) অন্যথায়, ans = GCD ( abs(y1-y2) , abs(x1-x2) )-1

যদি a^b = x হয়, তবে a^x = b  এবং b^x = a হবে।  খাতায় কয়েকটি সংখ্যা নিয়ে হিসেব করে দেখতে পারো। এবার বিষয়টি বুঝতে পারলে ঝটপট এই  প্রব্লেম  টি সলভ করে ফেলো। 

একটি 2D গ্রিডে এক পজিশন থেকে অন্য পজিশনের ক্ষুদ্রতম দূরত্ব বের করতে হবে যখন বর্তমান পজিশন থেকে সম্ভাব্য সকল দিকে(৮ দিকে) মুভ দেয়া যায়। এমন প্রব্লেম দেখলে অনেকেই এক দেখাতে সল্যুশন বলে দিবে যে একটা 2D BFS চালিয়ে বের করে নিলাম সিম্পল। কিন্তু এই প্রব্লেম টি যখন অন্য কোন প্রব্লেম এর সাবটাস্ক হিসেবে আসবে তখন MLE অথবা TLE খাওয়ার সম্ভাবনা প্রবল। এক্ষেত্রে এই প্রব্লেম টি O(1) কমপ্লেক্সিটি তে সলভ করা সম্ভব। আর সেটি হলো P1 (x1,y1)  থেকে p2(x2,y2) বিন্ধুর ক্ষুদ্রতম দূরত্ব হচ্ছে distance = max( abs(x1-x2) , abs(y1-y2) )