## Friday, 27 December 2013

### Important things in Java


int [] A = new int [n];

for (int x : A) System.out.println (x);


int[] array = new int[4];
Arrays.fill(array, 0);

System.out.println(Arrays.deepToString(array));



Math.max (a, b)

Math.abs (a)



StringBuilder:

StringBuilder res = new StringBuilder ();

res.append (char ('A'));

res.append (String);

String ans = res.toString();


int[] array = new int[4];
Arrays.fill(array, 0);

Arrays.Sort (object[], startIndex, endIndex);

Set st = new HashSet  ();
st.size();


List  list = new ArrayList  ();
Concerting Set to List type
List  list = new ArrayList  (st);
Collection.sort (list);

String s = new String();
s.toCharArray();

Input Output Code in Java (Code is taken from Egor's library).

-------------------------------------------------------------------------------------------
If you want to use something other, this is Parser class for input (Written by Rudradevbasak's team proof). For output, you can use PrintWriter class which is fast enough.

## Thursday, 26 December 2013

### Using Latex or Mathjax in Blogger

1. To see how any of the formulas were made in any question or answer, including this one, use the "edit" link to view the complete source. To quickly see the source of a single expression, right-click on it and choose "Show Math As > TeX Commands".

(Note that in some browsers, such as Firefox, the MathJax right-click menu that contains this command will be obscured by the browser's own right-click menu. Click somewhere outside the main browser canvas -- such as in the address bar -- to dismiss the browser menu and reveal the MathJax one behind it).

2. For inline formulas, enclose the formula in $...$.  For displayed formulas, use $$...$$.  These render differently: $\sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{2}$ (inline) or $$\sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{2}\tag{displayed}$$

3. For **Greek letters**, use \alpha, \beta, …, \omega: $\alpha, \beta, … \omega$.  For uppercase, use \Gamma, \Delta, …, \Omega: $\Gamma, \Delta, …, \Omega$.

4. For **superscripts and subscripts**, use ^ and _.  For example, x_i^2: $x_i^2$.

5. By default, superscripts, subscripts, and other operations apply only to the next "group". A "group" is either a single symbol, or any formula surrounded by curly braces {…}.  If you do 10^10, you will get a surprise: $10^10$. But 10^{10} gives what you probably wanted: $10^{10}$. Use curly braces to delimit a formula to which a superscript or subscript applies: x^5^6 is an error;  {x^y}^z is ${x^y}^z$, and x^{y^z} is $x^{y^z}$. Observe the difference between x_i^2 $x_i^2$ and x_{i^2} $x_{i^2}$.

6. **Parentheses** Ordinary symbols ()[] make parentheses and brackets $(2+3)[4+4]$. Use \{ and \} for curly braces $\{\}$.

These do *not* scale with the formula in between, so if you write (\frac12) the parentheses will be too small: $(\frac12)$.    Using \left(…\right) will make the sizes adjust automatically to the formula they enclose: \left(\frac12\right) is $\left(\frac12\right)$.

\left and\right apply to all the following sorts of parentheses: ( and ) $(x)$, [ and ] $[x]$, \{ and \} $\lbrace x \rbrace$, | $|x|$, \langle and \rangle $\langle x \rangle$,  \lceil and \rceil $\lceil x \rceil$, and \lfloor and \rfloor $\lfloor x \rfloor$. There are also invisible parentheses, denoted by .: \left.\frac12\right\rbrace is $\left.\frac12\right\rbrace$.

7. **Sums and integrals** \sum and \int; the subscript is the lower limit and the superscript is the upper limit, so for example \sum_1^n $\sum_1^n$. Don't forget {…} if the limits are more than a single symbol.  For example, \sum_{i=0}^\infty i^2 is $\sum_{i=0}^\infty i^2$. Similarly, \prod $\prod$, \int $\int$, \bigcup $\bigcup$, \bigcap $\bigcap$, \iint $\iint$.

8. **Fractions** There are two ways to make these. \frac ab applies to the next two groups, and produces $\frac ab$; for more complicated numerators and denominators use {…}: \frac{a+1}{b+1} is $\frac{a+1}{b+1}$. If the numerator and denominator are complicated, you may prefer \over, which splits up the group that it is in: {a+1\over b+1} is ${a+1\over b+1}$.

9. **Fonts**

* Use \mathbb or \Bbb for "blackboard bold": $\mathbb{CHNQRZ}$.
* Use \mathbf for boldface: $\mathbf{ABCDEFGHIJKLMNOPQRSTUVWXYZ}$  $\mathbf{abcdefghijklmnopqrstuvwxyz}$.
* Use \mathtt for "typewriter" font: $\mathtt{ABCDEFGHIJKLMNOPQRSTUVWXYZ}$ $\mathtt{abcdefghijklmnopqrstuvwxyz}$.
* Use \mathrm for roman font: $\mathrm{ABCDEFGHIJKLMNOPQRSTUVWXYZ}$  $\mathrm{abcdefghijklmnopqrstuvwxyz}$.
* Use \mathcal for "calligraphic" letters: $\mathcal{ ABCDEFGHIJKLMNOPQRSTUVWXYZ}$
* Use \mathscr for script letters: $\mathscr{ABCDEFGHIJKLMNOPQRSTUVWXYZ}$
* Use \mathfrak for "Fraktur" (old German style) letters: $\mathfrak{ABCDEFGHIJKLMNOPQRSTUVWXYZ} \mathfrak{abcdefghijklmnopqrstuvwxyz}$.

10. **Radical signs** Use sqrt, which adjusts to the size of its argument: \sqrt{x^3} $\sqrt{x^3}$; \sqrt[3]{\frac xy} $\sqrt[3]{\frac xy}$. For complicated expressions, consider using {...}^{1/2} instead.

11. Some special functions such as "lim", "sin", "max", "ln", and so on are normally set in roman font instead of italic font. Use \lim, \sin, etc. to make these: \sin x $\sin x$, not sin x $sin x$. Use subscripts to attach a notation to \lim: \lim_{x\to 0} $$\lim_{x\to 0}$$

12. There are a very large number of special symbols and notations, too many to list here; see [this shorter listing](http://pic.plover.com/MISC/symbols.pdf), or [this exhaustive listing](http://mirror.math.ku.edu/tex-archive/info/symbols/comprehensive/symbols-a4.pdf). Some of the most common include:
* \lt \gt \le \ge \neq $\lt\, \gt\, \le\, \ge\, \neq$.  You can use \not to put a slash through almost anything: \not\lt $\not\lt$ but it often looks bad.
* \times \div \pm \mp $\times\, \div\, \pm\, \mp$. \cdot is a centered dot: $x\cdot y$
* \cup \cap \setminus \subset \subseteq \subsetneq \supset \in \notin \emptyset \varnothing $\cup\, \cap\, \setminus\, \subset\, \subseteq \,\subsetneq \,\supset\, \in\, \notin\, \emptyset\, \varnothing$
* {n+1 \choose 2k} or \binom{n+1}{2k} ${n+1 \choose 2k}$
* \to \rightarrow \leftarrow \Rightarrow \Leftarrow \mapsto $\to\, \rightarrow\, \leftarrow\, \Rightarrow\, \Leftarrow\, \mapsto$
* \land \lor \lnot \forall \exists \top \bot \vdash \vDash $\land\, \lor\, \lnot\, \forall\, \exists\, \top\, \bot\, \vdash\, \vDash$
* \star \ast \oplus \circ \bullet $\star\, \ast\, \oplus\, \circ\, \bullet$
* \approx \sim \cong \equiv \prec $\approx\, \sim \, \cong\, \equiv\, \prec$.
* \infty \aleph_0 $\infty\, \aleph_0$ \nabla \partial $\nabla\, \partial$ \Im \Re $\Im\, \Re$
* For modular equivalence, use \pmod like this: a\equiv b\pmod n $a\equiv b\pmod n$.
* \ldots is the dots in $a_1, a_2, \ldots ,a_n$ \cdots is the dots in  $a_1+a_2+\cdots+a_n$
* Some Greek letters have variant forms:
\epsilon \varepsilon $\epsilon\, \varepsilon$, \phi \varphi $\phi\, \varphi$, and others. Script lowercase l is \ell $\ell$.

[Detexify](http://detexify.kirelabs.org/classify.html) lets you draw a symbol on a web page and then lists the $\TeX$ symbols that seem to resemble it.  These are not guaranteed to work in MathJax but are a good place to start.

13. **Spaces** MathJax usually decides for itself how to space formulas, using a complex set of rules. Putting extra literal spaces into formulas  will not change the amount of space MathJax puts in: a␣b and a␣␣␣␣b are  both $a b$. To add more space, use \, for a thin space $a\,b$; \; for a wider space $a\;b$.  \quad and \qquad are large spaces: $a\quad b$, $a\qquad b$.

To set plain text, use \text{…}: $\{x\in s\mid x\text{ is extra large}\}$. You can nest $…$ inside of \text{…}.

14. **Accents and diacritical marks** Use \hat for a single symbol $\hat x$, \widehat for a larger formula $\widehat{xy}$. If you make it too wide, it will look silly. Similarly, there are \bar $\bar x$ and \overline $\overline{xyz}$, and \vec $\vec x$ and \overrightarrow $\overrightarrow{xy}$. For dots, as in $\frac d{dx}x\dot x = \dot x^2 + x\ddot x$,  use \dot and \ddot.

15. Special characters used for MathJax interpreting can be escaped using the \ character: \$$\, \{ $\{$, \_ $\_$, etc.

(Tutorial ends here.)

-------------

It is important that this note be reasonably short and not suffer from too much bloat. To include more topics, please create short addenda and post them as answers instead of inserting them into this post.

### Standard Vieta Jumping and examples

$\sum_{k=1}^n k = \frac{n(n+1)}{2}$

Consider the following equation.
$x^2$ = $y^2 + z^2$.

Consider the first few numbers $x_0$, $x_1$ ,,, $x_n$.

## Tuesday, 10 December 2013

### 2 SAT

Definition:
(x1 v x2) ^ (x1 v -x2) ^ ....
per clause two literals.

Algorithm to found whether there exits a possible assignment or not?
Build implication graph corresponding and then check whether there exists a path from x to -x or not.
If such path exists, then no valid assignment can be done.

Building implication graph
(x v y) add edge -x to y, and -y to x.

Algorithm to find a possible assignment?

First check for the existence case.
for each unassigned literal x, assign it to true and all the y such x -> y, then assign y to true,
Assign all the opposite of these literals to be false.

Implementation:

Problems to practice:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=43&page=show_problem&problem=2453
http://www.spoj.com/problems/TORNJEVI/
http://www.spoj.com/problems/SUPSUP/
http://2011.nwerc.eu/results.php (Piece it Together ).
http://2012.nwerc.eu/en/results/problems/

References:
http://users.cms.caltech.edu/~umans/cs21/lec17.pdf
http://kartikkukreja.wordpress.com/2013/05/16/solving-2-sat-in-linear-time/
http://classes.soe.ucsc.edu/cmps132/Winter05/hw/hw8sols.pdf

## Saturday, 7 December 2013

### Finding nCk effectively

if n is or range 10^9 or so. and k is of the range <= 20, 50, 100 or so.

Finding nCk % mod:
n * (n - 1) * (n - 2) * (n - k + 1) / (k !).
Do the factorisation of k! easily.
Make an array A such that A[i] = n - i, i >= 0 && i < k.
now for each prime p, let us say it has power q in k!,
Remove q powers of p from A[0] to A[k - 1].

Finally multiply all the A[i]'s and then do mod to get the answer.

Another method.
n C k = ((n - 1) C (k - 1) + (n - 1) C k) % mod; when n is odd.
n C k = sum over i = 0 to k. ((n / 2) C i) * ((n / 2) C (k - i)). when n is even.
This method is also included in the code, but it is not so fast :(

## Wednesday, 4 December 2013

### Important vim commands

• :! for running a command outside the vim.                   eg. :!pwd
• set smartindent
• Ctrl x + Ctrl l                    for autocompletion of entire line
• Replacing in a line: s/foo/bar/g will replace each occurence of foo by bar.
• Replacing in a line: s/foo/bar/gc will replace each occurence of foo by bar, but ask for confirmation.
• Replacing in a file: %s/foo/bar/gc will replace each occurence of foo by bar, but ask for confirmation.
• But if use s/foo/bar it then it will replace the first occurance of foo by bar in the line.
• Use arrow keys to get the previous command.
• Use :ab mail praveendhinwa@gmail.com etc kind of abbreviations.
• >> and << for indentation
• sh: temporary returns to unix.
• e filename: opens the file with given filename.
• browse e: graphical file opening.
• use tab for completion of half command too
• :g/string/d delete all lines containing string
• :v/string/d delete all lines not containing string.
• 2,15s/foo/bar/g delete all occurences of foo by bar from line 2 to 15.
• * for searching the word under the cursor currently.
• /word Searching from top
• ?word Searching from bottom to top.
• /f[ao]r will search for far and for both.
• yy for copying a single line.
• 2yy for copying two lines.
• y for copying the selected text.
• p for pasting the clipboard content.
• shift + [ or ] for moving from the end of functions to start and vice versa.
• gg for moving the cursor to start of line
• G for moving the cursor to the end of line.
• :17 to move the cursor to line numbered 17.
• 0 Move the cursor to beginning of the line
• b for start of the word
• e for moving to end of the word
• cc for changing an entire line.
• Generating text to html code.     :%TOhtml
Mapping in Vim:
• :imap ;so System.out.println() , Whenever you will type ;so, it will autcomplete to System.out.println() with cursor between the paranthesis.

References

## Sunday, 22 September 2013

### Using Templates in C++ Programming

I would describe about using templates in c++.

1. functions using templates

2. classes using templates

3. Template Specialization
Template Specialization means that specialize your template for some particular type. eg. you define add function for integers to be integers addition but for strings it may be addition. So You need to define it seperately.

## Tuesday, 17 September 2013

### My Latest Template for Programming Contests

I have learnt few good things about c++.

• you can directly use this header file, it will precompile all the header files required.

#include <bits/stdc++.h>
using namespace std;

• struct _ { ios_base::Init i; _() { cin.sync_with_stdio(0); cin.tie(0); } } _;

this is meant for reducing slowness of slowness of iostream in syncing. more on
http://codeforces.com/blog/entry/8387
http://codeforces.com/blog/entry/925

Precaution: You need to make sure that you do not use scanf and cin statements interchangibly means
one code should exclusively use cin and cout's only if you are using this. Reason is quite obvious.

I have tested the code on codechef. It works great :). Infact slightly faster :)

Here is the link of my latest template:

## Note: For problem M, The editorial is saying that answer is -1 iff n is of form of p^i, Please read it as n is of form of p^i or 2 * p^i.

I have lost the tex file, So I am really sorry, Next time I will try to write editorials in a doc kind of format.

UPDATE1 : Problems have been added to SPOJ and to our Online judge also. http://www2.cse.iitk.ac.in/judge/public/ . So Enjoy solving them :)
http://www.spoj.com/problems/IITKWPCA/
See the problem from A to J, L to O.

UPDATE2: I have corrected the errors in the editorial and uploaded the latest file. If you want some more explantion.I will edit the article, just write a comment about which problem do you think that editorial can be improved and what you do not understand from the editorial.

PS: I have updated the editorial, You might face some problems in viewing it in google docs itself. Please download the file and view it.

## Wednesday, 14 August 2013

### Weekend Programming Contest this week on 17 August 2013

Hi,
We as a part of ACA, IITK and PClub IITK are organising a small WPC this week. So gear up to enjoy 15 challenging programming tasks. It will start on 6pm 17 August to 6 pm 18 August, 24 hours contest.

This is a team contest of consisting at max 3 persons. It has some prizes for top 6 teams but only for internal teams, so if you are some external participant then I am sorry about it, btw you can get a good practice of all kinds of algorithms.

It will mostly contain problems of all domains and all kinds of difficulty levels. Most of the problems are created by me, Some problems are just a bit modification of standard ideas.

Now time to know people behind the scenes of the WPC. Thank you Pankaj Jindal for inspiring me to write an internal contest. Thanks ACA (specifically Harshvardhan Sharama) for providing the judge, PClub (specially Ankush Sachdeva) for providing the prize money.
Problem Setter for the contest is me, Problem testers are Utkarsh Lath, Bhupendra Kastore. Rizwan Hudda has tested all the problem descriptions and his guidelines about difficulty of the contest.

Many many thanks to all of you. It was really a nice experience to work with you guys :)

Editorial for the contest will be posted here on my blog just after the contest. Problems will also be added on spoj so that you can increase your points on spoj also and do some practice of-course.

See you in the contest :)

## Thursday, 1 August 2013

### Let's Learn Java.

from 20Oct finally I would be learning Java for one week :)

int [] a = new int [10];
Arrays.sort (a);
Arrays.fill (a, 0);
Arrays.fill (a, startRange, endRange, value);
Arrays.sort (a, startIndex, endIndex);
String [] name = String[] {"Praveen", "Dhinwa"};

Queue <Integer> q = new LinkedList <Integer> ();
q.remove();

String s;
s.substr(startIndex, length)

String a[] = s.split(token);

String s;
Integer.parseInt (s);

## Thursday, 23 May 2013

### Sieve Methods : Prime, Divisor, Euler Phi etc.

Structure of the article. First I will explain what does sieve mean. Then I will give you some examples with corresponding java codes and finally some exercises :)

According to  http://www.thefreedictionary.com/sieve , "sieve" means A utensil of wire mesh or closely perforated metal, used for straining, sifting, ricing, or puréeing. Similar to this definition sieve is a method of doing stuff, where you keep rejecting the things that are useless and reducing the space that you are currently looking at.

So much of thing in air, Let us now take an example.

1. Finding primes upto N.
You have to print all primes upto N.

Method1 :  For all the numbers i from 1 to N, check if i is prime or not. If it is a prime, then print it.

Subproblem:

Checking whether a number K is prime.

Solution:

1. For all numbers i from 2 to K-1, check if K is divisible by i (as every number is divisible by 1 and itself). If yes, then not a prime else the number is a prime.

Complexity of this solution : O(K)

2. Note that we do not need to check upto K-1, instead we  can very well check upto sqrt(K).

Proof: Let us say a number K = a * b. Note that atleast one of a and b <= sqrt(K) otherwise product of them would exceed K. So check just upto sqrt(K).

3. Either use some probabilistic method for finding whether a number is prime or not.
More on this later. For now see link

http://en.wikipedia.org/wiki/Primality_test
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting

Method 2:
Now here comes the idea of sieve. So initially assume that all numbers are prime. Then you try to sieve/refine your search range by not looking at the entire numbers but at the reduced space. eg. When you find all the numbers which are divisible by 2, You do not look into those again, as they are already not prime. So those numbers are sieved out. Now try for 3,4, upto n.
In other terms, You first try all the numbers which are divisible are 2 (except 2 itself),
Note that all those wont be primes. So you can remove those out of your consideration now. Now try the same for 3,4,...... N. Finally you will end up with only prime numbers.
For understanding the actual thing going on, see the code.
So the code basically sets all the numbers upto N to be prime. Then for every number that is still prime, we set all of its multiples upto N to be non-prime.

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
static boolean[] isPrime;

public static void sieveOptimized(int N) {
isPrime = new boolean[N + 1];

for (int i = 2; i <= N; i++)
isPrime[i] = true;
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
// For further optimization, You can do instead of j += i, j += (2 * i).
// Proof is left to reader :)
for (int j = i * i; j <= N; j += i)
isPrime[j] = false;
}
}
}

