Spoj DSUBSEQ – CPP solution

Problem: http://www.spoj.com/problems/DSUBSEQ/

Say that so far you have generated so far N strings totally without using the letter A. Then you append the letter A and you generate N+N strings. Later, when you add the letter A again, you would like to know how many strings have been generated using the letter A. Obviously, if you add the letter A to those strings, you won’t get distinct.
Keep the number of totally string generated so far and the number of strings generated by using some letter. Later, when adding some letter (say K), then the strings you would generate is (TOTAL – NUM OF STRINGS GENERATED USING K).
Just update the invariant correctly.

#include <cstdio>

typedef long long ll;
#define MOD 1000000007LL
ll arr[30];
char str[100001];

inline ll mod(ll num) {
    num %= MOD;
    if (num < 0LL) num += MOD;
    return num;
}

int main() {
    int t;
    scanf("%d",&t);
    while (t--) {
        scanf("%s", str);
        int i = 0;
        ll sum = 1LL;
        while (str[i]) {
            ll tmp = mod(sum-arr[str[i]-'A']);
            arr[str[i]-'A'] = mod(arr[str[i]-'A']+tmp);
            sum = mod(sum+tmp);
            i++;
        }
        //sum = mod(sum+1LL);
        for (int i = 0; i < 30; i++) arr[i] = 0LL;
        printf("%lldn", sum);
    }
    return 0;
}

Spoj MOHIB1 – CPP solution

Problem: http://www.spoj.com/problems/MOHIB1/

Solution:
Let’s say that we want to answer for N. We first check the first ball, which will collide with balls 2,3,..N.
=> In the box we will then have the sum of the numbers from 2…N. Then we pick ball number 2 and it will collide with balls 3…N. => In the box we will then add sum(3…N) * 2.

=> answer for N is
answer(N) = sum (2…N) * 1 + sum(3…N) * 2 + sum(4..N) * 3 + … + sum(N…N)*(N-1)

We have to calculate this in a fast way. We can use dynamic programming for the sums and for the answers as well.
Precomputation should be done in O(N) time where N < = 10^4. Which will give us a O(1) time to answer a query (test). Let us say that we have the answer for all queries till K and we want to check for K+1. this means that the answer would be: sum (2...K) + (K+1) + (sum(3...K) + (K+1)) * 2 + (sum(4...K) + K+1) * 3 + ... + (sum(K...K) + K + 1) * (K-1) + sum(K+1 ... K+1) * K which is the same as answer(K+1) = answer(K) + sum(1...K) * (K+1). We have for sure precomputed already answer(K) and sum (1...K). => transition is very easy.

Code:

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

typedef unsigned long long ull;

ull dp[10001];
ull ans[10001];

void precompute() {
    for (ull i = 1; i<= 10000ULL; ++i) {
        dp[i] = dp[i-1]+i;
        if (i >= 2ULL) {
            ans[i] = ans[i-1] + dp[i-1]*i;
        }
    }
}

ull comp(int n) {
    return ans[n];
}

int main() {
    precompute();
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        ull ans = comp(n);
        printf("%llun", ans);
    }
    return 0;
}

SPOJ 3878. Rectangles Perimeter – CPP solution

Another nice dp problem though quite easy.

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

long dp[1001][2];

 long max(long a, long b) {
    if (a < b) return b;
    return a;
}

long abs(long a) {
    return a > 0 ? a : -a;
}

int main() {
    int n;
    scanf("%d", &n);
    int a,b;
    int preva,prevb;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d",&a,&b);
        if (i == 0) {
            dp[i][0]=a;
            dp[i][1]=b;
        } else {
            dp[i][0]=max(dp[i-1][1]+abs(b-preva),dp[i-1][0]+abs(b-prevb))+a;
            dp[i][1]=max(dp[i-1][1]+abs(a-preva),dp[i-1][0]+abs(a-prevb))+b;

        }
        preva=a;
        prevb=b;
    }
    printf("%ldn", max(dp[n-1][0],dp[n-1][1]));
    return 0;
}

Spoj 1871. Making A Budget – CPP solution

A nice dp problem though the description of it could be better. I had to assume that the number of workers is 300 (could not pass with 1000).

#include <iostream>
using namespace std;

// dp[month][workers] = current sum
#define INF 99999999
#define MAX 300

