tag:blogger.com,1999:blog-8113711071749533092018-02-15T04:45:09.026+06:00forthright48Learning Never EndsMohammad Samiul Islamnoreply@blogger.comBlogger39125tag:blogger.com,1999:blog-811371107174953309.post-85995071508934233472018-02-08T15:55:00.000+06:002018-02-08T16:15:46.544+06:00Application of Prufer Code: Random Tree Generation, Cayley's Formula and Building Tree from Degree CountOn the last post (Prufer Code: Linear Representation of a Labeled Tree), we discussed how to convert a labeled tree into Prufer Code and vice versa. On this post, we will look into some of its applications in problem-solving.
Generating Random Tree
This one is the simplest. Though problem-solving may not require generating random trees, problem setting might. In order to generate a random tree Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com0tag:blogger.com,1999:blog-811371107174953309.post-67192475170705318382018-01-29T01:02:00.000+06:002018-02-08T16:03:33.264+06:00Prufer Code: Linear Representation of a Labeled TreeI guess this is going to be my first post (apart from the contest analysis') which is not about Number Theory! It's not about graph either, even though the title has "Tree" in it. This post is actually about Combinatorics.
Prufer code, in my opinion, is one of the most underrated algorithms I have learned. It has a wide range of applications, yet, very few people seem to know about it. It's not Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com0tag:blogger.com,1999:blog-811371107174953309.post-385747528968513362017-11-18T23:39:00.000+06:002018-01-29T01:42:26.800+06:00Chinese Remainder Theorem Part 2 - Non Coprime ModuliAs promised on the last post, today we are going to discuss the "Strong Form" of Chinese Remainder Theorem, i.e, what do we do when the moduli in the congruence equations are not pairwise coprime. The solution is quite similar to the one we have already discussed in the previous post, so hopefully, it will be a lot easier to understand.
Prerequisite
If you haven't read my previous post, you Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com0tag:blogger.com,1999:blog-811371107174953309.post-8231456693713191372017-11-15T19:17:00.000+06:002018-01-29T01:43:24.240+06:00Chinese Remainder Theorem Part 1 - Coprime ModuliSecond part of the series can be found on: Chinese Remainder Theorem Part 2 - Non Coprime Moduli
Wow. It has been two years since I published my last post. Time sure flies by quickly. I have been thinking about resuming writing again for a while now. Took me long enough to get back into the mood.
I am really excited about today's post. I have been meaning to write on Chinese Remainder Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com2tag:blogger.com,1999:blog-811371107174953309.post-91332151576128007172015-09-29T22:20:00.000+06:002018-01-29T01:45:02.632+06:00Modular Inverse from 1 to NWe already learned how to find Modular Inverse for a particular number in a previous post, "Modular Multiplicative Inverse". Today we will look into finding Modular Inverse in a bulk.
ProblemGiven $N$ and $M$ ( $N < M$ and $M$ is prime ), find modular inverse of all numbers between $1$ to $N$ with respect to $M$.
Since $M$ is prime and $N$ is less than $M$, we can be sure that Modular Inverse Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com5tag:blogger.com,1999:blog-811371107174953309.post-46876640281923208592015-09-26T14:57:00.000+06:002015-09-26T15:00:23.154+06:00Euler Phi Extension and Divisor Sum TheoremPreviously we learned about Euler Phi Function. Today we are going to look at two theorems related to Euler Phi that frequently appears in CPPS. I am not sure whether these theorems have any official names, so I just made them up. These allow easy references so I will be using these names from now on.
Euler Phi Extension Theorem
Theorem: Given a number $N$, let $d$ be a divisor of $N$. Then Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com1tag:blogger.com,1999:blog-811371107174953309.post-53243161863351745722015-09-23T17:39:00.000+06:002015-09-26T10:48:06.233+06:00Modular Multiplicative Inverse
Problem
Given value of $A$ and $M$, find the value of $X$ such that $AX \equiv 1\:\text{(mod M)}$.
For example, if $A = 2$ and $M = 3$, then $X = 2$, since $2\times2 = 4 \equiv 1\:\text{(mod 3)}$.
We can rewrite the above equation to this:
$AX \equiv 1\:\text{(mod M)}$
$X \equiv \frac{1}{A}\:\text{(mod M)}$
$X \equiv A^{-1}\:\text{(mod M)}$
Hence, the value $X$ is known as Modular Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com0tag:blogger.com,1999:blog-811371107174953309.post-42252168373449683112015-09-21T15:10:00.001+06:002015-09-26T10:48:13.633+06:00Repeated Squaring Method for Modular Exponentiation Previously on Modular Exponentiation we learned about Divide and Conquer approach to finding the value of $B^P \:\%\: M $. In that article, which is recursive. I also mentioned about an iterative algorithm that finds the same value in same complexity, only faster due to the absence of recursion overhead. We will be looking into that faster algorithm on this post today.
Make sure you know about Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com0tag:blogger.com,1999:blog-811371107174953309.post-27296711957405064362015-09-17T12:59:00.000+06:002015-09-17T13:01:38.310+06:00Euler's Theorem and Fermat's Little TheoremWe will be looking into two theorems at the same time today, Fermat's Little Theorem and Euler's Theorem. Euler's Theorem is just a generalized version of Fermat's Little Theorem, so they are quite similar to each other. We will focus on Euler's Theorem and its proof. Later we will use Euler's Theorem to prove Fermat's Little Theorem.
Euler's TheoremTheorem - Euler's Theorem states that, if $a$ Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com0tag:blogger.com,1999:blog-811371107174953309.post-78255523635451854662015-09-07T14:56:00.000+06:002015-09-07T15:00:57.614+06:00Segmented Sieve of Eratosthenes
Problem
Given two integers $A$ and $B$, find number of primes inside the range of $A$ and $B$ inclusive. Here, $1 \leq A \leq B \leq 10^{12}$ and $B - A \leq 10^5$.
For example, $A = 11$ and $B = 19$, then answer is $4$ since there are $4$ primes within that range ($11$,$13$,$17$,$19$).
If limits of $A$ and $B$ were small enough ( $ \leq 10^8$ ), then we could solve this problem using theMohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com1tag:blogger.com,1999:blog-811371107174953309.post-68915884867225433132015-09-04T17:38:00.000+06:002017-11-25T10:25:35.541+06:00Euler Totient or Phi FunctionI have been meaning to write a post on Euler Phi for a while now, but I have been struggling with its proof. I heard it required Chinese Remainder Theorem, so I have been pushing this until I covered CRT. But recently, I found that CRT is not required and it can be proved much more easily. In fact, the proof is so simple and elegant that after reading it I went ahead and played MineCraft for 5 Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com6tag:blogger.com,1999:blog-811371107174953309.post-73915137558748769762015-08-31T21:11:00.000+06:002015-09-02T14:58:53.233+06:00Bit ManipulationOn this post, we will look into how to use "Bitwise Operators" to manipulate bits of a number. Bit manipulation is a useful tool that can sometimes perform complicated tasks in a simple manner.
We will work on integer values and assume each number has $32$ bits in them. If a number has only $0$ or $1$ as its digit, then assume that it is in binary form. All position of bits is $0$ indexed.
Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com0tag:blogger.com,1999:blog-811371107174953309.post-54947300137314188832015-08-27T17:07:00.000+06:002015-08-27T17:08:48.879+06:00Bitwise OperatorsWe know about arithmetic operators. The operators $+,-,/$ and $\times$ adds, subtracts, divides and multiplies respectively. We also have another operator $\%$ which finds the modulus.
Today, we going to look at $6$ more operators called "Bitwise Operators". Why are they called "Bitwise Operators"? That's because they work using the binary numerals (bits, which are the individual digits of the Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com2tag:blogger.com,1999:blog-811371107174953309.post-19454745132883150242015-08-27T12:46:00.000+06:002015-08-27T12:50:27.033+06:00SPOJ LCMSUM - LCM Sum
Problem
Problem Link - SPOJ LCMSUM
Given $n$, calculate the sum $LCM(1,n) + LCM(2,n) + ... + LCM(n,n)$, where $LCM(i,n)$ denotes the Least Common Multiple of the integers $i$ and $n$.
Solution
I recently solved this problem and found the solution really interesting. You can find the formula that solves this problem on OEIS. I will show you the derivation here.
In order to solve this Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com8tag:blogger.com,1999:blog-811371107174953309.post-49413725002649047392015-08-25T22:51:00.000+06:002015-08-25T22:51:59.047+06:00Contest Analysis: BUET Inter-University Programming Contest - 2011, UVa 12424 - 12432Last week (2015-08-21) we practiced with this set. Some of the problems didn't have proper constraints, which caused some headaches. This contest originally followed Google Code Jam format with two subproblems ( small and large ) for each problem. Each of the sub-problems had a different constraint on them. But when they uploaded it online, they removed both constraints from some problems, makingMohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com2tag:blogger.com,1999:blog-811371107174953309.post-55938132127499877582015-08-20T22:44:00.000+06:002015-08-22T17:47:05.996+06:00Contest Analysis: IUT 6th National ICT Fest 2014, UVa 12830 - 12839I participated in this contest last year. Our team "NSU Shinobis" managed to solve 5 and placed in top 10 ( failed to find the rank list ). The IUT 7th ICT National Fest 2015 is going to be held next month, so I thought I would try to up solve the remaining problems. I tried to compile detailed hints for the problems here.
UVa 12830 - A Football Stadium
Complexity: $O(N^3)$
Category: Loop, DP, Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com0tag:blogger.com,1999:blog-811371107174953309.post-10354148456654042132015-08-17T17:56:00.002+06:002015-08-21T23:19:31.925+06:00Modular Exponentiation
Problem
Given three positive integers $B, P$ and $M$, find the value of $B^P \:\%\: M$.
For example, $B=2$, $P=5$ and $M=7$, then $B^P \:\%\: M = 2^5 \: \% \: 7 = 32 \: \% \: 7 = 4$.
This problem is known as [1]Modular Exponentiation. In order to solve this problem, we need to have basic knowledge about [2]Modular Arithmetic.
Brute Force - Linear Solution $O(P)$
As usual, we first Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com0tag:blogger.com,1999:blog-811371107174953309.post-28441969145536145662015-08-15T12:05:00.000+06:002015-09-15T19:28:03.083+06:00Leading Digits of FactorialProblemGiven an integer $N$, find the first $K$ leading digits of $N!$.
For example, for $N=10$ and $K=3$, then first $3$ leading digits of $10! = 3628800$ is $362$.
Finding leading digits uses concepts similar to [1]Number of Trailing Zeroes of Factorial.
Brute Force SolutionFinding the value of $N!$ and then printing the first $K$ digits is a simple but slow solution. Using $long\:long$ we Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com6tag:blogger.com,1999:blog-811371107174953309.post-34400324935571789722015-08-12T10:54:00.000+06:002015-08-12T10:54:29.351+06:00Number of Trailing Zeroes of Factorial
Problem
Given a positive integer $N$, find the number of trailing zero $N!$ has.
For example, $5! = 120$ has $1$ trailing zero and $10! = 3628800$ has $2$.
Brute Force Solution
Brute Force solution for this problem involves calculating the value of $N!$, which is overkill in this situation. Read the section on Brute Force on this article before you continue - [1] Number of Digits of Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com0tag:blogger.com,1999:blog-811371107174953309.post-54087663803705153762015-08-10T20:26:00.000+06:002015-08-10T20:29:22.435+06:00Prime Factorization of Factorial
Problem
Given a positive integer $N$, find the prime factorization of $N!$.
For example, $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 = 2^3 \times 3 \times 5$.
Brute Force Solution
A possible solution is to calculate the value of $x = N!$ and then prime factorize $x$. But calculating $N!$ is tedious. We cannot fit $N!$ where $N > 20$ in a long long variable. We will need to use Big Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com0tag:blogger.com,1999:blog-811371107174953309.post-24756726709752040872015-08-08T15:21:00.001+06:002015-08-10T10:54:20.502+06:00Number of Digits of Factorial
Problem
Given an integer $N$, find number of digits in $N!$.
For example, for $N=3$, number of digits in $N! = 3! = 3\times 2\times 1 = 6$ is $1$. For $N=5$, number of digits in $5! = 120$ is $3$.
Brute Force Solution
The first solution that pops into mind is to calculate $N!$ and count how many digits it has. A possible solution will look like the following:
int factorialDigit ( int n )Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com11tag:blogger.com,1999:blog-811371107174953309.post-62886576510559160932015-08-04T22:05:00.000+06:002015-08-04T22:05:10.040+06:00UVa 10407 - Simple division
Problem
Problem Link - UVa 10407 - Simple division
Given an array of numbers, find the largest number $d$ such that, when elements of the array are divided by $d$, they leave the same remainder
Solution
We will be using our knowledge about Congruence Relation and GCD to solve this problem. But first, we need to make sure that we understand the problem properly.
Wrong Approach
At Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com2tag:blogger.com,1999:blog-811371107174953309.post-59863520795823186642015-08-03T16:00:00.000+06:002015-08-03T16:00:08.177+06:00UVa 11388 - GCD LCM
Problem
Problem Link - UVa 11388 - GCD LCM
Given two positive integers $(G, L)$, we have to find a pair of integers $(a,b)$ such that $gcd(a, b)=G$ and $\text{lcm}(a, b)=L$. If there are multiple such pairs, we have to find the pair where $a$ is minimum. Also, both $a$ and $b$ needs to be positive.
Solution
We don't know the value of $(a,b)$ yet. Here is how I approached the problem.
Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com1tag:blogger.com,1999:blog-811371107174953309.post-36924119279693953912015-08-01T21:22:00.000+06:002015-08-01T21:32:19.311+06:00Introduction to Number SystemsNumber System is a consistent way of expressing a number. It consists of three parts:
The Symbol - It can be digits, letters or any other symbol.
The Position - The position of symbols determine their weight.
The Base - The total number of different symbols supported.
Number system is often named after the size of its base. For example, the "Decimal Number System", with symbols $(Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com0tag:blogger.com,1999:blog-811371107174953309.post-84307557011549372932015-07-29T18:22:00.000+06:002015-07-29T18:22:00.890+06:00Simple Hyperbolic Diophantine Equation
Problem
Given the integers $A, B, C, D$, find a pair of $(x,y)$ such that it satisfies the equation $Axy + Bx + Cy = D$.
For example, $2xy + 5x + 56y = -7$ has a solution $(x,y) = (-27,64)$.
Hyperbolic equations are usually of form $Ax^2 + By^2 + Cxy + Dx + Ey = F$. Here we don't have coefficients of $x^2$ and $y^2$. That's why we are calling it "Simple".
So how do we tackle the problem?Mohammad Samiul Islamhttps://plus.google.com/105318322076018763007noreply@blogger.com0