public static void sieve(int N) {
isPrime = new boolean[N + 1];

for (int i = 2; i <= N; i++)
isPrime[i] = true;
for (int i = 2; i <= N; i++) {
if (isPrime[i]) {
for (int j = i + i; j <= N; j += i)
isPrime[j] = false;
}
}
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int limit = sc.nextInt();

// call the sieve method
sieveOptimized(limit);

for (int i = 1; i <= limit; i++) {
if (isPrime[i])
System.out.printf("%d ",i);
}
}
}


Now comes the complexity part: Complexity of this code is O(n * logn).
Proof: (This proof comes a lot of times in various algorithms, So pay attention).
For all numbers i going from 2 to n, you need to check all the multiples of i. Note that number of multiples of i upto n are n / i. Hence Expression for the complexity will be written as n / 2 + n / 3 + .. + 1. Take n common out of expression. Now it becomes n * (1 / 2 + ..... + 1/n).
Now as the expression is definitely greater than n. So adding an n to the expression won't have any effect on the complexity, So add n to the expression and now it becomes n * (1 + 1 / 2 + ... + 1/ n).  The expression (1 + 1 / 2 + 1 / 3 + ... 1 / n) is harmonic sum and it's bounded by ln(n). Hence overall complexity is O(n * logn)
Proof of harmonic sum:
A simple Proof: Let us integrate 1 / x from 1 to n. (Note that we are doing integration, which means sum of area under the curve 1/x, which is greater than (1 + 1 / 2 + ... + 1 / n). Value of the integral can be found easily. In fact integration of 1/x dx is ln(x).
2. Finding Sum of divisors of numbers upto N.
Now you have to find sum of divisors of all numbers upto N. Here we are not just considering proper divisors(numbers other 1 and itself), we are considering all the divisors. Here you can do something like this.
Here let us say divisorSum[i] denotes sum of divisors of i. Intially value of divisorSum[i] is equal to zero. Then for all the numbers i from 1 to n, We check all the multiples of i (let us say j) and add i to divisorSum[j].
In other words, Start from 1 and for all the numbers which are multiples of 1, increment their sumDiviors by 1.
Now do the same for 2,3, ... N. Note that for a number i, you are doing this adding operation upto N/i times. So the complexity calculation is same as before.
Look the beautifully commented code.

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();

while (T-- > 0) {
int n = sc.nextInt();
int divisorSum[] = new int [n + 1];

// For every number i, You know that 2*i,3*i,4*i   upto k*i such that k*i<=n, will have i
// as one of it's divisors, so add that to divisorSum[j]

for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i) {
divisorSum[j] += i;
}
}

