CodeForces B. The least round way – CPP solution

Link to problem:
Almost classic dynamic programming problem. Key is that you have to minimize the number of 2s and 5s and also consider the case when there could be a 0 in the input meaning that the upper bound for the answer becomes 1. However, the best answer could be still 0. Consider the input case:
3
1 1 1
1 0 1
1 1 1
There is a 0, but if you walk on the border, then the answer is 0, not 1.

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

#define MAX 1001

struct Pair {
    long fives;
    long twos;
};

long twos[MAX][MAX];
long fives[MAX][MAX];
long t[MAX][MAX];
int n;
char path[3*MAX];
char path_matrix_twos[MAX][MAX];
char path_matrix_fives[MAX][MAX];

Pair makePair(long twos, long fives) {
    Pair p;
    p.twos = twos;
    p.fives = fives;
    return p;
}

Pair compPair(int i, int j) {
    long twos=0, fives=0;
    int cpy = t[i][j];
    do {
        if (cpy%2 == 0) {
            ++twos;
            cpy /= 2;
        } else if (cpy%5 == 0) {
            ++fives;
            cpy /=5;
        } else {
            break;
        }
    }
    while(cpy!=0);
    return makePair(twos,fives);
}

void comp() {
    for (int i = 1; i < n; ++i) {
        twos[0][i] += twos[0][i-1];
        twos[i][0] += twos[i-1][0];
        path_matrix_twos[0][i] = 'L';
        path_matrix_twos[i][0] = 'T';
        fives[0][i] += fives[0][i-1];
        fives[i][0] += fives[i-1][0];
        path_matrix_fives[0][i] = 'L';
        path_matrix_fives[i][0] = 'T';
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < n; ++j) {
            if (twos[i-1][j] < twos[i][j-1]) {
                twos[i][j] += twos[i-1][j];
                path_matrix_twos[i][j] = 'T';
            } else {
                twos[i][j] += twos[i][j-1];
                path_matrix_twos[i][j] = 'L';
            }
            if (fives[i-1][j] < fives[i][j-1]) {
                fives[i][j] += fives[i-1][j];
                path_matrix_fives[i][j] = 'T';
            } else {
                fives[i][j] += fives[i][j-1];
                path_matrix_fives[i][j] = 'L';
            }
        }
    }
}

int main() {
    scanf("%d",&n);
    int zero = 0;
    int zeroPosI, zeroPosJ;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%ld", &t[i][j]);
            Pair p = compPair(i,j);
            twos[i][j] = p.twos;
            fives[i][j] = p.fives;
            if (t[i][j]==0) {
                zero = 1;
                zeroPosI = i;
                zeroPosJ = j;
            }
        }
    }
    comp();
    long ans = min(twos[n-1][n-1], fives[n-1][n-1]);
    if (ans > 1 && zero==1) {
        ans = 1;
        int idx=0;
        for (int i = 0; i < zeroPosI; ++i) {
            path[idx++] = 'D';
        }
        for (int j = 0; j < zeroPosJ; ++j) {
            path[idx++] = 'R';
        }
        for (int i = zeroPosI; i < n-1; ++i) {
            path[idx++] = 'D';
        }
        for (int j = zeroPosJ; j < n-1; ++j) {
            path[idx++] = 'R';
        }
    } else {
        if (twos[n-1][n-1] < fives[n-1][n-1]) {
            int x = n-1, y = n-1;
            for (int i = 2*(n-1) -1; i>=0; --i) {
                if (path_matrix_twos[y][x] == 'L') {
                    --x;
                    path[i] = 'R';
                } else {
                    --y;
                    path[i] = 'D';
                }
            }
        } else {
            int x = n-1, y = n-1;
            for (int i = 2*(n-1) -1; i>=0; --i) {
                if (path_matrix_fives[y][x] == 'L') {
                    --x;
                    path[i] = 'R';
                } else {
                    --y;
                    path[i] = 'D';
                }
            }
        }
    }




    printf("%ldn", ans);
    printf("%sn", path);
    return 0;
}

Spoj GSS3 – CPP solution

The problem is the same as GSS1. The only difference is the modify (update) operation.

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

void modify(int from, int to, int index, int indexMod) {
    if (from == to && from == indexMod) {
        tree[index] = makeNode(q[from], q[from], q[from], q[from]);
        return;
    }
    int mid = (from+to)/2;
    if (indexMod <= mid) {
        modify(from, mid, (index<<1), indexMod);
    } else {
        modify(mid+1, to, (index<<1)+1, indexMod);
    }
    tree[index] = combine(tree[index<<1],tree[(index<<1)+1]);
}


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,c;
    for (int i = 0; i < t; ++i) {
        scanf("%d%d%d",&a,&b,&c);
        if (a == 0) {
            q[b] = c;
            modify(1,n,1,b);
        } else {
            printf("%ldn", ans(1,1,n,b,c).best);
        }

    }
    return 0;
}

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