Codeforces Round 187 ~ One Point Solution

I don't participate in codeforces rounds as much as I'd like. But it is hard enough to free my schedule to participate in TopCoder rounds (and I need to participate because it is my job to write editorials), then writing the editorials consumes quite a lot part of each week. Today I finally found a period of time in which I am both willing to try a codeforces round and I feel like I have time. So this happened.

Problem C - Sereja and Subsequences

Link to problem

I remember getting bored with the first two problems of division 1 codeforces, so this time I decided to start with the C.

In this problem, you like to find the sum of the products of each unique non-decreasing subsequence of a sequence. For example, if the unique non-decreasing subsequences were {1},{2} and {1,2}, the result is (1) + (2) + (1*2) .

An easy version

Let us forget that the maximum number of integers in the sequence is 10^5 and solve a slower version. This is a simple dynamic programming solution.

Let f(i) the sum of all the products of subsequences that start with seq[i]. It is easy to calculate it for i=N-1 (Base case). For other cases:

f(i) is at least seq[i], because there is a subsequence that contains only seq[i].
Else we need to find indexes j for subsequences starting with seq[j], so that we append seq[i] in front of the subsequences. We multiply seq[i] to the count of f(j) to find the sum of those products. however, in order not to repeat subsequences, we need j to be the smallest index that has value equal to seq[j].

The final result is to add up all res[i], whenever i is the smallest index to have value equal to seq[i].

const long MOD = 1000000007;
int N;
long seq[100000];
long res[1000001];

int solve()
{
    memset(res, 0, sizeof(res));
    for (int i=N-1; i >= 0; i--) {
        long nw = seq[i];
        
        for (int j=seq[i]; j <= 1000000; j++) {
            if (seq[j] >= seq[i]) {
                bool seen = false;
                for (int k=i+1; k<j; k++) {
                    seen |= (seq[j] == seq[k]);
                }
                if (! seen) {
                    res[i] = (res[i] + seq[i] * res[j] ) % MOD;
                }
            }
        }
    }
    long total = 0;
    for (int i=0; i<N; i++) {
        bool seen = false;
        for (int j=0; j<i; j++) {
            seen |= (seq[j] == seq[i]);
        }
        if (! seen) {
            total = (total + res[i]) % MOD;
        }
    }
    return total;
}

A less easy version

Instead of making sure the index j is the smallest index with value equal to seq[j], we can save up the work by replacing the function of the res[i] array, this time it returns the currently-known sum of products of subsequences that start with i (not seq[i]).

Then the dp looks like this:

const long MOD = 1000000007;
int N;
long seq[100000];
long res[1000001];

int solve()
{
    memset(res, 0, sizeof(res));
    for (int i=N-1; i >= 0; i--) {
        long nw = seq[i];
        
        for (int j=seq[i]; j <= 1000000; j++) {
            nw = (nw + seq[i]* res[j] ) % MOD;
        }
        res[i] = nw;
    }
    long total = 0;
    for (int i=1; i<1000000; i++) {
        total = (total + res[i]) % MOD;
    }
    return total;
}

Final one

In each step i, we just need to find the sum of all res[j] such that j >= seq[i]. Then replace res[i] with a new value. At the end, we need the sum of all res[j] such that j is >= 0. We can implement this solution using a tree. A special data structure that can quickly return the sum of all inserted values greater than or equal to an index. It should also be possible to quickly insert and remove. We can just use a binary indexed tree for this.

const long MOD = 1000000007;
int N;
long seq[100000];
long oldvalue[1<<20];

// Stuff for the tree:
// An index i is parent of 2*i+1, 2*i+2, and is related to an interval [a,b)
long tree[1<<21];

const int MIN = 0;
const int MAX = 1<<20;
void insert(int x, long value, int node=0, int a=MIN, int b=MAX)
{
    tree[node] = (tree[node] + value) % MOD;
    if (a < b-1) {
        int left  = 2*node + 1;
        int right = 2*node + 2;
        int m = (a + b) / 2;
        if (x < m) {
            insert(x,value, left, a, m); 
        } else {
            insert(x,value, right, m, b);
        }
    }
}

long sum(int x, int node=0, int a=MIN, int b=MAX)
{
    if (a >= x) {
        return tree[node];
    }
    if (b <= x) {
        return 0;
    }
    int m = (a + b) / 2;
    int left  = 2*node + 1;
    int right = 2*node + 2;
    long p = sum(x, left,a,m);
    long q = sum(x, right,m,b);
    return (p + q) % MOD;
}

int solve()
{
    memset(tree, 0, sizeof(tree) );
    memset(oldvalue, 0, sizeof(oldvalue));
    for (int i=N-1; i >= 0; i--) {
        // New value:
        long nw = (seq[i] * (1 + sum(seq[i])) ) % MOD;
        // This should remove the old value:
        insert(seq[i], MOD - oldvalue[seq[i]] );
        oldvalue[seq[i]] = nw;
        // Insert the new value:
        insert(seq[i], nw);
    }
    return sum(0);
}

One Point Solution

Friday, 7 June 2013