// Complexity of this code is O(n * logn)
// Proof: Expression for the complexity can be written as n / 1 + n / 2 + ... + n / n
// take n common
// n * (1 + 1 / 2 + ..... + 1/n)
// (1 + 1 / 2 + 1 / 3 + ... 1 / n) is harmonic sum and it's bounded by logn.
// A simple Proof: Let us integrate 1 / x from 1 to n.
// (Note that we are doing integration, which means sum of area under the curve 1/x
// which is greater than (1 + 1 / 2 + ... + 1 / n)
// value of integration can be found easily
// as integration of 1/x dx is ln(x)

for (int i = 1; i <= n; i++)
System.out.printf("%d ", divisorSum[i]);

System.out.printf("\n");
}
}
}


3. Finding No of divisors of numbers upto N.
This is also same as the previous example. Here instead of the storing sum in the array, store the number of divisors and for every multiple of i (say j), In the previous example, you were adding value i to divisorSum[j] , Here just increment the count of noOfDivisior[j] by one.
Code is very easy and hence omitted. Complexity is also same.

4. Sieve for finding euler phi function.
I will denote the euler phi function for a number n by phi(n). phi(n) is defined as follows.
It is count of how many number from 1 to n are coprime(having gcd value 1) to n.
For example phi(6) is 2 as 1,5  are coprime to 6.
Few properties of phi function :
a). phi(p) = p - 1. Where p is prime. All the numbers from 1 to p - 1 are coprime to p.
b). phi(a * b) = phi(a) * phi(b) where a and b are coprime.
c). phi(p^k) = p^k - p^(k - 1). Note that here ^ denotes power. Here all the numbers from 1 to p^k are coprime to p^k except all the multiples of p, which are exactly p^(k -1).

