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.add (5);
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

Sliding Window Algorithms and problems related to that..

See the code


Amortized complexity is O(n).

Problems to Solve:
References:

  1. http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html
  2. http://softwarelearner.blogspot.in/2011/04/minima-in-sliding-window.html
  3. http://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples/8269948#8269948
  4. http://richardhartersworld.com/cri/2001/slidingmin.html
  5. http://wcipeg.com/wiki/Sliding_window
  6. http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/
  7. http://wcipeg.com/wiki/Sliding_range_minimum_query

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
http://apps.topcoder.com/forums/?module=Thread&threadID=803822&start=0&mc=2

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