Processing math: 100%

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).

class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long readLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public String readString() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public String next() {
return readString();
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object...objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}
public void printLine(Object...objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
}


-------------------------------------------------------------------------------------------
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.

private static class Parser
{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Parser(InputStream in)
{
din = new DataInputStream(in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public int ni() throws Exception
{
int ret = 0;
byte c = read();
while (c <= ' ') c = read();
boolean neg = c == '-';
if (neg) c = read();
do
{
ret = ret * 10 + c - '0';
c = read();
} while (c > ' ');
if (neg) return -ret;
return ret;
}
public long nl() throws Exception
{
long ret = 0;
byte c = read();
while (c <= ' ') c = read();
boolean neg = c == '-';
if (neg) c = read();
do
{
ret = ret * 10 + c - '0';
c = read();
} while (c > ' ');
if (neg) return -ret;
return ret;
}
public String ns() throws Exception
{
StringBuffer ret=new StringBuffer();
byte c = read();
while (c <= ' ') c = read();
do
{
ret = ret.append((char)c);
c = read();
} while (c > ' ');
return ret.toString();
}
private void fillBuffer() throws Exception
{
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1) buffer[0] = -1;
}
private byte read() throws Exception
{
if (bufferPointer == bytesRead) fillBuffer();
return buffer[bufferPointer++];
}
}
view raw Parser.java hosted with ❤ by GitHub





























Thursday, 26 December 2013

Sliding Window Algorithms and problems related to that..

See the code

#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int a[N];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
deque <pair <int, int> > window;
for (int i = 0; i < n; i++) {
// from the back of deque, if the value of last element is greater or equal than a[i]
// then keep poping the elements.
// Invariant : deque always remains sorted.
// Important property due to which this trick works, is that the popped numbers are useless
// in the next iteration as they are not longer can affect minimum.
while (!window.empty() && window.back().first >= a[i]) {
window.pop_back();
}
window.push_back (make_pair (a[i], i));
// Now from the front of deque, pop all the elements which were out of our window.
while (!window.empty() && window.front().second <= i - k) {
window.pop_front();
}
if (i >= k - 1)
cout << window.front().first << " ";
}
return 0;
}

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.

 

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define SZ(x) ((int)((x).size()))
#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define FILL(a,v) memset(a,v,sizeof(a))
#define FF first
#define SS second
#define DEBUG(a) cerr <<#a<<" : " << a<<endl;
typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int,int> PII;
// Main code starts Now.
LL mod = 2004;
map <pair <LL, LL> , LL> mp;
/*
// This is another cool method.
LL ncr (LL n, LL k) {
if (mp.find (MP (n, k)) != mp.end())
return mp[MP (n, k)];
if (n < 0 || k < 0) return 0;
if (k > n) return 0;
if (n == 0) {
if (k == 0)
return 1;
else
return 0;
}
if (n & 1) {
LL ans = (ncr (n - 1, k) + ncr (n - 1, k - 1));
if (ans >= mod)
ans -= mod;
mp[MP(n, k)] = ans;
return ans;
} else {
LL ans = 0;
REP (j, k + 1) {
LL temp = (ncr (n / 2, j) * ncr (n / 2, k - j));
temp %= mod;
ans += temp;
if (ans >= mod)
ans -= mod;
}
mp[MP (n, k)] = ans;
return ans;
}
}
*/
LL A[15];
vector <pair<int, int> > fact[15];
LL ncr (LL p, LL q) {
if (q > p)
return 0;
if (q == 0)
return 1;
REP (i, q) {
A[i] = p - i;
}
REP (i, SZ(fact[q])) {
int tot = fact[q][i].second;
REP (j, q) {
while (tot && A[j] % fact[q][i].first == 0) {
tot --;
A[j] /= fact[q][i].first;
}
}
assert (tot == 0);
}
LL ans = 1;
REP (i, q) {
ans *= A[i];
ans %= mod;
}
return ans;
}
int isPrime (int n) {
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
int getAns (int n, int k) {
int ans = 0;
while (n) {
ans += (n / k);
n /= k;
}
return ans;
}
int main () {
vector <int> prime;
REP (i, 11) {
FOR (j, 2, 11) {
if (isPrime (j)) {
int tot = getAns (i, j);
// cout << i << " " << j << " " << tot << endl;
if (tot > 0)
fact[i].PB (make_pair (j, tot));
}
}
}
for (int i = 0; i <= 10; i++) {
for (int j = 0; j < fact[i].size(); j++) {
cout << fact[i][j].first << " " << fact[i][j].second << " , ";
}
cout << endl;
}
LL N, M;
while (scanf ("%lld %lld", &N, &M) != EOF) {
cout << ncr (N, M) << endl;
}
return 0;
}
view raw nCk.cpp hosted with ❤ by GitHub

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