Binary Heap – C++ implementation

It is relatively unlikely to find a simple implementation of this structure online, so…:

#include <iostream>
using namespace std;

#define MAX 10000
#define NONE -1

struct heap {
    int values[10000];
    int size;
};

int parent(int index) {
    return (index-1)>>1;
}

int leftChild(heap * h, int index) {
    int ch = (index<<1)+1;
    return h->size<= ch ? NONE : ch;
}

int rightChild(heap * h, int index) {
    int ch = (index<<1)+2;
    return h->size<= ch ? NONE : ch;
}

void swap(heap * h, int a, int b) {
    int tmp = h->values[a];
    h->values[a] = h->values[b];
    h->values[b] = tmp;
}

void heapifyDown(heap * h) {
    int index = 0;
    while (index != h->size-1) {
        int lIndex = leftChild(h, index);
        int rIndex = rightChild(h, index);
        if (lIndex == NONE) return;
        int childIndex = lIndex;
        if (rIndex == NONE) {
            childIndex = lIndex;
        } else if(h->values[lIndex] > h->values[rIndex]) {
            childIndex = rIndex;
        }
        swap(h,index,childIndex);
        index = childIndex;
    }
}

void heapifyUp(heap * h, int index) {
    while (index) {
        int pIndex = parent(index);
        if (h->values[index] < h->values[pIndex]) {
            swap(h,index,pIndex);
            index = pIndex;
        } else {
            break;
        }
    }
}

void insert(heap * h, int value) {
    h->values[h->size++] = value;
    heapifyUp(h, h->size-1);
}

void pop(heap * h) {
    h->values[0] = h->values[--h->size];
    heapifyDown(h);
}

int top(heap * h) {
    return h->values[0];
}

bool isEmpty(heap * h) {
    return h->size==0;
}

heap * initHeap() {
    heap * tmp = new heap[1];
    tmp->size = 0;
    return tmp;
}

void print (heap * h) {
    for (int i = 0; i < h->size; ++i) {
        cout << h->values[i] << " ";
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    int a;
    heap * tmp = initHeap();
    for (int i = 0; i < n; ++i) {
        cin >> a;
        insert(tmp,a);
    }
    while (!isEmpty(tmp)) {
        int smallest = top(tmp);
        pop(tmp);
        cout << smallest << " ";
    }
    return 0;
}

USACO 3.4 Raucos Rockers – CPP solution

A not that hard DP problem. The problem is very similar to the 01-knapsack problem.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

FILE *in,*out;

int n,t,m;

#define MAX 21

int songs[MAX];
int dp[MAX][MAX];
int sack[MAX];
int ans = 0;

void clear() {
    for (int j = 0; j < MAX; ++j) {
        sack[j] = 0;
    }
}

int best (int from, int to) {
    if (from > to) return 0;
    clear();
    for (int i = from; i <= to; ++i) {
        for (int j = t; j >= 0; --j) {
            if (sack[j]>0 && j+songs[i] <= t && sack[j+songs[i]] < sack[j]+1) {
                sack[j+songs[i]] = sack[j] + 1;
            }
        }
        if (sack[songs[i]] == 0) {
            sack[songs[i]] = 1;
        }
    }
    int bestAns = 0;
    for (int i = t; i>=0; --i) {
        bestAns = max(bestAns,sack[i]);
    }
    return bestAns;
}

void solve() {
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = j; k < n; ++k) {
                if (i == 0) {
                    dp[i][k] = max(dp[i][k], best(i,k));
                } else {
                    dp[i][k] = max(dp[i][k], dp[i-1][j] + best(j+1,k));
                }

            }
        }
    }
    ans = dp[m-1][n-1];
}


