Spoj GSS1 – CPP solution

Link to problem: http://www.spoj.com/problems/GSS1/
The solution is standard: a segment tree where information about the total sum, the maximum left possible, right possible and best sum.

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

struct node {
    long sum;
    long best;
    long left;
    long right;
};

int n;
long q[50003];
node tree[200003];

node makeNode(long sum, long best, long left, long right) {
    node tmp;
    tmp.sum = sum;
    tmp.best = best;
    tmp.left = left;
    tmp.right = right;
    return tmp;
}

node combine (node l, node r) {
    long left = l.left;
    if (l.sum + r.left>left) left =l.sum + r.left;
    long right = r.right;
    if (r.sum + l.right > right) right = r.sum + l.right;
    long best = max(l.right + r.left, max(l.best, r.best));
    return makeNode(l.sum+r.sum,best, left, right);
}

node build(int from, int to, int index) {
    if (from == to) {
        tree[index] = makeNode(q[from], q[from], q[from], q[from]);
        return tree[index];
    }
    int mid = (from+to)/2;
    node l = build(from,mid, (index<<1));
    node r = build(mid+1,to, (index<<1)+1);

    tree[index] = combine(l,r);
    return tree[index];
}

node ans(int index, int from, int to, int a, int b) {
    if (from == a && to == b) {
        return tree[index];
    }
    int mid = (from+to)/2;
    if (b <= mid) {
        return ans((index<<1), from, mid, a, b);
    }
    if (a > mid) {
        return ans((index<<1) + 1, mid+1,to,a,b);
    }
    node l = ans((index<<1), from, mid, a, mid);
    node r = ans((index<<1) + 1, mid+1,to,mid+1,b);
    return combine(l,r);
}


int main() {
    scanf("%d",&n);
    for (int i = 1; i <= n; ++i) scanf("%d",&q[i]);
    build(1,n,1);
    int t;
    scanf("%d",&t);
    int a,b;
    for (int i = 0; i < t; ++i) {
        scanf("%d%d",&a,&b);
        printf("%ldn", ans(1,1,n,a,b).best);
    }
    return 0;
}

USACO 4.2 The Perfect Stall – CPP solution

We need to match as much as values from the set N with the set M. We just create a graph where every element of N is connected to every possible to match element in M. Then we run a slightly modified DFS or as some people refer to it a modified flow alrorithm. It doesn’t really matter how we call it since the flow algorithms just find as much as possible paths from the source to the sink using either BFS, DFS or PFS (priority-first search or best-first search).

In other words we just check whether an element q from N can be matched with an element t of M. If q is possible to match with t but t is matched with another element z of the set N, we check whether that element z can be matched with another element in M. If it is possible, then we can for sure make such changes that q matches t since z can match another free element in M.

We do this for every element q in N.

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

int n,m;
int g[201][201];
int marked[201];
int used[201];

int dfs(int k) {
    for (int i = 1; i<=m; ++i) {
        if(g[k][i]<=0) continue;
        used[i] = 1;
        if (marked[i]==-1 || dfs(marked[i])) {
            marked[i] = k;
            return 1;
        }
    }
    return 0;
}

int flow() {

    memset(marked,-1,sizeof(marked));

    int ans = 0;

    for (int i = 1; i <= n; ++i) {
        memset(used,0,sizeof(used));
        ans += dfs(i);
    }

    return ans;

}

int main() {
    FILE *in = fopen("stall4.in", "r");
    fscanf(in, "%d%d", &n,&m);
    for (int i = 1; i<= n; ++i) {
        int c;
        int k;
        fscanf(in, "%d", &c);
        for (int z = 0; z < c; ++z) {
            fscanf(in, "%d", &k);
            g[i][k] = 1;
        }
    }
    fclose(in);
    FILE * out = fopen("stall4.out", "w");

    fprintf(out, "%dn", flow());
    fclose(out);

    return 0;
}

USACO 4.2 – Drainage Ditches CPP Solution

The problem is standard. Just use some flow algorithm. The constraints are small. You do not have to use Dinic here.

#include <algorithm>
#include <cstdio>
using namespace std;

#define MAX 999999

int n,m;
int g[201][201] = {0};
int path[201];

int found, minFlow;

void clear() {
    for (int i = 1; i<= n; ++i) path[i] = -1;
    found = 0;
    minFlow = MAX;
}

void dfs(int k, int parent) {
    if (found) return;
    if (path[k] != -1) return;
    path[k] = parent;
    if (k == n) {
        found = 1;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (g[k][i]>0) {
            dfs(i, k);
        }
    }
}


int flow() {
    int ans = 0;

    while(1) {
        clear();
        dfs(1, 0);
        if (path[n] == -1) return ans;
        int v1 = path[n],v2 =n, tmp = MAX;
        while(1) {
            if (v1 < 1) break;
            tmp = min(g[v1][v2], tmp);
            v2 = v1;
            v1 = path[v1];
        }
        v1 = path[n], v2 = n;
        ans += tmp;
        while (1) {
            if (v1 < 1) break;
            g[v1][v2] -= tmp;
            g[v2][v1] += tmp;
            v2 = v1;
            v1 = path[v1];
        }
    }

    return ans;
}

int main() {
    FILE * in = fopen("ditch.in", "r");
    FILE * out = fopen("ditch.out", "w");
    fscanf(in ,"%d%d", &m,&n);
    int a,b,c;
    for (int i = 0; i < m; ++i) {
        fscanf(in, "%d%d%d",&a,&b,&c);
        g[a][b] += c;
    }
    fprintf(out, "%dn", flow());
    fclose(in);
    fclose(out);
    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;
}

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

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!

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

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