Git commands for initial configuration

Posted in Unix by

#!/bin/sh
git config --global user.name "Vasya Pupkin"
git config --global user.email "Vasya.Pupkin@mail.ru"
git config --global core.editor gedit
git config --global color.ui true

Commands for auto completion:
#!/bin/sh
cd ~
curl -OL https://raw.github.com/git/git/master/contrib/completion/git-completion.bash
mv ~/git-completion.bash ~/.git-completion.bash
gedit ~/.bash_profile
#enter:
#if [ -f ~/.git-completion.bash ]; then
# source ~/.git-completion.bash
#fi

How to write binary searches correctly.

Posted in Algorithms by

 

Suppose there is a function f(x),where x is double.

The function has the form of  a step:

Suppose we can find the value of f(xi) for every xi,but we don’t know the value of x0.

How to find xo in O(LogN)? 

double l=0,r=inf
for(int iter=0;iter<100;iter++)
{
 double mid=(l+r)/2;
 if(f(mid)==0) l=mid;else r=mid;
}

The answer is mid

Ok,it’s easy.

Now let’s take a function with an integer domain.

int l=l0;int r=r0; //here we should take lo,r0 such as f(lo)=0,and f(ro)=1

while(r-l>1)

{

int mid=(l+r)/2;

iif(f(mid)==0) l=mid;else r=mid;

}

What do we get? f(lo)=0(why? because we never assigned to l “something” if f(“something”)!=0) ! and f(ro)=1(the same thing,we always have f(newr)=1),and (ro-lo)==1! That’s what we need.

No let’s think what happens if lo and  are negative,for example,-1 and -6

(-1+-6)/2= -7/2..here we should have -4 to make the binary search working,but we have -3.

That’s why it’s better to replace the expression for mid with mid=l+(r-l)/2

Now we have mid=-6+(-1-6)/2=-6+(5/2)=-4.Nice:)

Java Fast I/O

Posted in Java by

Here is a template for Java fast input/output.You can use it in programming contests or some specific problems with standart I/O bottleneck.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main implements Runnable {

StringTokenizer st;
BufferedReader in;
PrintWriter out;

public void run() {
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(new OutputStreamWriter(System.out));

try {
solve();
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}

out.flush();
out.close();

}
public static void main(String[]args)
{
new Thread(null,
new Runnable()
{
public void run()
{
new Main().run();
}
},"1",1<<20).start();
}

private String nextToken() throws IOException
{
while(st==null || !st.hasMoreTokens())
{
st=new StringTokenizer(in.readLine());
}
return st.nextToken();
}
private int nextInt() throws NumberFormatException, IOException
{

return Integer.parseInt(nextToken());
}
private double nextDouble() throws NumberFormatException, IOException
{
return Double.parseDouble(nextToken());
}

private void solve() throws NumberFormatException, IOException
{
out.print("ads");
}

}

Fast fibonacci numbers calculation modulo P in O(LOG(N))

Posted in Algorithms by

A well -known fact about fibonacci is that it can be calculated  by getting  the n_th power of the matrix
[0 1 ;1 1].So we can use this idea combined with fast n-th power calculation:

long long Fib (long long n,long long p) {
long long res1 =1,res2=0,res3=0,res4=1;
long long a1=0,a2=1,a3=1,a4=1;
long long rres1,rres2,rres3,rres4;
while (n)
if (n & 1) {
//res *= a;
rres1=(res1*a1+res2*a3)%p;
rres2=(res1*a2+res2*a4)%p;
rres3=(res3*a1+res4*a3)%p;
rres4=(res3*a2+res4*a4)%p;
res1=rres1;
res2=rres2;
res3=rres3;
res4=rres4;
n--;
}
else {
//a *= a;
rres1=(a1*a1+a2*a3)%p;
rres2=(a1*a2+a2*a4)%p;
rres3=(a3*a1+a4*a3)%p;
rres4=(a3*a2+a4*a4)%p;
a1=rres1;
a2=rres2;
a3=rres3;
a4=rres4;
n >>= 1;
}
return res4;
}