Method for finding:
1. Simple : For all numbers from 1 to n, check if it is coprime to n or not, If yes add that to your answer.
2.  Let us say your number is n, which can be denoted as p1^k1 * p2^k2 ..... *p_m*k_m. Note that here p1, p2.... pm are prime. Basically n is written in it's prime representation.
Then phi(n) would be [ p1^k1 - (p1^(k1-1) ) ] * ....... [p_m^k_m - (p_m^(k_m-1) )] . The expression for n can also be written as p1^k1 * p2^k2 * .... * p_m^k_m * (1 - 1/p1) * (1 - 1/p2) .... * (1 - 1/pm).
which is equal to n * (1 - 1/p1) * (1 - 1/p2) .... * (1 - 1/p_m).
See the code for details.
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {

public static boolean isPrime (int n) {
if (n < 2)
return false;
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}

public static int eulerPhiDirect (int n) {
int result = n;
for (int i = 2; i <= n; i++) {
if (isPrime(i))
result -= result / i;
}

return result;
}

public static int eulerPhi (int n) {
int result = n;
// think that it like this, initially all numbers have gcd with n to be equal to 1.
// Hence value of result is n
// according to formulla  n * (1 - 1/p1) * (1 - 1/p2) .... * (1 - 1/pm). We will be calculating value
// of the product upto i. that is n * (1 - 1/p1) * ... (1 - 1/p_i)
// So let us take example of p1. value of result after one iteration will be n - n / p1, which is precisly
// n * (1 - 1/p1).
// Similarily by induction hypthesis we can say finally the result will be as required.

for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
result -= result / i;

// By using while loop here, we are ensuing that all the numbers i will be prime.
// because for every i, all it's multiples are gets removed.
while (n % i == 0) {
n /= i;
}
}
}

