8
\$\begingroup\$

The original description of the problem can be found here, its input here and its expected output here.

The problem:

Given a integer sequence a1 ... an (-10000 \$\leq\$ ai \$\leq\$ 10000). Where n (1 \$\leq\$ n \$\leq\$ 100),the size of the sequence, is a given number.

Find the number of increasing subsequences with length equals to a given size k (1 \$\leq\$ k \$\leq\$ n \$\leq\$ 100).

An increasing subsequence ai1 ... aix of a sequence a1 ... an is defined as
aix-1, \$<\$ aix for all 1 \$<\$ x \$\leq\$ n).

The input has several testcases. The first line contains the numbers n and k. The second line contains a sequence of length n. 0 0 ends the input. The sequence will be given in a way that the subsequences count can't be bigger than a signed number of 64 bits.

Example:

10 5
1 2 3 4 5 6 7 8 9 10
3 2
3 2 1
0 0

The output is the number of increasing subsequences:

Example for the above input:

252
0

My solution uses a recursive idea. The sequence values are stored in an array of size n+1 with a \$-\infty\$ in the 0 index of the array. After this, a function goes from de 0 index to de n position recursively. And a comparison is made to check if the current value (picked) is less than the next value.

#include <stdio.h>
#include <string.h>
#include <limits.h>

long long memoization[102][102];

long long LCIS(int *S,int len,int picked,int LCISlen, int K){
    if(memoization[picked][LCISlen])
        return memoization[picked][LCISlen];

    long long q = 0;

    int i;
    for (i = picked + 1; i < len; i++) {
        if(S[picked] < S[i] && LCISlen < K)
            q += LCIS(S, len, i, LCISlen + 1, K);
        else if(S[picked] < S[i] && LCISlen == K)
            q++;
    }

    return memoization[picked][LCISlen] = q;
}

int main(){

    int N,K;
    while(scanf("%d %d",&N,&K), (N != 0) && (K != 0)){

        int i, S[N+1];

        S[0] = INT_MIN;

        for (i = 1; i <= N; i++)
            scanf("%d",&S[i]);

        memset(memoization,0,sizeof memoization);

        printf("%lld\n",LCIS(S,N+1,0,1,K));
    }
}

The solution got accepted by the judge, but it takes nearly 1 sec to give the answer. Other solutions take 0 seconds. This made me think that this solution isn't a good one.

\$\endgroup\$
11
\$\begingroup\$

Concept

You have called this a "Longest Increasing Subsequence" problem, but it's not, is it? It's counting all possible sequences of a specific length, not just the longest. As a result, I think you may have confused yourself in a few ways....

Naming

Your variable and method names are ... horrible. Variables should always be useful names, and, while N and K are referenced in the problem specification, S is not. Additionally, upper-case names are not encouraged... so you should have n and k instead. The method name LCIS is also off, it should be longest_increasing_sequence, and where does the C in LCIS come from?

Standards

Your code compiles OK (with a warning about the missing return in the main method) with basic C compiler. This makes me think you intend to use C99 which compiles it without warnings. But, in C99, you should declare your variables where they are used, not at the beginning of the blocks. For example, you should declare i inside the for-loop.

Globals

Globals are to be avoided.

Algorithm

Your concept of memoization is good, but I am not convinced the recursion is doing what you think it does. I am not convinced the memoization is used at all effectively. Frankly, I struggled to follow your algorithm, in part because memoization does not tell me much about what is being memoized...

I started hacking your code, and ended up restructuring it as a set of nested loops. The resulting complexity is somewhere around \$O(n^3)\$, which sounds really bad, but, for the problem given I am not sure can be improved on... A large part of the complexity is in the determination of the paths, not the combinatorics required to compute the count. I am likely wrong here somewhere, but my performance of the resulting code is more than good enough to be in the right ballpark...

So, I use memoization as well, the system I use is, for each node, starting from the last, to record the number of increasing paths, and how long they are, to the end of the sequence. The last node, for example, can be the last node in the sequence, and thus has a count of 1 in path-length 0 (0 because I zero-base the path length - 0 really means "there is 1 path starting from this node where this node is the last member too").

With that system, I can then work backwards through the sequence, and simply add up the paths that have the right length.

The critical method looks like:

long long count_sequences(const int *seq, const int size, const int path) {
    long long pathcounts[size][size];

    memset(pathcounts, 0, sizeof(pathcounts[0][0]) * size * size);

    long long count = 0;

    // start from end and work back.
    for (int i = size - 1; i >= 0; i--) {
        //printf("  start %d at %d\n", seq[i], i);
        // always 1 step from here to end.
        pathcounts[i][0] = 1;
        for (int j = i + 1; j < size; j++) {

            // check for increasing sequence
            if (seq[j] > seq[i]) {
                //printf("    next %d at %d\n", seq[j], j);

                for (int k = size - j; k >= 0; k--) {
                    pathcounts[i][k + 1] += pathcounts[j][k];
                }
            }
        }
        // zero-based path length - must subtract 1
        count += pathcounts[i][path - 1];
    }

    return count;
}