int main() {
    for (int i = 0; i < MAX; ++i) {
        for (int j = 0; j < MAX; ++j) {
            dp[i][j] = 0;
        }
    }
    in = fopen("rockers.in","r");
    fscanf(in,"%d%d%d",&n,&t,&m);
    for (int i = 0; i < n; ++i) {
        fscanf(in,"%d",&songs[i]);
        if (songs[i] <= t) {
            dp[i][i] = 1;
        }
    }
    fclose(in);
    solve();
    out = fopen("rockers.out","w");
    fprintf(out,"%dn",ans);
    fclose(out);
    return 0;
}

USACO 3.4 Closed Fences – CPP solution

Checking whether the fence is valid is fairly simple. We just check whether one line segment intersects some other line segment (excluding the neighbor segments).
Afterwards, it is the tricky part. We have to find all the visible segments. How can we do that?
Let the observer be the point P and some random line segment be Q where its end points are respectively A and B.
We will partition the line in 250 parts (from A + EPS to B – EPS). Then we will build every possible line to the part points (i.e. the line P – (A + EPS*2)). Then we will just check whether the newly created line intersects some of the fence segments. If it doesn’t, the line segment Q is visible to P.
And also, we will have to use in our calculations as well. For example, in our check whether the value is nearly 0.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int n;

#define EPS 0.05
#define PARTITION 250.0

struct point {
    double x;
    double y;
};


struct line {
    point a;
    point b;
};

FILE * in, * out;

point p[202];
line l[202];
point observer;

vector<line> ans;

point makePoint(double x, double y) {
    point tmp;
    tmp.x = x;
    tmp.y = y;
    return tmp;
}

line makeLine(point a, point b) {
    line tmp;
    tmp.a = a;
    tmp.b = b;
    return tmp;
}

point operator -(point a, point b) {
    a.x -= b.x;
    a.y -= b.y;
    return a;
}

point operator +(point a, point b) {
    a.x += b.x;
    a.y += b.y;
    return a;
}

line getOrderedLine (line a) {
    if (a.a.y > a.b.y) {
        point tmp = a.a;
        a.a = a.b;
        a.b = tmp;
    }
    if (a.a.y == a.b.y && a.a.x > a.b.x) {
        point tmp = a.a;
        a.a = a.b;
        a.b = tmp;
    }
    return a;
}

double cross(point a, point b) {
    return a.x*b.y - a.y*b.x;
}

bool nearlyZero(double value) {
    if (value>=-EPS && value<=0) {
        return true;
    }
    return false;
}

void printPoint (point a) {
    cout << "(" << a.x << " " << a.y << ")";
}

void printLine(line a) {
    printPoint(a.a);
    cout << " - ";
    printPoint(a.b);
    cout << endl;
}

bool segmentIntersect(line a, line b) {
    a = getOrderedLine(a);
    b = getOrderedLine(b);
    double first = cross(a.b-a.a,b.a-a.a)*cross(a.b-a.a,b.b-a.a);
    double second = cross(b.b-b.a,a.a-b.a)*cross(b.b-b.a,a.b-b.a);
    if (nearlyZero(first) && nearlyZero(second)) {
        if (a.a.y!=a.b.y && b.a.y != b.b.y) {
            if (((a.a.y <= b.a.y && a.b.y >= b.a.y) || (b.a.y <= a.a.y && a.a.y <= b.b.y))) return true;
        } else {
            if ((a.a.x <= b.a.x && a.b.x >= b.a.x) || (b.a.x <= a.a.x && a.a.x <= b.b.x)) return true;
        }
        return false;
    }
    if (first > EPS) return false;
    if (second > EPS) return false;

    return true;
}


bool canSeeLine(line a, int ignoreIndex) {
    point delta = makePoint((a.b.x-a.a.x)/PARTITION, (a.b.y-a.a.y)/PARTITION);
    line cpy = a;
    for (int i = 0; i < PARTITION-1; ++i) {
        a.a = a.a+delta;
        line check = makeLine(observer, a.a);

        bool blocked = false;
        int j = 0;
        for (j = 0; j < n && !blocked; ++j) {
            if (j == ignoreIndex) continue;
            if (segmentIntersect(l[j],check)) {
                blocked = true;
            }
        }
        if (!blocked) {
            if (ignoreIndex==19) {
                printLine(cpy);
                printLine(a);
            }
            return true;
        }

    }
    return false;
}