if (n > 1) {
result -= result / n;
}

return result;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();

while (T-- > 0) {
int n = sc.nextInt();

// call the eulerPhiDirect or eulerPhi method.
// culerPhi is more faster as it does not take sqrt(n) for checking for prime

int ans = eulerPhiDirect (n);
System.out.println(ans);
}
}
}


Now Let us calculate value of sieve of all numbers from 1 to N.
Let us say eulerPhi[i] be the value of phi(i). Assign initially all the values of eulerPhi[i] to be i. Then for every prime p, for all multiples of p, we will multiply value of eulerPhi[i] by (1 - 1/p) as per the formula. multiplying eulerPhi[i] by (1 - 1/p) is exactly equal to eulerPhi[i] -= (eulerPhi[i] / p).
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {

public static boolean isPrime (int n) {
if (n < 2)
return false;
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}

private static int[] eulerPhi;

public static void eulerSieve (int N) {
eulerPhi = new int[N + 1];

// set initial value of phi(i) = i
for (int i = 1; i <= N; i++)
eulerPhi[i] = i;

// for every prime i, do as described in blog.
// Note that we are using isPrime(i) function that takes sqrt(n) time. You are advised to write
// a seperate sieve of finding primes as described by me.
// which will reduce the compleixty of this to n * log(n)
// Proof of this is similar to previous ones. Left to reader.

for (int i = 1; i <= N; i++) {
if (isPrime(i))
for (int j = i; j <= N; j += i)
eulerPhi[j] -= eulerPhi[j] / i;
}
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();

eulerSieve(N);

for (int i = 1; i <= N; i++)
System.out.printf("%d ",eulerPhi[i]);
}
}


