SRM 524: LongestSequence, finally!

Oh finally.

What we have is a set of constraints { c[1], c[2], ... c[N] } . If c[i] is negative then the sum of each (-c[i] ) consecutive elements for a sequence must be negative. And if c[i] is positive then the sum of every group of c[i] consecutive elements in the sequence must be positive.

Return the largest sequence possible of real numbers that can follow those rules, or -1 if it is infinite.

a) When infinite?
Well, if every condition requires the sums to be negative or every condition requires them to be positive, then we can have a sequence of infinite positive (or negative) numbers and fulfill the condition. We should assume that this is not only sufficient but also necessary, perhaps something more formal is needed.

b) If a length is possible, then smaller lengths are possible and viceversa
Let us say a sequence of length Y exists, then sequences of length X where (X < Y) also exist (just remove the extra numbers). If on the other hand, a sequence of length Y does not exist, then it is also impossible to have sequences of length Z where (Z > Y), because they require the first Y elements to follow the condition.

This means that we can use binary search in the number of elements in order to find the maximum possible number of elements.

C) Given the number of elements, formalize
Given t, the number of elements that we want to guess if it is possible or not. Is it possible?

It helps to write each constraint as an inequation.

For example, if a constraint is -2, it means that:

x1 + x2 < 0
x2 + x3 < 0
x3 + x4 < 0
(and so and so)
x_t-1 + x_t < 0

If we also have a constraint 4. Then we also need to fulfill:
x1 + x2 + x3 + x4 > 0
x2 + x3 + x4 + x5 > 0
...
x_t-3 + x_t-2 + x_t-1 + x_t > 0
--
That is as far as I got during the match when solving the problem. Then I read some confusing bits of help during the chat. Like 'use accumulations'. After putting some thought, I finally figured it out, only 2 hours after the match:

D) And the Aha! time
The trick is to consider the accumulated sums of the elements instead of x1, x2, ... .

For example:

S₀ = 0. (Sum of the first 0 elements).
S₁ = x1.
S₂ = x1 + x2 + x3.
...

Which does not sound very useful, except that each of the left sides of the inequations we previously used can be represented as a subtraction of two accumulated sums. For example, x1+x2+x3+x4 is clearly S4. However, less clearly : x2 + x3 + x4 is (S4 - S1).

So, in fact, the inequations in the {-2, 4} example are:
S2 - S0 < 0
S3 - S1 < 0
S4 - S1 < 0
...
S_t - S_t-2 < 0

And:

S4 - S0 > 0
S5 - S1 > 0
S6 - S2 > 0
...
S_t - S_t-4 > 0

Finally, the trick is that the inequations will become:

S2 < S0
S3 < S1
S4 < S2
...
S_t < S_t-2

And:

S4 > S0
S5 > S1
S6 > S2
...
S_t > S_t-4

This system of inequations will have a solution if and only there is never a transitive cycle. For example. S0 > S1 , S1 > S0 would cause a cycle and make it impossible.

However, you will have to note that we need a decent upper bound for the binary search, else we would be doing too many operations or using too much memory when detecting the cycles. In fact, the result should not be larger than 2000. But you can use 100000 as an upper bound and the cycle finding shall still work.

struct LongestSequence 
{ 
    vector<int> G[2002]; 
    int visited[2002]; 
    bool cycles; 
    void dfs(int x) { 
        if (visited[x] == 0) { 
            visited[x] = 2; 
            for (int j=0; j<G[x].size(); j++) { 
                dfs(G[x][j]); 
            } 
            visited[x] = 1; 
        } else if (visited[x] == 2) { 
            //cycle! 
            cycles = true; 
        } 
    } 
 
    bool isItEvenPossible(int t, const vector<int> & C) 
    { 
        int n = C.size(); 
        for (int i=0; i<=t; i++) { 
            visited[i] = 0; 
            G[i].resize(0); 
        } 
         
        // build the graph: 
        for (int i=0; i<n; i++) { 
            int a = abs(C[i]); 
            for (int j=0; j+a <= t; j++) { 
                if (C[i] > 0) { 
                    // S[j+a] - S[j] > 0 
                    // S[j+a] > S[j] 
                    G[j].push_back(j+a); 
                } else { 
                    // S[j+a] - S[j] < 0 
                    // S[j+a] < S[j] 
                    G[j+a].push_back(j); 
                } 
            } 
        } 
        // From previous loop note that 
        // Each node has degree of at most n.         
        cycles = false; 
        for (int i=0; i<=t; i++) { 
            dfs(i); 
        } 
        return ! cycles; 
    } 
 
    int maxLength(vector <int> C) 
    { 
        int n = C.size(); 
        bool allneg = true; 
        bool allpos = true; 
        for (int i=0; i<n; i++) { 
            allneg &= (C[i] < 0); 
            allpos &= (C[i] > 0); 
        } 
        // all negative or all positive, infinite solution is possible: 
        if (allneg || allpos) { 
            return -1; 
        } 
        // Binary search for the length of the sequence 
        // We initially know that isItEvenPossible(lo ) is true and 
        // isItEvenPossible(hi) is false 
        int lo = 0; 
        int hi = 2001; 
        while (lo + 1 < hi) { 
            int ha = hi - (hi - lo) / 2; 
            if (isItEvenPossible(ha, C) ) { 
                lo = ha; 
            } else { 
                hi = ha; 
            } 
        } 
        return lo; 
    } 
};