USACO 3.4 Electric Fence – CPP solution

This is an interesting problem which I was not able to solve by the first try and I will shortly explain why after I explain what is my solution ( O(N) time where N is the maximum Y value).
We get the information about the two lines which make the triangle. By information, I mean the slope and the C value. (y = slope*x + C).
The we just iterate from 0 to the maximum Y value of our triangle (the pivot point) and we check what is the possible leftest value and accordingly rightest value. Then we add the value count (right-left+1) to our COUNT variable.
Everything seems fine and the solution yields just O(N) time where N is at maximum 32 000 (a fairly small number).

You may as well try the solution on your really cool computer with the latest 64bit processor and you will probably always get the right answer. But after you submit it, you will get a wrong answer warning from USACO. How come? Everything works correct on your computer? Well, it is mostly because your processor is 64bit and their maybe 32bit? I don’t really know and I do not want to get into really technical stuff.

The problem is with the decimal part. For example, we may receive for rights X value 9.999998 which should be actually 10.0 or it might be even 10.01 or even more. We will add an EPS value (a very small number) to check whether one value equals another. For example, 9.99998 will equal 10.00 and 10.0001 will equal 10.00.

Just now our program seems to work flawlessly.

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

#define INF -99999.0
#define EPS 0.00001

double n,m,p;
long long cnt = 0;

struct line {
    double k;
    double c;
};

line leftLine,rightLine;

line makeLine (double k, double c) {
    line tmp;
    tmp.k = k;
    tmp.c = c;
    return tmp;
}

double slope(double x1, double y1, double x2, double y2) {
    if (x2-x1==0.0) return INF;
    return (y2-y1)/(x2-x1);
}

double properRound(double value) {
    double ceiled = ceil(value);
    double floored = floor(value);
    if (value-EPS <= floored) return floored;
    if (value+EPS >= ceiled) return ceiled;
    return value;
}

int getLeft(int y) {
    if (leftLine.k == INF) {
        return 1;
    }
    double pos = properRound((y-leftLine.c)/leftLine.k);
    return floor(pos + 1.0);
}

int getRight(int y) {
    double pos = properRound((y-rightLine.c)/rightLine.k);
    return ceil(pos-1.0);
}

int getCount(int y) {
    return getRight(y)-getLeft(y)+1;
}

void solve() {
    leftLine = makeLine(slope(0.0,0.0,n,m),0.0);
    rightLine = makeLine(slope(p,0.0,n,m),-slope(p,0.0,n,m)*p);
    for (double i = 1.0; i < m; i+=1.0) {
        cnt += getCount(i);
    }
}

int main() {
    ifstream in("fence9.in");
    in >> n >> m >> p;
    in.close();
    solve();
    ofstream out("fence9.out");
    out << cnt << endl;
    out.close();
    return 0;
}

HC-05 Bluetooth Module Windows 7 problems

If you have bought an Arduino bluetooth module (or whatever other device) and it uses the HC-05 chip, then you will probably have a problem establishing a connection with your computer. You will first establish it and shortly the connection will break.
This is because of the Windows 7 bluetooth drivers. I had some serious problems fixing this issue and there were a lot of people having the same issue.
So what is the solution: just install other bluetooth drivers or just install another OS like Ubuntu (it runs flawlessly ).

USACO 3.3 American Heritage – CPP solution

I think this is one of my favorite problems in USACO although it is quite easy. However, it includes a lot of things one needs to know in order to be solved efficiently – binary trees, dp and most importantly programming (working with pointers and creating dynamic structures).
The idea is simple: since we have two kind of traverses of the tree( in-order and pre-order), we can build up the tree by the data. Then, we will just traverse the tree in post-order.

#include <iostream>
#include <fstream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

string inorder;
string preorder;

struct node {
    string value;
    struct node * left;
    struct node * right;
    struct node * parent;
};

node * tree;
node * map[128];
string ans;

node * buildNode(string value, node * left, node * right, node * parent) {
    node * tmp = new node[1];
    tmp->value = value;
    tmp->left = left;
    tmp->right = right;
    tmp->parent = parent;
    return tmp;
}

void setInMap(string str, node * parent) {
    for (int i = 0; i < str.length(); ++i) {
        map[str.at(i)] = parent;
    }
}