5. Sieve for finding inverse modulo m.
Inverse of a number a with respect to m is defined as b * a = 1 mod m. Then b is called inverse of a modulo m.
So first of all do you realize that it is not necessary to exist the inverse? Example for a = 4, b = 6.
Let us play around the expressions. a * b = 1 mod m can be written as a * b = 1 + m * k.
which  can be written as a * b - m * k = 1. If the left side has a common factor of both a and m, means gcd(a,m) != 1, then note that right side won't be divisible by that number, Hence no solution of
the equation when a and m has gcd non zero. Hence inverse will exist when a and m have non zero gcd.

Now solving a * b + m * (-k) = 1. write the same as a * b + m * k1 = 1.
So let us try to find solution of a * b + k * m = 1. This k is not equal to previous k, infact it is -k. It is equal to k1.
So let us try to solve generic problem a * x + b * y = 1. where a and b can also be negative and gcd(a, b) = 1.
Let us try a simpler version of the same problem which is solving b * x1 + (a  % b) * y = 1;
Now try to relate these equations.
a % b = a - [ a / b] * b. where [] denotes floor function. This is same as removing all multiples of b from a, which is exactly equal to a % b.
Now the equation turns into b * x1 + (a - [a/b] * b) * y1 = 1
which is a * y1 + b * (x1 - [a/b] * y1) = 1.
So this is recursive version of a * x + b * y = 1, where x is replaced with y1 and y is replaced with x1 - [a/b]  * y1.
Things getting really complex.
(Note that this method is exactly similar to finding gcd of two numbers). Seeing the code will help you to understand more.)
Complexity of this code is same as gcd as it has exactly the same recurrence relation as of that. Time complexity of gcd(m, n) is log (max(m , n)). Hence we can consider time complexity of this method around O(logn).