void solve() {
    for (int i = 0; i < n-1; ++i) {
        for (int j = i+2; j < n-1; ++j) {
            if (segmentIntersect(l[i],l[j])) {
                printLine(l[i]);
                printLine(l[j]);
                return;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (canSeeLine(getOrderedLine(l[i]),i)) {
            ans.push_back(l[i]);
        }
    }
}

int getPointIndex(point a) {
    for (int i = 0; i < n; ++i) {
        if (a.x == p[i].x && a.y == p[i].y) return i;
    }
}

bool comparator(line a, line b) {
    int indexA = getPointIndex(a.b);
    int indexB = getPointIndex(b.b);
    if (indexA != indexB) return indexA < indexB;
    return getPointIndex(a.a) < getPointIndex(b.a);
}

int main() {
    in = fopen("fence4.in","r");
    int a,b;
    fscanf(in,"%d%d%d",&n,&a,&b);
    observer = makePoint(a,b);
    for (int i = 0; i < n; ++i) {
        fscanf(in,"%d %d",&a,&b);
        p[i] = makePoint((double)a,(double)b);
    }
    p[n] = p[0];
    for (int i = 0; i < n-1; ++i) {
       l[i] = makeLine(p[i],p[i+1]);
    }
    l[n-1] = makeLine(p[0],p[n-1]);
    fclose(in);
    solve();
    out = fopen("fence4.out","w");
    if (ans.size() == 0) {
        fprintf(out, "NOFENCEn");
    } else {
        fprintf(out,"%dn", ans.size());
        sort(ans.begin(),ans.end(), comparator);
        for (int i = 0; i < ans.size(); ++i) {
            fprintf(out,"%d %d %d %dn",(int)ans[i].a.x,(int)ans[i].a.y,(int)ans[i].b.x,(int)ans[i].b.y);
        }
    }
    fclose(out);
    return 0;
}

ADB pull/push operations

Usually, if you are an Android developer, you would like to pull and push files from/to your android emulated device. However, there are some issues you might encounter:

– When you pull or push, you might get a message that the directory is read-only
– You might not be able to find the file after you pulled it.

The problem-like way to pull and push files:
Run your adb device as a shell:
adb shell
Then just pull the file
adb pull /data/data/something/something.db C:tmpsomething.db

The problem-proof way to do it:
Open the DDMS perspective in Eclipse, find the file and download it by click the SAVE button.

“Fundamentals of Computer Programming with C#” finally came out

About a year and a half back I worked on the translation (and edit) of the famous Bulgarian programming book “Fundamentals of Computer Programming with C#” into English. Well, it is finally done and published:

So, what makes this book really good, challenging, but at the same time perfect for novices? Firstly, it covers ABSOLUTELY the fundamentals and we are not only talking about basic programming such as loops, containers, oop, etc… we are talking about real-life programming situations – how to solve problems, how to make your code readable for people who haven’t seen your work before, how to make things faster and mostly how to think like a professional software engineer.

It doesn’t only cover topics by just introducing the needed material, but also suggests a lot of fundamental problems in programming (which would usually be asked on an official interview). Of course, you may not be able to solve on them on your own. For this case, there are also published solutions + materials for further reading.

Two years and a half back I read the Java version of the same book which basically took my programming skills to a whole new level and gave me a deep understanding of programming.

There is not really which can be told more about this book, but really:

– It’s good
– It’s tested. Thousands of programmers in Bulgaria study on this book and afterwards work in the IT industry
– It’s free. You do not have to pay for it, you do not have to download it illegally

And here’s the website of the book:
http://www.introprogramming.info/english-intro-csharp-book/