void buildTree(char value) {
    node * tmp = map[value];
    size_t index = tmp->value.find(value,0);
    string left = tmp->value.substr(0,index);
    string right = tmp->value.substr(index+1,tmp->value.length()-(index+1));
    tmp->value = tmp->value.substr(index,1);
    tmp->left = buildNode(left,NULL,NULL,tmp);
    tmp->right = buildNode(right,NULL,NULL,tmp);
    setInMap(left,tmp->left);
    setInMap(right,tmp->right);
    if (value == preorder.at(0)) {
        tree = tmp;
    }
}

void traversePostOrder(node * tmp) {
    if (tmp->left != NULL && tmp->left->value != "") {
        traversePostOrder(tmp->left);
    }
    if(tmp->right != NULL && tmp->right->value != "") {
        traversePostOrder(tmp->right);
    }
    ans.append(tmp->value);
}

int main() {
    ifstream in ("heritage.in");
    in >> inorder >> preorder;
    in.close();

    tree = buildNode(inorder, NULL, NULL, NULL);
    setInMap(inorder,tree);

    for (int i = 0; i<preorder.length(); ++i) {
        buildTree(preorder.at(i));
    }
    traversePostOrder(tree);
    ofstream out("heritage.out");
    out << ans << endl;
    out.close();
    return 0;
}

This is one of the few times when I nail the problem by the first try. Usually, I always forget something whether it would be a special case or just accessing a forbidden file.

USER: Martin Radev [martin.28]
TASK: heritage
LANG: C++

Compiling…
Compile: OK

Executing…
Test 1: TEST OK [0.000 secs, 3504 KB]
Test 2: TEST OK [0.000 secs, 3504 KB]
Test 3: TEST OK [0.000 secs, 3504 KB]
Test 4: TEST OK [0.000 secs, 3504 KB]
Test 5: TEST OK [0.000 secs, 3504 KB]
Test 6: TEST OK [0.000 secs, 3504 KB]
Test 7: TEST OK [0.000 secs, 3504 KB]
Test 8: TEST OK [0.000 secs, 3504 KB]
Test 9: TEST OK [0.000 secs, 3504 KB]

All tests OK.
YOUR PROGRAM (‘heritage’) WORKED FIRST TIME! That’s fantastic
— and a rare thing. Please accept these special automated
congratulations.

Here are the test data inputs:

——- test 1 —-
ABEDFCHG
CBADEFGH
——- test 2 —-
F
F
——- test 3 —-
BCAD
ABCD
——- test 4 —-
GOLEAFS
SFAELOG
——- test 5 —-
GSHBAQTPM
ABGHSPQTM
——- test 6 —-
AUBYCVDZEWFXGTH
ZYUABVCDXWEFTGH
——- test 7 —-
ABDCJHKILMNPOQFEGRS
ABCDEFHJIKLMNOPQGRS
——- test 8 —-
GFDIHKLJMBNESRTPOQAUCWVZYX
ABDFGHIJKLMENOPRSTQCUVWXYZ
——- test 9 —-
EHGDIFJLKMBNCOQSPRAWUXZYTV
ABDEGHFIJKLMCNOPQSRTUWXYZV
Keep up the good work!
Thanks for your submission!

JSON – the solution to most of your problems

Whether from storing projects, receiving data or sending data, JSON is probably the best solution I have ever encountered. I have worked on quite a few projects which use JSON for communication and data storage. The latter has saved me a lot of the well-known headaches when a client tells you that he wants to add some new input to the current app/website.
So, what was my solution to this in the past? Total bull shit. I just made another field in the database, added the needed variables in the code, etc. Well, that’s not cool. Will you be constantly adding new fields in your table? Personally, I just store a text field called data and store everything in JSON format.

And what about data communication/parsing? Well, the other typical standard is xml which sucks, because the normal built-in methods do not parse it often very well and it is a pain in the ass to build one yourself when you’re in a hurry to finish the project. On the other end, JSON parsers work very well. For example, in PHP (yeah, that shit) there are two key methods for working with json -> json_decode and json_encode. And you can actually decode a JSON file to an array, which makes everything easy because you just have to use the foreach iterator or a normal loop.

Also, JSON is a way to make cool games/guis. In the libgdx framework (java game 2d development framework), you can give information about the skin of your actors with JSON. And this actually save you a lot of code. You just write all of the colors, fonts, etc you will use in the json file and there you have it – a beautiful working gui with a few lines of code to load the atlas, the skin, etc.

USACO 3.3 Home on the range – CPP solution

That was a relatively hard problem. I have started the problem with dynamic programming but from another angle. I have decided just to compute whether there are only 1’s for a given range. The state was [row][col start][col end]. Then I found out that it would not work with some compiles because 251^3 is too much memory for an array. Then I just to work around with another DP solution. Again, I will pre-compute whether I have 1s for a given range, but with the following states:
rows[row index][col index] = number of 1s on this row to the given col index
cols[row index][col index] = number of 1s on this col to the given row index
dp[row index][col index] = biggest square with right-bottom corner at row index, col index.

Then solution is hidden in the dp array. Let us say dp[i][j] is equal to p. There are p unique squares with lengths of the sides: 1 to p inclusive.

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

#define MAX 9999999
#define pii pair<int,int>
#define psi pair<pii,bool>

ifstream in;
ofstream out;

int n;

char g[251][251];
int ans[251] = {0};

int dp[251][251] = {0};
int vertical[251][251] = {0};
int horizontal[251][251] = {0};


void solve() {
    for (int i = 0; i < n; ++i) {
        dp[i][0] = g[i][0] == '1' ? 1 : 0;
        for (int j = 0; j < n; ++j) {
            dp[0][j] = g[0][j] == '1' ? 1 : 0;
            if (i == 0) {
                vertical[i][j] = g[i][j] == '1' ? 1 : 0;
            } else {
                vertical[i][j] = g[i][j] == '1' ? (vertical[i-1][j] + 1) : 0;
            }
            if (j == 0) {
                horizontal[i][j] = g[i][j] == '1' ? 1 : 0;
            } else {
                horizontal[i][j] = g[i][j] == '1' ? (horizontal[i][j-1] + 1) : 0;
            }
            if (i >= 1 && j >= 1) {
                if (g[i][j] == '1') {
                    int needed = dp[i-1][j-1]+1;
                    if (horizontal[i][j] >= needed && vertical[i][j] >= needed) {
                        dp[i][j] = needed;
                    } else {
                        dp[i][j] = max(1,min(horizontal[i][j],vertical[i][j]));
                    }
                } else {
                    dp[i][j] = 0;
                }
                if (dp[i][j] >= 2){
                    for (int k = 2; k <= dp[i][j]; ++k) {
                        ++ans[k];
                    }
                }
            }
        }
    }
}

int main() {
    in.open("range.in");
    in >> n;
    for (int i = 0; i < n; ++i) {
        in >> g[i];
    }
    in.close();
    solve();
    out.open("range.out");
    for (int i = 2; i<=n; ++i) {
        if (ans[i]>0) {
            out << i << " " << ans[i] << endl;
        }
    }
    out.close();
    return 0;
}

We could also do some changes to make the solution n^2:
We just have to remove the computation for ans[] from the inner cycles and do it out of the cycles after all of the dp computations are done. For ans[] we will just store the current value -> ans[dp[i][j]]+=1.
Then we will just go over all of the values in ans[] backwards.

USACO 3.3 Camelot – CPP solution

A relatively hard problem. We must be careful with the input since the characters represent the columns and the digits represent the rows.
Computing the shortest distance to a given cell for a given knight is easy – just use BFS. The shortest distance for the king to a given cell is the tricky part since there are two possibilities:
– to travel there on its own (very unlikely)
– to get picked up by a knight at some cell
The first possibility is easy to compute – use bfs or just use basic arithmetics (the distance is the maximum of the relative distances for X and Y).
The second is harder, but we can use memorization to solve it.

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

ifstream in;
ofstream out;

#define pii pair<int,int>
#define MAXR 30
#define MAXC 26
#define MAX 1000
#define INF 9999999


int n,m;
int used[MAX][MAXR][MAXC];
int kingUsed[MAX][MAXR][MAXC];
vector<pii> knights;
pii king;
int sz;

int pos(char c) {
    return (int)(c-'A');
}

int knightsMovesX[8] = {2,2,-2,-2,1,1,-1,-1};
int knightsMovesY[8] = {1,-1,1,-1,2,-2,2,-2};
int kingMovesX[8] = {1,1,1,0,0,-1,-1,-1};
int kingMovesY[8] = {-1,1,0,1,-1,-1,1,0};

bool ok(int x, int y) {
    if (x < 0 || y < 0 || x>=n || y >= m) return false;
    return true;
}

void bfsKnights(int index, pii position) {
    queue<pii> q;
    used[index][position.first][position.second] = 0;
    q.push(position);
    bool kingFound = false;
    int steps = INF;
    while (!q.empty()) {
        pii temp = q.front();
        q.pop();
        int cx = temp.first;
        int cy = temp.second;
        for (int i = 0; i < 8; ++i) {
            int nx = cx + knightsMovesX[i];
            int ny = cy + knightsMovesY[i];
            if (ok(nx,ny)) {
                if (used[index][nx][ny]!=-1) {
                    if (used[index][cx][cy] + 1 == used[index][nx][ny]) {
                        kingUsed[index][nx][ny] = min(kingUsed[index][cx][cy],kingUsed[index][nx][ny]);
                    }
                    continue;
                }
                used[index][nx][ny] = used[index][cx][cy] + 1;
                kingUsed[index][nx][ny] = min(kingUsed[index][cx][cy],kingUsed[index][nx][ny]);
                q.push(pii(nx,ny));
            }
        }
        //cout << endl;
    }
}

void bfsKing() {
    queue<pii> q;
    for (int i = 0; i < sz; ++i) {
        kingUsed[i][king.first][king.second] = 0;
    }
    q.push(king);
    while (!q.empty()) {
        pii temp = q.front();
        q.pop();
        int cx = temp.first;
        int cy = temp.second;
        for (int i = 0; i < 8; ++i) {
            int nx = cx + kingMovesX[i];
            int ny = cy + kingMovesY[i];
            if (ok(nx,ny) && kingUsed[0][nx][ny]==-1) {
                for (int k = 0; k < sz; ++k) {
                    kingUsed[k][nx][ny] = kingUsed[k][cx][cy] + 1;
                }
                q.push(pii(nx,ny));
            }
        }
    }
}

void print(int index) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << used[index][i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

void printKing(int index) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << kingUsed[index][i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

void clear(int index) {
    for (int k = 0; k < n; ++k) {
        for (int j = 0; j < m; ++j) {
            used[index][k][j] = -1;
        }
    }
}

void clearKing(int index) {
    for (int k = 0; k < n; ++k) {
        for (int j = 0; j < m; ++j) {
            kingUsed[index][k][j] = -1;
        }
    }
}

int main() {
    ifstream in("camelot.in");
    in >> n >> m;
    char a;
    int b;
    in >> a >> b;
    king = pii(b-1,pos(a));
    while (in >> a >> b) {
        knights.push_back(pii(b-1,pos(a)));
    }
    in.close();
    sz = knights.size();
    for (int i = 0; i < sz; ++i) {
        clearKing(i);
    }

    bfsKing();
    for (int i = 0; i < sz; ++i) {
        clear(i);
        bfsKnights(i,knights[i]);
    }
    int ans = INF;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int sum = 0;
            int kingCost = INF;
            for (int k = 0; k < sz; ++k) {
                if (used[k][i][j]==-1) {
                    sum = INF;
                } else {
                    sum += used[k][i][j];
                }
                kingCost = min(kingCost,kingUsed[k][i][j]);
                //cout << i << " " << j << " " << used[k][i][j] << " " << kingUsed[k][i][j] << endl;
                //cout << kingUsed[k][i][j] << endl;
            }
            sum += kingCost;
            if (ans > sum) {
                ans = sum;
            }
        }
    }

    ofstream out("camelot.out");
    if (ans == INF) ans = 0;
    out << ans << endl;
    out.close();
    return 0;
}

Battle for Space – a java game with LibGDX

Ok, I have kind of finished my fist java game using the libgdx framework and the box2d physics engine. It is a simple space shooter. I could have also skipped using the box2d engine, but I have decided to use it just to get a hang of it.
Photos of the game:

Menu:
menu

In the game:
game

Game over:
gameover

To move use the arrows, to shoot use the space button.
JAR file + source: Battle for Space

The game could be easily deployed for ios and android.

USACO 3.3 Shopping Offers – CPP solution

It is the same at the 01 knapsack problem, but we must find another state. Firstly, I tried using a map to store the state (i.e. 00001, 02105), but it could not pass the last test. If we use a penta array, the solution is fast enough.

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

#define pii pair<int,int>
#define psi pair<string,int>
#define MAX 9999999
#define MAXI 6

FILE * in, *out;

int best = MAX;

struct item {
    int id;
    int cnt;
};

struct offer {
    int cnt;
    vector<item> items;
    int price;
};

int n,s;

vector<offer> offers;

int comp[10000];

int dp[MAXI][MAXI][MAXI][MAXI][MAXI];
int need[5] = {0};

void solve() {
    for (int i = 0; i < MAXI; ++i) {
        for (int j = 0; j < MAXI; ++j) {
            for (int k = 0; k < MAXI; ++k) {
                for (int z = 0; z < MAXI; ++z) {
                    for (int r = 0; r < MAXI; ++r) {
                        // stop
                        for (int a = 0; a < MAXI-i; ++a) {
                            for (int b = 0; b < MAXI-j; ++b) {
                                for (int c = 0; c < MAXI-k; ++c) {
                                    for (int d = 0; d < MAXI-z; ++d) {
                                        for (int e = 0; e < MAXI-r; ++e) {
                                            int ai = a+i;
                                            int bi = b+j;
                                            int ci = c+k;
                                            int di = d+z;
                                            int ei = e+r;
                                            if (dp[ai][bi][ci][di][ei]>dp[i][j][k][z][r]+dp[a][b][d][e]) {
                                                //cout << dp[ai][bi][ci][di][ei] << " ";
                                                dp[ai][bi][ci][di][ei] = dp[i][j][k][z][r]+dp[a][b][d][e];
                                                //cout << dp[ai][bi][ci][di][ei] << endl;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

int main() {
    in = fopen("shopping.in","r");
    fscanf(in,"%d",&s);
    offer tmp;
    item tmp2;
    for (int i = 0; i < s; ++i) {
        fscanf(in,"%d",&tmp.cnt);
        tmp.items.clear();
        for (int j = 0; j < tmp.cnt; ++j) {
            fscanf(in,"%d%d",&tmp2.id, &tmp2.cnt);
            tmp.items.push_back(tmp2);
        }
        fscanf(in,"%d",&tmp.price);
        offers.push_back(tmp);
    }
    fscanf(in,"%d",&n);
    int id,cnt,regular_price;
    for (int i = 0; i < MAXI; ++i) {
        for (int j = 0; j < MAXI; ++j) {
            for (int k = 0; k < MAXI; ++k) {
                for (int z = 0; z < MAXI; ++z) {
                    for (int r = 0; r < MAXI; ++r) {
                        dp[i][j][k][z][r] = MAX;
                    }
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {

        fscanf(in,"%d%d%d",&id,&cnt,&regular_price);


        comp[id] = i;
        need[i] = cnt;
        int cur[5];
        for (int j = 0; j < 5; ++j) {
            cur[j] = 0;
        }
        cur[i]=1;
        dp[cur[0]][cur[1]][cur[2]][cur[3]][cur[4]] = regular_price;
    }

    for (int i = 0; i < s; ++i) {
        int cur[5] = {0};
        for (int j = 0; j < offers[i].cnt; ++j) {
            cur[comp[offers[i].items[j].id]] = offers[i].items[j].cnt;
        }
        dp[cur[0]][cur[1]][cur[2]][cur[3]][cur[4]] = min(dp[cur[0]][cur[1]][cur[2]][cur[3]][cur[4]],offers[i].price);
    }


    fclose(in);
    solve();

    out = fopen("shopping.out","w");
    if (dp[need[0]][need[1]][need[2]][need[3]][need[4]]==MAX) dp[need[0]][need[1]][need[2]][need[3]][need[4]] = 0;
    fprintf(out,"%dn",dp[need[0]][need[1]][need[2]][need[3]][need[4]]);
    fclose(out);
}