import java.io.*;
import java.util.*;
import java.math.*;

class pair {
public int x, y;

pair (int x,int y) {
this.x = x;
this.y = y;
}

boolean isEquals (pair p) {
if (this.x == p.x && this.y == p.y)
return true;
else
return false;
}
}

public class Main {
public static int gcd (int a, int b) {
if (b == 0)
return a;
return gcd (b, a % b);
}

public static pair solve (int a,int b) {
if (b == 0) {
// a * x + b * y = 1
// here b = 0
// hence a * x = 1
// if a is not 1, then error else x = 1 and y = 0
// Note that error wont be here, we will always find a which is not 1
// as error case is already handle in solveThis function
return new pair (1, 0);
} else {
// do the recursive call
pair p = solve (b, a % b);
int x1 = p.x;
int y1 = p.y;

int x = y1;
int y = x1 - (a / b) * y1;

return new pair (x, y);
}
}

public static pair solveThis (int a, int b) {
if (gcd (a, b) != 1)
// (-1, -1) corresponds to error, that means no inverse exists in this case
return new pair (-1, -1);
else
return solve (a, b);
}

public static int modpow (long a, long b, long c) {
long res = 1;
while (b > 0) {
if (b % 2 == 1) {
res = (res * a) % c;
}
a = (a * a) % c;
b >>= 1;
}

return (int) res;
}

public static int findInverseModuloPrime (int a, int p) {
return modpow (a, p - 2, p);
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int a = sc.nextInt();
int m = sc.nextInt();

pair p = solveThis (a, m);

if (p.isEquals(new pair(-1, -1)))
System.out.printf("Error, inverse does not exist");
else
System.out.printf("%d %d\n", p.x, p.y);
}
}



Now I will tell you another easier method . Generalized version of Fermat's theorem says that a ^ phi(m) = 1 mod m where gcd(a, m) = 1. Fir finding inverse a ^ (phi(m) - 1) = 1 / a (mod m) = (inverse(a)) mod m.
Hence for finding inverse(a) mod m, You can just find a ^ (phi(m) - 1) by modular exponention method. In case of m being prime, As phi(m) = m - 1. So just find a ^ (m - 2) % m. This is what precisely computed by modpow function in the above function.

Complexity:

Now Sieve for finding inverse modulo m:
You have to find inverse(i) mod m for i ranging from 1 to n.
as complexity of modpow is log (n). and we are doing this for n numbers. Hence total complexity will be O(n * logn). Here I am going to describe a better method using sieve
Just use the identitiy inverse(i) = (-(m/i) * inverse(m % i) ) % m + m;
Proof:  It is good one. I do not want reveal it now. Try yourself. If you come up with it, post it in the comments, I would check whether it is correct or not?

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int n = sc.nextInt(); // denotes the range upto which you want to find the value of modInverse[i]
int m = sc.nextInt();

int modInverse[] = new int[n + 1];

modInverse[1] = 1; // this is you know 1 * 1 mod m = 1

for (int i = 2; i <= n; i++) {
modInverse[i] = (-(m/i) * modInverse[m % i]) % m + m;
}

for (int i = 2; i <= n; i++)
System.out.printf("%d ", modInverse[i]);
}
}