Note how, at each level we have to look ahead for increasing members, but, we only need to look in to the memoization for increasing members to accumulate path lengths.

Note also how we can accumulate the count as we retreat?

The entire program I have is:

#include <stdio.h>
#include <string.h>
#include <limits.h>

long long count_sequences(const int *seq, const int size, const int path) {
    long long pathcounts[size][size];

    memset(pathcounts, 0, sizeof(pathcounts[0][0]) * size * size);

    long long count = 0;

    // start from end and work back.
    for (int i = size - 1; i >= 0; i--) {
        //printf("  start %d at %d\n", seq[i], i);
        // always 1 step from here to end.
        pathcounts[i][0] = 1;
        for (int j = i + 1; j < size; j++) {

            // check for increasing sequence
            if (seq[j] > seq[i]) {
                //printf("    next %d at %d\n", seq[j], j);

                for (int k = size - j; k >= 0; k--) {
                    pathcounts[i][k + 1] += pathcounts[j][k];
                }
            }
        }
        // zero-based path length - must subtract 1
        count += pathcounts[i][path - 1];
    }

    return count;
}

int main(){

    int n,k;
    while(scanf("%d %d",&n,&k), n != 0 && k != 0) {

        int sequence[n];

        for (int i = 0; i < n; i++) {
            scanf("%d", &sequence[i]);
        }

        long long count = count_sequences(sequence, n, k);

        printf("%lld\n", count);
    }
}

On my computer, with -Wall and -O3, it runs the full dataset in 0.01 seconds.

\$\endgroup\$
  • \$\begingroup\$ I think I agree that the solution should be \$O(n^3)\$. After your comment I realized that the sequences could be noncontiguous. So then after rethinking, I came up with a solution that iterated through the sequence (loop 1), and for each element searched for every greater element to its right (loop 2), and for every element found, it updated a memoized list that was of size n (loop 3). It's probably why the problem has n = 100, so that an \$O(n^3)\$ algorithm takes 1000000 iterations which is doable. \$\endgroup\$ – JS1 Jun 10 '15 at 19:58
  • \$\begingroup\$ I wrote my own program and it came out almost identical to your program. The only differences: long long pathcounts[size][path]; memset(pathcounts, 0, sizeof(pathcounts)); for (int k = path-2; k >= 0; k--) { Essentially, in the third loop, you don't have to iterate the whole size, just up to the requested path length. \$\endgroup\$ – JS1 Jun 10 '15 at 20:48
2
\$\begingroup\$

Don't repeat the same work

Ignoring the possibility of rewriting the algorithm for the moment, let's look at this section of code:

    int i;
    for (i = picked + 1; i < len; i++) {
        if(S[picked] < S[i] && LCISlen < K)
            q += LCIS(S, len, i, LCISlen + 1, K);
        else if(S[picked] < S[i] && LCISlen == K)
            q++;
    }

Consider this revised version:

    if (LCISlen < K) {
        for (int i = picked + 1; i < len; i++) {
            if (S[picked] < S[i]) {
                q += LCIS(S, len, i, LCISlen + 1, K);
            }
        }
    } else if (LCISlen == K) {
        for (int i = picked + 1; i < len; i++) {
            if (S[picked] < S[i]) {
                q++;
            }
        }
    }

Note that the original checked LCISlen against K on every loop iteration even though they are constant in the loop. This version checks before entering the loop.

In many cases, this won't matter, so you'll favor the original code for readability. But it is a performance improvement that you can make when performance is a known issue and you are doing this frequently.

Don't repeat the same work 2

    if(memoization[picked][LCISlen])
        return memoization[picked][LCISlen];

Note that 0 is a valid value. The problem is that if the answer is 0, you'll recalculate it every time. Thus making 0 the default is imperfect. Instead make an invalid value the default. Then you can do something like

    if (memoization[picked][LCISlen] >= 0) {
        return memoization[picked][LCISlen];
    }

And the initialization:

        memset(memoization,0,sizeof memoization);

would change to

        memset(memoization, -1, sizeof memoization);

Now the code will remember valid 0 values that it calculates.

This is actually a big deal for some inputs. For example, a long decreasing sequence. I don't have a local C compiler so it would be difficult for me to check, but this might well make a noticeable difference in performance on its own.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy