Mohibur Rahman's Blog

     Basic Things of a Binary Tree 1.   Check if a Binary Tree is a subtree of another Binary Tree (একটি বাইনারি ট্রি অন্য একটি বাইনারি ট্রি এর সাবট্রি কিনা চেক করা ) Suppose we have a main Binary Tree M   and another Binary Tree S .  We have to check if S is a subtree of M or not. Solution:  Tree S is a subtree of M if both inorder and preorder traversals of S are substrings of inorder and preorder traversals of M  respectively ( ট্রি S, ট্রি M এর সাবট্রি হবে যদি S এর ইনঅর্ডার এবং প্রিঅর্ডার ট্রাভার্সেল  M এর ইনর্ডার এবং প্রিওর্ডার ট্রাভার্সেল এর সাবস্ট্রিং হয় ). The above algorithm doesn't work for cases where a tree is present in another tree, but not as a subtree. Handle this case by adding a special character whenever we encounter NULL in inorder and preorder traversals.

Codeforces 1368B সলিউশন ঃ সবগুলা লেটার একবার করে নিলে একটা সাব সিকুয়েন্স পাওয়া যাবে।মোট ১০ টি লেটার আছে তাদের প্রত্যেককে পজিশন দিয়ে ডিফাইন করলে নিচের ছক এর মত হয়।  Letter C  O  D  E  F  O  R  C E S  Positon  1   2  3 4  5  6  7  8   9  10  Count 1  1  1  1  1  1  1  1  1  1  এখানে সাবসিকুয়েন্স বের করার সূত্র হলো প্রত্যেক পজিশন এর count এর গুনফল। এখন কোন একটা পজিশন এ একটা লেটার যোগ করলে সাবসিকুয়েন্স হয়ে যাবে (২*১*১*১*১*১*১*১*১*১ ) = ২। যা দেখতে এমন হবে ccodeforces । টেবিলটা হবে নিচের মত।  Letter C  O  D  E  F  O  R  C E S  Positon  1   2  3 4  5  6  7  8   9  10  Count 2  1  1  1  1  1  1  1  1  1  এমন ভাবে প্রত্যেক পজিশন এর কাউন্ট ১ করে বাড়াবো আর চেক দিবো টোটাল সাবসিকুএন্স K থ...

Today we will discuss a common problem. The problem is, you are given a string S, you have to find the longest palindromic substring in S. For example, S = abcbsd, here our desired answer is bcb with length 3. Solution: This problem can be solved in many ways. One of them is DP solution and another is Expand Around Center. DP: DP solution is a very straight cut solution. We go through all the substrings of the main string S and check each substring is palindrome or not and find the longest substring if it is palindrome. Here we do DP in the palindrome checking part. Here is the Code. Complexity O(n^2) . #include<bits/stdc++.h> using namespace std ;   string s ; int dp [ 1005 ] [ 1005 ] ; ///dp[l][r] means is substring s[l...r] is a palindrome or not   int isPalindrome ( int left, int right ) { if ( left >= right ) return 1 ; if ( dp [ left ] [ right ] ! = - 1 ) return dp [ left ] [ right ] ; int result = 0 ; if ( s ...

Pick's theorem says that if a polygon has I vertices/points inside it and B vertices or points on the border of it, then the AREA of this polygon is : AREA = I + ( B / 2 ) -1 There some conditions for applying this theorem. The shape must be a polygon. It can be concave or convex, but not self-intersecting. No circles apply here. Each vertex of the polygon must fall on the board. The polygon must be complete. No holes. Although, if it does have a hole, we can still compute the area by subtracting the smaller area from the larger area if the interior hole is also a lattice polygon. Pick's formula assumes unit measures and unit squares for the area. You can make your unit whatever you desire though if sides of your shape aren't whole numbers. However, you must adjust the value of your unit squares accordingly. So, if you made your lattice units 0.5, your interior squares would each be 0.5*0.5=0.25 square units each. A problem related to Picks Theorem is   LightOJ ...

Geometry #  Given two points p (x1, y1) and q (x2, y2), calculate the number of integral points lying on the line joining them. Solution 1. If the edge formed by joining  p  and  q  is parallel to the X-axis, then the number of integral points between the vertices is : abs( y2 - y1 ) - 1 2. Similarly if edge is parallel to the Y-axis, then the number of integral points in between is : abs( x2 - x1 ) - 1 3. Else, we can find the integral points between the vertices using below formula: GCD(abs( x2 - x1 ) , abs( y2 - y1 )) - 1

Number of Divisors(NOD) Given N you have to find the number of divisors of N. Solution: Step 1: Generating Prime using Sieve of Eratosthenes Step 2: Count Divisors using prime factorization CODE: long long NOD_using_factorization ( long long n ) /// O(lof2(N)) { long long sqrtn = sqrt ( n ) ; long long tmp = 1 ,divisors = 1 ; for ( int i = 0 ; i < prime. size ( ) && prime [ i ] <= sqrtn ; i ++ ) { ///if ( sieve[n] == 0 ) break; ///*Checks if n is prime or not*/ Please comment This line if n > 1e7 if ( n % prime [ i ] == 0 ) { tmp = 1 ; while ( n % prime [ i ] == 0 ) { n / = prime [ i ] ; tmp ++ ; } divisors * = tmp ; sqrtn = sqrt ( n ) ; ...

1#    Using Logarithms to Find Number of Digits in Large Numbers 2#   A number N can be represented by the difference of the square of two numbers that means  it is possible to find two integers p and q  such that   N = p^2 - q^2 If N is Odd or N is divisible by 4.         If we named this type of number is a good number then       2.1# If two number A and B both are good number then the product of them are also must be a good number 3# If a array / sequence have N element then total number of subarray / contigious_subsequence is n(n+1)/2 <<<<<<<<<<<<<<<<<<<<<<<<<<<<**************>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>