Finally, Here are some few exercises for you to try
I will keep adding the list if I found some problems.

## Tuesday, 21 May 2013

### Solving some dynamic programming problem

Today I am going to explain solution of this problem : http://www.spoj.com/problems/BEHAPPY/
1. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index

Now let us see the problem. It says that no of ways of arraning a_1 + a_2 + ... a_m  = n.
where A[i] <= a_i <= B[i].
Note the ranges : 1<=M<=20, 1<=N<=100, 0<=Ai,Bi,<=100

If you try to check every possible, then it is going to surely going to time out. Finding time complexity of naive approach is left to reader. For solving this problem, you can use maximal matching. But here I would describe only dp algorithm.
1.    Let dp[i][j] denotes the  no of ways of arranging when you have assigned upto i - 1 places and trying to assign i th place.
2.    From state dp[I][j] by matching I and j, you can go to state dp[I + 1][j + 1]. By not matching, you can go to dp[I][j + 1]. Coding this is very easy and complexity is O(n*n).

## Saturday, 18 May 2013

### Using Constructors and Comparators in C++

First I will describe using constructors in C++.

struct point {
int x, y;
point() {} // default constructor
point (int _x, int _y) {
x = _x;
y = _y;
}
};
// Note that in C++, You do not need to use typedef as it is already typedefed
to point, So you do need to use
// typedef for that.

Another way
struct point {
int x, y;
point() {} // default constructor
point (int x, int y): x(x), y(y) {}
};


Now using comparators in C++
struct point {
int x, y;
point() {}
point (int x, int y) : x(x), y(y) {}

bool operator<(const point &rhs) const{
// your main logic for the comparator goes here
return make_pair(y,x) < make_pair(rhs.y, rhs.x);
}

Final Code:
// Comment
struct point {
int x, y;
point() {}
point (int _x, int _y) {
x = _x;
y = _y;
}
bool operator<(const point &rhs) const{
return make_pair(y,x) < make_pair(rhs.y, rhs.x);
}
bool operator==(const point &rhs) const{
return make_pair(y,x) == make_pair(rhs.y, rhs.x);
}
};
Sample uses:
sorting an array in reverse order
Method 1:
vector a;
sort(a.rbegin(), a.rend());

Method 2:
sort(a.begin(), a.end());

For an vector
#include
#include
#include
#include
#include
#include
#include

using namespace std;

bool cmp(int a,int b) {
return a >= b;
}

int main() {
int n;
cin >> n;

vector a;

for (int i = 0; i < n; i++) {
int x;
cin >> x;
a.push_back(x);
}

sort (a.begin(), a.end(), cmp);

for (int i = 0; i < a.size(); i++)
cout << a[i] << " ";

return 0;
}



For an array now.
#include
#include
#include
#include
#include
#include
#include

using namespace std;

bool cmp(int a,int b) {
return a >= b;
}

int a[100];

int main() {
int n;
cin >> n;

for (int i = 0; i < n; i++) {
cin >> a[i];
}

sort (a, a + n, cmp);

for (int i = 0; i < a.size(); i++)
cout << a[i] << " ";

return 0;
}



Deleting redundent points out of n points given. Two points are considered to be equal if both their x and y coordinates are equal.
#include
#include
#include
#include
#include
#include
#include

using namespace std;

struct point {
int x, y;
point() {}
point (int x, int y) : x(x), y(y) {}
bool operator<(const point &rhs) const{
return make_pair(y,x) < make_pair(rhs.y, rhs.x);
}
bool operator==(const point &rhs) const{
return make_pair(y,x) == make_pair(rhs.y, rhs.x);
}
};

int main() {
int n;
cin >> n;

vector a;

for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
a.push_back(point(x, y));
}

set st;

for (int i = 0; i < n; i++) {
st.insert(a[i]);
}

vector res;
set :: iterator it;
for (it = st.begin(); it != st.end(); it++) {
res.push_back(*it);
}

for (int i = 0; i < res.size(); i++)
cout << res[i].x << "  " << res[i].y << endl;

return 0;
}



## Monday, 29 April 2013

### Important things to do in summers 2013

1. Getting good in programming contests. Start practicing at topcoder, codeforces, spoj and codechef.
Also solve some old problems of different - different contests.
2. Read mathematics problem for putnam competition.
3. Operating system and networks revision.
4. Puzzle solving for job perspective.
5. Writing something in English for improvement of thought flowing and generation of ideas.
6. Writing short stories in both Hindi and English, I will also try poems.
7.  http://www.imomath.com/index.php?options=525&lmm=0
8. Revise algorithms
9. Doing some courses in algorithms
10. Reading some interesting book about algorithms and recent research areas in algorithms.