ALGO NOTEBOOK

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

A good problem to practice. https://www.hackerrank.com/challenges/xor-se/problem Some important info and cheat sheets to remember.

#include<bits/stdc++.h> ///...................................*****................................................./// /// Author : Raihan Khan Raka ( raihankhanraka@gmail.com ) /// /// Department of Computer Science /// /// & Engineering /// /// Comilla University , Bangladesh. /// ///...................................*****................................................./// /*....................................Values................................................*/ #define p5 100007 #define p6 1000007 #define PI acos(-1) #define M 1000000007 #define inf 1LL << 62 #define white 0 #define gr...

Euler's Totient Function Euler's Totient function returns the number of positive integers less than or equal to n which are co-prime with n. Two numbers are co-prime when they have no common divisors or their gcd is 1. For instance,  phi(8)=4  , since there's four integers 1,3,5,7 that are co-prime with 8. Prime numbers are co-prime with any number below it. if P is a prime number then  phi(P)=P-1  . For instance  phi(7)=6  , since 1,2,3,4,5,6 all are co-prime with 7. Phi function is also multiplicative. That means if n=a*b , then, Phi(n) = Phi(a * b) = Phi(a) * Phi(b) if a and b are not relatively co-prime then Phi(n) = Phi(a * b) = Phi(a) * Phi(b) * d/phi(d) , where d=gcd(a,b) P1 and P2 are prime numbers and n can be represented in the form of n=P1*P2, then Phi(n) = Phi(P1 * P2) = Phi(P1) * Phi(P2) = (P1-1) * (P2-1)  for instance , 21 = 3 * 7 Phi(21)=Phi(3) * Phi(7) =(3-1) * (7-1) ...

The  problem  statement actually refers to finding out number of pairs of integers that have LCM n ( which is the given value). There can be 2000 test cases and value of n can be at most 10 14 . let's assume that the prime factorization of n can be represented as n = p1 q1 .p2 q2 .......px qx , where p1,p2....px are prime numbers and q1,q2...qx are corresponding powers. lets assume that any two integers are i and j such that LCM(i,j)=n. since n is their LCM, the prime factorization of i and j must have the following qualities. 1. if i = px qx then j must be either j = px qx-1 or j = px qx-2 or ..... j = px 0 2. if j = px qx then i must be either i = px qx-1 or i = px qx-2 or ..... i = px 0 3. i = px qx and j = px qx for the 1st scenario we can see there are qx combinations for the 2nd scenario we can see there are qx combinations for the 3rd scenario we can see there are 1 combinations so, there can be a total of 2*qx + 1 combinations for each of the pr...

///https://codeforces.com/problemset/problem/20/C #include<bits/stdc++.h> ///...................................*****................................................./// /// Author : Raihan Khan Raka ( raihankhanraka@gmail.com ) /// /// Department of Computer Science /// /// & Engineering /// /// Comilla University , Bangladesh. /// ///...................................*****................................................./// /*....................................Values................................................*/ #define p5 100007 #define p6 1000007 #define PI acos(-1) #define M 1000000007 #define white 0 #define g...

Introduction: At first we need to know what Machine Learning(ML) is. Generally, people make a mistake by assuming that machine learning refers to learn from machine. Actually it's the opposite. ML means making the machine learn. Computers can make predictions and take decisions on their own with the help of ML. Imagine you are playing a coin toss game with your computer where you are tossing a two sided coin at each turn.  First turn is yours and it could be either head or tail. The next turn is the computer's and computer will not aware of the first turns outcome. After several turns if the coin is in head state then the computer wins and you win otherwise. So, there is 50% probability that you will win or the computer will win. Let's apply ML to this game. The first game will be played like before and there will be again 50% probability that you will win or the computer will win. Then the computer will record all of it's moves and label it's outcome with this ...

Cycle in a 2D graph with DFS Problem Link :  Fox And Two Dots Solution Idea : This problem can be solved using DFS. You can Check my  Solution  . Coloring a graph  Problem Link :  Coloring a Tree Solution Idea : Using DFS we can color a node and its subtree. We are coloring only subtrees. so we can't visit upwards of a tree while coloring. That's why we are using directed graph. if a tree is already colored in it's required color, we don't need to color it anymore. You can Check my  Solution . Also solved  Customized Chess Board  ( brute force approach )

Problem link :  MARBLES In order to solve this problem we need to know basic permutation and combination. We can address this problem with the tag "Selection With Repetition" . If we have n type of object or n objects and we have to choose k objects from these where each object can be choosen multiple times, then number of ways we can do it is  (n+k-1) C (k). Let's come to our problem. we have K type of objects and we have to choose N objects from them. So, now we can convert the given formula into (K+N-1) C (N). Suppose , we have 30 objects to choose and we have 7 types of objects. This formula will give us (36)C(30) = 1947792. Which is much much greater that the required answer. This happens because we have calculated all the possibilities without filtering those possibilities where we haven't taken at least one from each types (which is a key condition) . Let's assume another example - we have two letters A , B and we have to choose 3 letters each ti...

Graph Algorithms: .................................................................................................................................................. Breadth First Search (BFS) Depth First Search (DFS) Shortest Path from source to all vertices **Dijkstra** Shortest Path from every vertex to every other vertex **Floyd Warshall** Minimum Spanning tree **Prim** Minimum Spanning tree **Kruskal** Topological Sort Johnson’s algorithm Articulation Points (or Cut Vertices) in a Graph Bridges in a graph Dynamic Programming: .................................................................................................................................................. Coin Change DP Counting DP 0-1 Knapsack Longest Common Subsequence Longest Increasing Subsequence Minimum Partition Ways to Cover a Distance Longest Path In Matrix Subset Sum Problem Optimal Strategy for a Game Bitmask DP Digit DP Edit Distance Expected value/Probability MCM N-...