int main () {
    for (int t=1;1;++t) {
        int months, hire, salary, severe;
        cin >> months;
        if (months==0)break;
        cin >> hire >> salary >> severe;
        int dp[24][MAX]={INF};
        for (int i = 0;i<months;++i) {
            for (int j = 0;j<MAX;++j) dp[i][j]=INF;
        }
        int needed;
        int prev;
        for (int i = 0; i < months; ++i) {
            cin >> needed;
            if (i == 0) {
                for (int k = 0;k < MAX; ++k) {
                    dp[i][k] = k*(salary+hire);
                }
            } else {
                for (int k=0; k < MAX; ++k) {
                    for (int j = prev; j < MAX; ++j) {
                        if (k<j) {
                            dp[i][k] = min(dp[i][k], dp[i-1][j]+(j-k)*severe + k*salary);
                        } else {
                            dp[i][k] = min(dp[i][k], dp[i-1][j]+(k-j)*hire + k*salary);
                        }
                    }
                }
            }
            prev = needed;
        }
        int ans = INF;
        for (int i = MAX-1; i>=needed; --i) {
            ans = min(ans, dp[months-1][i]);
        }
        cout << "Case " << t << ", cost = $"<< ans << endl;
    }
    return 0;
}

SPOJ Wise And Miser – CPP solution

A very basic dynamic programming problem. Basically:
for the kth city you see see what is the best possible time using each of the buses based on the best time for the (k-1)-th city.

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

#define INF 99999999

int min(int a, int b) {
      return a < b ? a : b;
}

int main() {
    int n,m;
    int g[101][101];
    int dp[101][101];
    scanf("%d%d",&n,&m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {             scanf("%d", &g[i][j]);         }         if (i > 0) {
            for (int j = 0; j < m; ++j) {                 dp[i][j] = INF;                 if (j>0) {
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1] + g[i][j]);
                }
                if (j < m-1) {
                    dp[i][j] = min(dp[i][j], dp[i-1][j+1] + g[i][j]);
                }
                dp[i][j] = min(dp[i][j], dp[i-1][j] + g[i][j]);
            }
        } else {
            for (int j = 0; j < m; ++j) {
                dp[i][j] = g[i][j];
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < m; ++i) {
        ans = min(dp[n-1][i], ans);
    }
    printf("%dn", ans);
    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.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 2.3 Zerosum – CPP solution

A DFS solution would be fast enough to pass the tests. We have just N-1 places to put signs where N is the number of digits we can use. This yields that the time complexity of our algorithms is O(3^(N-1)) where N can be maximum 9. We will generate every possible expression and then evaluate it. If it sums to zero, then we just print it. In order to get in in ASCII order, we will first use the empty sign, then the + sign and then the – sign.

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

ifstream in;
ofstream out;

int n;

vector<int> numbers;
char signs[10];

int calcSum() {
    int sum = numbers[0];
    for (int i = 1; i < numbers.size(); ++i) {
        if (signs[i-1]=='+') {
            sum+=numbers[i];
        } else {
            sum-=numbers[i];
        }
    }
    return sum;
}

void printSolution() {
    for (int i = 0; i < numbers.size(); ++i) {
        int tmp = numbers[i];
        string c;
        while (tmp!=0) {
            c.insert(0,1,(char)(tmp%10 + '0'));
            if (tmp>10) c.insert(0,1,' ');
            tmp/=10;
        }
        out << c;
        if (i+1!=numbers.size()) out << signs[i];
    }
    out << endl;
}

void dfs(int curNumber, int curSign) {
    if (curNumber == n+1) {
        int sum = calcSum();
        if (sum==0) {
            printSolution();
        }
        return;
    }
    numbers[numbers.size()-1] = numbers[numbers.size()-1]*10+curNumber;
    dfs(curNumber+1,curSign);
    numbers[numbers.size()-1] = (numbers[numbers.size()-1]-curNumber)/10;
    signs[curSign] = '+';
    numbers.push_back(curNumber);
    dfs(curNumber+1,curSign+1);
    signs[curSign] = '-';
    dfs(curNumber+1,curSign+1);
    numbers.pop_back();
}

int main() {
    in.open("zerosum.in");
    in >> n;
    in.close();
    out.open("zerosum.out");
    numbers.push_back(1);
    dfs(2,0);
    out.close();
}

Another idea (not implemented): It is fairly obvious that we cannot have more than 2 empty signs since the integer would get too big and we cannot get a zero sum. We could generate every possible number (1,2,3,4 … 12,23,34 … 89). Keep an array dp[2000]. If dp[x] is equal to one, then we can generate the value X. We will always add an offset to the sum. That’s why we have to create such a big array. We will also keep a vector array (vector from[2000]) to keep the solutions. After we have calculated all the possible sums using dynamic programming, we will just use the from array to print all the solutions. What’s the time complexity? We have N numbers and a sum from -1000 to +1000 (+offset). For every number we will have to either add it, subtract it or append it to the current number in the dp array. The time complexity is O(C*N) where C is the maximum size of the array. As you have probably noticed, this solution is very similar to the 1-0 knapsack problem.