Using gecode for simple arithmetic constraints


#include<stdio.h>
//3. (X in {1,2,3,4}) and (Y in {2,3,4}) 
//   and (Z in {4,5,10}) and X^2+Y^2=Z^2 and X<Y.
//Solution: X=3,Y=4,Z=5.

#include <gecode/int.hh>
#include <gecode/minimodel.hh>
#include <gecode/search.hh>


using namespace Gecode;

class Constraint3 : public Space {
protected:
  IntVarArray l;
public:
  Constraint3(void)  {
    const int range1[]={1,2,3,4};
    const int range2[]={2,3,4};
    const int range3[]={4,5,10};
    IntVar x(*this,IntSet(range1,4));
    IntVar y(*this,IntSet(range2,3));
    IntVar z(*this,IntSet(range3,3));
    IntVarArgs dynArray;
    dynArray<<x<<y<<z;
    l=IntVarArray(*this,dynArray);
    rel(*this, x<y);
    distinct(*this, l);
    rel(*this,      x*x+y*y==z*z);
    branch(*this, l, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
  }
  Constraint3(bool share, Constraint3& s) : Space(share, s) {
    l.update(*this, share, s.l);
  }
  virtual Space* copy(bool share) {
    return new Constraint3(share,*this);
  }
  void print(void) const {
    std::cout << l << std::endl;
  }
};

int main(int argc, char* argv[]) {
  Constraint3* m = new Constraint3;
  DFS<Constraint3> e(m);
  delete m;
  while (Constraint3* s = e.next()) {
    s->print(); delete s;
  }
  return 0;
}

Git commands for initial configuration

#!/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.

 

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 x0 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 that f(lo)=0, and f(ro)=1
while(r-l>1)</em>
{
  int mid=(l+r)/2;
  if(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

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&lt;&lt;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))

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;
}