Match summary

It was a quite a match. The money prizes attracted a sizable amount of coders and stakes were high. The problem setters were nV and rng_58 who offered us a very challenging match in both divisions.

The division 1 250 and division 2 500 was the first sight of things to come. It did not only require analysis but had its implementation corner cases that allowed plenty of successful challenges. In division 1, around 300 coders solved it correctly. Division 2 is a world of extremes and this time, only 22 coders solved it correctly. Proving it to often be more than enough to win the first place in the room.

Anyone willing to acquire money prizes would know that just the easy problem was not going to be enough. The division 1 550 presented itself to be quite an obstacle. Although conceptually a typical dynamic programming problem. It appears that it was not close easy to notice what to do in order to reduce the degree of the polynomial time complexity. Only 46 coders solved this problem correctly. Even WJMZBMR, the top scorer, needed 21 minutes to solve it.

Most division 2 coders were busy with the medium problem, but some were able to solve the 1000-points problem. It was a interesting number theory problem that required quite a few observations. Solving this problem was the ticked to top 12. ibra combined being one of the few coders to solve all 3 problems, a fruitful challenge phase and a decent score in 1000 to earn the first division place. eatmore got second with a faster 1000 and BiliBili third place.

The top names, not content with being the few to solve div1 550, also tried the div1 950 out - The one problem contributed by rng_58. One of those problems that need both theoretical knowledge and tons of creativity and intuition. Usual suspects: ACRush, Petr, UdH-WiNgeR, marek.cygan and lyrically solved this problem.

Petr got the first place thanks to consistent performance in all three problems and 4 successful challenges. ACrush's top score for the 950 points problem earned him the second place. 6 successful challenges, allowed kalinov to get the third place.

The Problems

Value	250
Submission Rate	758 / 1074 (70.58%)
Success Rate	703 / 758 (92.74%)
High Score	BrainDeveloper for 249.52 points (1 mins 15 secs)
Average Score	180.86 (for 703 correct submissions)

It is possible to simply iterate through all triples (r, g, b) with the new color components. Then verify that the conditions are followed correctly, you must verify that the maximum distance between r and startR is not more than d2. Do not forget that at least one color has to differ by at least d1 units.

This naive algorithm works because there are O(maxR*maxG*maxB) different triples 100 x 100 x 100 = 1000000 is fast enough for TopCoder's servers.

Alternative solutions and additional comments.

<PLACE YOUR COMMENTS HERE>

Value	500
Submission Rate	313 / 1074 (29.14%)
Success Rate	21 / 313 (6.71%)
High Score	abcsampson for 387.51 points (16 mins 19 secs)
Average Score	259.35 (for 21 correct submissions)

Value	250
Submission Rate	804 / 880 (91.36%)
Success Rate	300 / 804 (37.31%)
High Score	peter50216 for 240.69 points (5 mins 37 secs)
Average Score	163.61 (for 300 correct submissions)

It is the first element that matters

Let me start by pointing out how the first element will always determine the whole sequence (assuming there are valid sequences that exist). Simply note that once a₀ is fixed, then a₁ can be found through an equation that depends on op₀, then a₂, etc. Thus we just need to count the number of values for a₀ that yield a valid sequence.

A valid sequence, since the only operators are addition and subtraction, then the only issue that makes some sequences invalid is the condition from the statement that all integers a_i were positive.

Bounds

At first, there is one only thing we know about a₀. It has to be positive. Thus we have (a₀ > 0). 0 becomes a lower bound for a₀.

Let us move on to a₁. There are two possible equations depending if the first operator is + or -

1) a0 + a1 = b0   ->    a1 = b0 - a0
2) a0 - a1 = b0   ->    a1 = a0 - b0

Let us assume the first operator was +. Besides of the equation, there is also another condition: a₁ must be positive. This will take us to:

     a1 > 0 
b0 - a0 > 0
     a0 < b0

In this situation, b₀ has become an upper bound for a₀.

If we instead assume that the operator was: "-"

     a1 > 0 
a0 - b0 > 0
     a0 > b0

Now, b₀ is a lower bound for a₀.

Let us assume the second operator is +, then we have the following equation and in-equation:

     a2 > 0

a1 + a2 = b1
a2 = b1 - a1

b1 - a1 > 0

We do remember the value of a₁:

b1 - (a0 - b0) > 0
            a0 < b1 + b0

And we have discovered a new upper bound for a₀

Each value a_i will imply either a lower bound or an upper bound for a₀, provided we first solve the equation to find a_i and then the in-equation to find the bound. A valid a₀ is one that obeys all of these bounds. It must be greater than the maximum lower bound we find and smaller than the minimum upper bound. If those minimum and maximum make an empty set (ie: the lower bound is higher than the upper bound), there are no solutions and the result is 0. If no upper bounds are found (You can count on the (a0 > 0) lower bound to exist) then there are infinite starting values and the result is -1. Else, the result is min(upperBound) - max(lowerBound) - 1.

Solving the equations and finding all the bounds

For each i, we need to find an equation for a_i that should be only in terms of constants and a_0.

The main problem is that each initial equation for a_i is initially represented in terms of a_i-1 instead of a₀. However, we can assume when solving each a_i that a_i-1 has already been solved.

Let us say that the previous value is :

ai = s * a0 + t

Two parameters s and t will be enough because all equations are linear. Then we need to find new values (s,t) for a_i+1.

Case 1) The operator was "+":

ai + ai+1 = Bi
(s * a0 + t) + ai+1 = Bi
ai+1 = Bi - (s * a0 + t)
ai+1 = Bi -  s * a0 - t
ai+1 = -s * a0  + (Bi  - t)

The new values of (s',t') would be: (-s, B_i - t ).

Case 2) The operator was "-":

ai - ai+1 = Bi
(s * a0 + t) - ai+1 = Bi
ai+1 = s * a0 + (t - Bi)

The new values of (s',t') are: (s, t - B_i). Note that s can only be 1 or -1. At first we have a₀ = s * a₀ + t with (s = 1, t = 0). After that, only the sign of s changes.

After we found s and t for each i, we can use the in-equation:

ai > 0
s * a0 + t > 0

s can be negative or not, that would change the result. If s is positive:

a0 > -t

If in the other case, s is negative:

a0 <  t

Either way, a new lower or upper bound is found and we can implement the code:

Code

public int getCount(int[] B, String operators)
{
    int n = B.length;
    int s = 1;
    long t = 0;
    final long INF = Long.MAX_VALUE;
    long lowBound = 0;
    long upperBound = INF;
    for (int i=0; i<=n; i++) {
        // value of the last number is
        // a0*s + t  > 0
        // a0*s > -t
        if (s == -1) {
            // -a0 > -t
            // a0 < t
            upperBound = Math.min(upperBound, t);
        } else {
            // a0 > -t
            lowBound = Math.max(lowBound, -t);
        }
        
        if (i==n) {
            break;
        }
        if ( operators.charAt(i) == '-') {
            //new number is:
            //  B[i]   = (a0*s + t) - A[i+1]
            //  A[i+1] = (a0*s + t - B[i])
            t -= B[i];
        } else {
            //new number is:
            //  B[i]   = (a0*s + t) + A[i+1]
            //  A[i+1] = B[i] - (a0*s + t)
            //  A[i+1] = B[i] - a0*s - t
            s *= -1;
            t = -t + B[i];
        }
        
                    
    }
    if (upperBound == INF) {
        return -1;
    }
    if (upperBound <= lowBound) {
        return 0;
    }
    return (int)( upperBound - lowBound - 1);
}

Alternative solutions and additional comments.

<PLACE YOUR COMMENTS HERE>

Value	1000
Submission Rate	40 / 1074 (3.72%)
Success Rate	12 / 40 (30.00%)
High Score	Gripleaf for 902.70 points (9 mins 32 secs)
Average Score	656.24 (for 12 correct submissions)

Reduce the fraction

The fraction in the input is not necessarily reduced. Since the result is the same for 2/4 as 1/2, it is better to just reduce the fraction. Grab the Greatest common divisor of p and q, and divide each by it.

This will let us assume that p and q are pair-wise coprime - do not have any prime factor in common.

The opposite

This problem asks us to find the number of bases in which the fraction is infinite (cyclic). In certain problems that ask you to count the number of X from a range such that Condition(X) is true, it may be better to actually count the X such that Condition(X) is false and subtract them from the range to find the initial request. In this case, we will find a condition for a base to yield a finite representation of P/Q.

Let us find the condition for P/Q to be finite. Let us first inspect cases in our familiar base 10. What makes 1/2 finite? It is because 10 is a multiple of 2. 1/4 is finite because 100 is a multiple of 4. 37/5 is finite, because 370 is a multiple of 5. 1/1 is finite because 1 is a multiple of 1. In other words, there exists a integer i such that: (P * 10ⁱ) is a multiple of Q (i could be 0 or very large).

Extending the definition to any base X. We should count the number of X such that there exists a integer i such that: (P * Xⁱ is a multiple of Q)

Congruences

This makes us enter the realms of modular arithmetic and congruences. Indeed we need to count the number of solutions to the following congruence:

P * Xi = 0 (mod Q).

Where X is between A and B, inclusive.

In reality, we already know that P and Q are pair-wise coprime. This means that in order for a product between P and another number to be a multiple of Q, the other number must be a multiple of Q. Therefore:

Xi = 0 (mod Q).

Our condition has become to count the X such that raising them to any power yields a multiple of Q.

A necessary condition

A necessary condition for Xⁱ to be a multiple of Q is that X must be a multiple of each of the prime factors of Q. Since (Xⁱ) is a power of X, no prime factor from another number can appear. For example, if Q was 24 = 2*2*2*3, then X has to be a multiple of 6. Assume that X was not a multiple of 6, it does not matter to which high power we raise 4 to, it will never be a multiple of 3 and thus it will never be a multiple of 24.

And the condition is sufficient

Assume X is a multiple of each of the prime factors of Q. Then there is always an exponent i high enough such that Xⁱ is a multiple of Q. For example, if Q = 24 = 2*2*2*3 and X = 2*3, then we use i = 3 and we will have: (2*3)*(2*3)*(2*3) = 2*2*2 * 3 * (3*3) = Q * 9. i is merely the maximum exponent among the prime factors of Q.

The minimum common multiple of all the prime factors of Q, is their product. So we will factorize Q and find that its factorization is: p1⁴ * p2² * p3⁸. Then Y= (p1 * p2 * p3) is the minimum common multiple of the prime factors of Q. A number X is a multiple of each of the prime factors of Q if and only if it is a multiple of Y.

Let us make a function countMultiples(B, Y) that returns the number of multiples between 0 and B-1 of Y. This is equal to (B-1)/Y. The result between A and B is: countMultiples(B+1,Y) - countMultiples(A,Y) = B/Y - (A-1)/Y. Which yields the number of X that yield a finite representation of P/Q. Which can be then subtracted from B-A-1 to know the number of bases with infinite representations.

Code

long gcd(long a, long b) {
    while (b != 0) {
        long c = b;
        b = a%b;
        a = c;
    }
    return a;
}
public long getNumberOfGoodBases(long P, long Q, long A, long B)
{
    //Reduce the fraction:
    long g = gcd(P,Q);
    P /= g;
    Q /= g;
    
    // P * X^e = 0 mod Q
    //X^e must not divide Q?

    //count Xs such that X^e divides Q and X<B:
    // X is a multiple of Y, where Y is the product of all
    // prime factors of Q.
    long Y = 1;
    for (int p=2; p<=Q/p; p++) { //Factorization in O(sqrt(Q))
        if (Q%p == 0) {
            Y *= p;
            while (Q%p == 0) {
                Q/=p;
            }
        }
    }
    Y *= Q;

    
    long finite = B/Y - (A-1)/Y;
    
    return (B+1-A) - finite;
}

Alternative solutions and additional comments.

<PLACE YOUR COMMENTS HERE>

Value	550
Submission Rate	83 / 880 (9.43%)
Success Rate	46 / 83 (55.42%)
High Score	WJMZBMR for 375.32 points (21 mins 37 secs)
Average Score	263.98 (for 46 correct submissions)

The solution uses dynamic programming. Of course, the complication lied in how to use dynamic programming in a way that did not use a very high polynomial degree in the time and/or memory complexity. Let us start with the straightforward dynamic programming solution that was too slow.

Easy dynamic programming, too slow.

The idea is to simply use a recurrence that remembers a) The number of planks with a color already assigned. and b) The color triplet of the last assigned plank. And calculates the probability the remaining colors are picked in a way that the fence is ugly.

The recurrence is as follows: F(i, r, g, b). i specifies the number of planks which already had a color assigned. And (r,g,b) the colors of the last plank. F(1, startR, startG, startB) would yield the overall probability that the fence is ugly. The base case is when F(N, r,g,b) (N == i), this means that all the planks have been colored. Therefore, (r,g,b) is equal to the colors of the last plank. We must just verify if (r,g,b) makes a non-beautiful to (startR, startG, startB). If it does, then the fence is ugly with probability 1.0, else the probability is 0.0.

What is left is to calculate the transition between a state F(i, r,g,b) to others. For each (i,r,g,b), count all the new values for the colors (nr,ng,nb) such that the new values make a beautiful transition to (r,g,b). Then, for each , valid transition, find F(i+1, nr,ng,nb). The total sum of these probabilities divided by the total number of beautiful/valid transitions is the result for F(i, r,g,b).

The issue, of course, is that even with dynamic programming, there are O(N * maxR * maxG * maxB) states, and each needs to iterate through O(maxR * maxG * maxB) states. This would be too slow.

Negation

What we need is a way to somehow save all the computational work that is done at each of our O(N * maxR * maxG * maxB) states. The first idea I would suggest is to take a look to the condition that enables a transition to be beautiful.

• Each color component of the new color tuple must be within d2 units of the previous value.
• At least one color component of the new color tuple must have a difference with the previous value of at least d1. The negation of this property would be for each of the components to be within (d1-1) units of the previous value.
• Note that the set of tuples such that all components are within (d1-1) units of the original value is a subset of the tuples with all components within (d2) units.

Note the similarity between the first condition and the negation of the second condition. Imagine we had a way to calculate two things: sumWithin(r,g,b, d) and countWithin(r,g,b, d). sumWithin(r,g,b, d) would return the total sum among all F(i+1, nr,ng,nb) such that nr, ng and nb are within d units of r, g and b, respectively. Similarly countWithin(r,g,b, d) counts the total number of pairs (nr, ng, nb) such that nr, ng and nb are d units of r, g and b, respectively. Wouldn't the total result of F(i, r,g,b) be: (sumWithin(r,g,b, d2) - sumWithin(r,g,b, d1-1)) / (countWithin(r,g,b, d2) - countWithin(r,g,b, d1-1))?

The modification helps us because we are now only interested in how to find the total sum of F(i+1, nr,ng,nb) such that : (nr - d <= r <= nr + d), (ng - d <= g <= ng + d) and (nb - d <= b <= nb + d). If we find a way to solve this query in O(1) time, we will be able to apply the query to the different cases ( d2, d1-1 ) and find the sum of the probabilities in beautiful transitions needed to calculate F(i, r,g,b).

It may initially look like attempting to fit too many operations inside a small package. But it is actually a doable task. Perhaps it would be better to first handle an easier version of the question.

Only two color components

Let us for a minute move on to an easier problem with less dimensions. There are now only two color components: red and green. We would like to find the sum between all f(i+1, nr,ng) such that: (nr - d <= r <= nr + d) and (ng - d <= g <= ng + d) in O(1). Do not forget that we also need the total count of values.

The solution to this problem is not uncommon. First of all, let us consider that the colors have bounds of their own (0 and maxR or maxG). Thus let us do the following variable assignments:

r1 = max(r - d,0);
g1 = max(g - d,0);
r2 = min(r + d + 1, maxR);
g2 = min(g + d + 1, maxG);

The question is to find the sum between F(i+1, nr,ng) such that: (r1 <= nr < r2) and (g1 <= ng < g2) this will ensure the bounds are considered. The count of the values is actually easily calculated as : (r2 - r1)*(g2 - g1).

In order to find the sum, simply consider F(i+1) as a table of dimensions maxR x maxG:

We want to find the sum of cells inside the rectangle in green. An easy way that combines dynamic programming with the Inclusion-exclusion principle is to first calculate a function acum2D[r][g] that returns the total sum of values such that: (nr < r) and (ng < g). Then you can see that the total colored area is equal to acum2D[r2][g2] but we would like to subtract the rectangles colored other than green. From the inclusion-exclusion principle, you can confirm that:

Sum (r1 <= r < r2; g1 <= g < g2) = acum2D[r2][g2]
                                 - acum2D[r1][g2] - acum2D[r2][g1]
                                 + acum2D[r1][g1]

Finally, in order to calculate acum2D quickly, we can use the same principle:

acum2D[r][g] = F(i+1, r-1, g-1)
             + acum2D[r-1][g] + acum2D[r][g-1]
             - acum2D[r-1][g-1]

3 components

It may appear that it would not be that easy if a new dimension is added, but it is. Let us add the calculation of b1 and b2 in similar ways to r2,r1,g2 and g1. The space of f(i+1, r,g,b) actually makes a parallelepiped instead of a 2D table, but the same logic will work.

acum3D[r][g][b] = F(i+1, r-1, g-1, b-1)
                + acum3D[r-1][g][b] + acum3D[r][g-1][b] + acum3D[r][g][b-1]
                - acum3D[r-1][g-1][b] - acum3D[r][g-1][b-1] - acum3D[r-1][g][b-1]
                + acum3D[r-1][g-1][b-1]
                
Sum (r1 <= r < r2; g1 <= g < g2; b1 <= b < b2)
            =  acum3D[r2][g2][b2]
             - acum3D[r1][g2][b2] - acum3D[r2][g1][b2] - acum3D[r2][g2][b1]
             + acum3D[r1][g1][b2] + acum3D[r2][g1][b1] + acum3D[r1][g2][b1]
             - acum3D[r1][g1][b1]

Code

And those long formulas are all we needed to solve the problem. The following c++ solution needs 0.5 seconds in Topcoder's servers in its worst case:

double dp[41][50][50][50];
double getProbability(int N, int maxR, int maxG, int maxB,
                             int startR, int startG, int startB, int d1, int d2)
{
    // dp[i][r][g][b]
    //   probability that the final setting is ugly after we picked the
    //   first i planks and the last plank we picked has colors (r,g,b)
    
    //base case: i=N
    for (int r=0; r<maxR; r++) {
        for (int g=0; g<maxG; g++) {
            for (int b=0; b<maxB; b++) {
                int dr = abs(r - startR);
                int dg = abs(g - startG);
                int db = abs(b - startB);
                
                if ( (dr<=d2 && dg<=d2 && db<=d2) &&
                     (dr>=d1 || db>=d1 || dg>=d1) ) {
                   //beautiful:
                    dp[N][r][g][b] = 0.0;
                } else {
                   //ugly
                    dp[N][r][g][b] = 1.0;
                }
            }
        }
    }
    double acum3D[maxR+1][maxG+1][maxB+1];
    memset(acum3D,0,sizeof(acum3D));

    for (int i=N-1; i>=1; i--) {
        // acum3D[r][g][b] returns the sum of :
        //    dp[i][j][k] such that: i<r, j<g, k<b
        for (int r=1; r<=maxR; r++) {
         for (int g=1; g<=maxG; g++) {
          for (int b=1; b<=maxB; b++) {
              acum3D[r][g][b] = dp[i+1][r-1][g-1][b-1]
                              + acum3D[r-1][g][b] + acum3D[r][g-1][b] + acum3D[r][g][b-1]
                              - acum3D[r-1][g-1][b] - acum3D[r][g-1][b-1] - acum3D[r-1][g][b-1]
                              + acum3D[r-1][g-1][b-1];
          }
         }
        }
        
        
        
        for (int r=0; r<maxR; r++) {
         for (int g=0; g<maxG; g++) {
          for (int b=0; b<maxB; b++) {
            double & res = dp[i][r][g][b];
            int r1 = max(r - d2,0);
            int g1 = max(g - d2,0);
            int b1 = max(b - d2,0);
            int r2 = min(r + d2 + 1, maxR);
            int g2 = min(g + d2 + 1, maxG);
            int b2 = min(b + d2 + 1, maxB);
            
            int count = (r2 - r1)*(g2 - g1)*(b2 - b1);
            res = acum3D[r2][g2][b2]
                - acum3D[r1][g2][b2] - acum3D[r2][g1][b2] - acum3D[r2][g2][b1]
                + acum3D[r1][g1][b2] + acum3D[r1][g2][b1] + acum3D[r2][g1][b1]
                - acum3D[r1][g1][b1];
            
            if (d1 != 0) {
                r1 = max(r - d1 + 1,0);
                g1 = max(g - d1 + 1,0);
                b1 = max(b - d1 + 1,0);
                r2 = min(r + d1, maxR);
                g2 = min(g + d1, maxG);
                b2 = min(b + d1, maxB);
                
                count -= (r2 - r1)*(g2 - g1)*(b2 - b1);
                res -= acum3D[r2][g2][b2]
                     - acum3D[r1][g2][b2] - acum3D[r2][g1][b2] - acum3D[r2][g2][b1]
                     + acum3D[r1][g1][b2] + acum3D[r1][g2][b1] + acum3D[r2][g1][b1]
                     - acum3D[r1][g1][b1];
            }

            if (! count) { // We may visit some invalid cases in (maxR,maxG,maxB)
                           // these cases won't affect the final result because
                           // they are unreachable, but without this condition,
                           // nans may appear in the acum3D array.
                res = 1.0;
            } else {
                res /= count;
            }

            
          }
         }
        }
    }
    
    
    return dp[1][startR][startG][startB];
}

Alternative solutions and additional comments.

<PLACE YOUR COMMENTS HERE>

Value	950
Submission Rate	9 / 880 (1.02%)
Success Rate	5 / 9 (55.56%)
High Score	ACRush for 651.66 points (21 mins 24 secs)
Average Score	492.98 (for 5 correct submissions)

Modulo 10 or 2 and 5?

The product of the queries is presented modulo 10. We end up with a series of modular congruences of the form ( A[Qfrom[i]] * A[Qfrom[i]+1] * ... * A[Qto[i]] = output[i] (mod 10) ). One thing about congruence relations is that they tend to be easier when the modulo is a prime number. Specially if multiplication is involved. Would not it be great if the modulo was a prime number instead of 10? There is a good chance it would be easier to solve.

We do know that 10 = 2 * 5, two prime numbers. This is a simple enough of a composite number. Imagine for a second we extracted the conditions modulo 2 and 5 from the original equations. It is as easy as just taking the output of each interval and get the remainder after dividing by 2 or 5, respectively. For example, if one of our congruences says ( A[0] * A[1] * A[2] = 7 (mod 10) ). We could say that there are other two congruences: ( A[0] * A[1] * A[2] = 1 (mod 2) ) and ( A[0] * A[1] * A[2] = 2 (mod 5) ). (Because (7 mod 2 = 1) and (7 mod 5 = 2). If the first congruence is true then both of the other two congruences must also be true.

If we took the modulo 2 and modulo 5 congruences from each congruence generated by the tuples (Qfrom[i], Qto[i], output[i]) and first we found, x - the number of ways to place numbers modulo 2 in N elements using the modulo 2 congruences and then solve separately to find y, the number of ways to place numbers modulo 5 in the N-elements array, the product (x * y) would actually be the solution for the (modulo 10) version.

For example, imagine we found that one of the possible inputs modulo 2 was (1,0,1,1) and one of the possible inputs modulo 5 was (2,3,3,0). We can always combine them up. Ask what number from 0 to 10 is equal to 1 modulo 2 and 2 modulo 5? The result is: 7. Using similar logic for the remaining elements we can find that the combination modulo 10 is: (7, 8, 3, 5).

We can always do this, first solve for modulo 2, then for modulo 5 and finally, combine the results through a single product.

Prime sub-problem

Let us therefore, solve each sub-problem, which is the same exact problem as the original one, with the exception that in one case, 10 is replaced by 2 and in the other, 10 is replaced by 5. Please note that for each version, we modify the output array. From now on, we will refer to the specific prime number that can be 2 or 5 as p.

There are special traits about such a low and simple value like 2 that are useful to solve the problem. But let us instead focus on the general case in which we solve for any prime value. We will after all have to solve for 5, and if the approach we find to work with 5 also works with 2, then that will reduce our work.

Let us first handle those products that return 0 (modulo p):

If output[i] = 0, then we can tell that at least one of the numbers in the interval from Qfrom[i] and Qto[i] must be 0. In the opposite case, output[i] != 0, and it should not be possible to place a 0 in any of the positions between Qfrom[i] and Qto[i]. We will segregate the positions that can be zero from the positions that cannot be zero.

Positions that can be 0

Let us calculate the total number of ways to assign values (0, 1, ... p-1) to all the positions that can be 0. In this case, note the condition possibly introduced by intervals with (output = 0) that requires at least one of the positions inside those intervals to be 0.

Let us solve this with dynamic programming. What is important at every step in a recurrence is to know which of the 0-intervals forces you to place a 0 in a given position, and to know if you are forced to do that, you need to remember the position in which you placed a 0. Let f(N, first0) be the number of valid ways to assign the elements among the first N elements in the array that can be assigned 0 such assuming that first0 is the smallest position >= N that already has a 0. Let us solve F(i, first0), if (i-1) is a position that allows 0, then we have to assign a value to this position. If there is at least one interval with result 0 such that its starting point is (i-1) then this might be our last chance to place a 0 for this interval. We just need to know if we did not place a 0 in the interval yet, this is equivalent to asking (Qto[interval] < first0). Once we know if we are forced to place a 0 or not, we can follow to the next state. If we place a 0, the number of ways will be F(i-1, i-1), because we just placed a new 0 at position (i-1). Else the number of ways is (p-1)*F(i-1, first0), we placed one of the (p-1) available numbers different to 0. If the position is one that does not allow a 0, then we must check if we are forced to place a 0 there, if we are, then there are 0 correct ways to solve the issue. If we are not required to place a 0, the result is F(i-1, first0), because we will not count the number of ways to place a value here yet.

The base case is F(0, first0), there is only 1 way to fill 0 elements - do nothing. The overall number of ways to fill the positions that allow zero is F(N, N). We are adding an imaginary position N in which we placed a 0, since this position will not overlap with any intervals, it is the same as saying that we did not place any 0 yet.

Note that this recurrence alone shall find any inconsistencies between intervals with outputs equal to 0 and those that are not. If the non-zero intervals made it impossible to fill enough zeros, the result of the recurrence will be 0.

Positions that cannot be 0

The following subproblem is the most complicated one. We can assume that intervals with output = 0 have already been taken care of and that the positions that can include 0 are filled in a way that follows the condition of these intervals. We can just ignore the (output=0) intervals from now on.

What we have left is a set of intervals with (output=1). The first question we shall have is how to find any inconsistency between these intervals that makes a solution impossible. Then how to count the number of solutions (considering only cells that cannot have 0 as result, and such all of the cells that belong to the intervals that still remain).

The simplest condition to find an inconsistent setting is when two intervals have identical starting and ending point but different outputs. What about intervals that are completely identical? It is not helpful to keep duplicates, so we shall remove the duplicate interval.

A good second idea is to handle cases in which a interval is a subset of another interval. The general case is not easy to handle, but how about easier variations in which the smaller interval either begins or ends at the same position as the larger interval?

If you already know the result of the product of the first 2 elements of a interval, and you also know the total product of the 4 elements in the interval, then you can modify the larger interval to consider only the elements that do not intersect. In order to find the value of the new interval, you have to use some modular arithmetic. We need to solve the congruence: (a*x = b (mod p)). This is the moment in which it really helps that p is prime, because it will guarantee that there is a result to that congruence. In order to actually solve it, we can even just do brute-force until we find the x (There are only p-1 candidates to try) or we can first find the modular multiplicative inverse of the smaller interval and multiply the larger interval with it to find the new value. (The modular multiplicative inverse can also be found through a single loop through p-1 elements). For example, 2 * 4 = 3 (mod 5).

If we do this process once it will need O(t*t) operations, where t is the number of intervals. We will end with less or as many intervals as the beginning of the process. (Less if we removed any duplicate interval) (Cutting a interval modifies an existing interval). Please note that after cutting a interval, you get a new interval with a new starting or end position. The new intervals may once again be identical to other intervals (new or old) or also be the starting or ending subset of a new or old interval. Thus we can repeat again and again until no more cuts are done. We can be sure that this process will need less than O(t*t) iterations, because two intervals can only be cut together at most once. O(t*t*t*t) is not an issue for the time limit.

The remaining intervals will all be either disjoint or intersect but not have the same ending or starting point. It is not useful to try to cut a pair of intervals that intersect this way, because there are two sides in the larger interval after subtracting the smaller one from it. In reality, we can be certain that this remaining structure will always be consistent and have a number of solutions equal to: (p-1)^{(number of positions) - (number of remaining intervals)}. You may be wondering why.

Let us assume there is only one interval left and it contains 5 positions. We can pick any combination of values (p-1) for the first 4 elements. They will yield some total product q, the remaining value will forcibly be the solution for q * x = [output of the interval] (mod p). This solution always exists (p is prime).

Each of the remaining intervals implies one position which will have a forced value that depends on the other positions in the interval. We can assume this position to be the last one, and it will allow us to show the (p-1)^{(number of positions) - (number of remaining intervals)} formula to be true:

In the image (assume p=5), the green interval contains only one element and its product mus be 4. The red interval contains 2 elements with a product that must be 3. The blue interval contains 3 elements that must also yield 3 as a product. The yellow interval 1 and the black interval 1. (All operations modulo 5). We assume each of the interval's last (rightmost) element to be the 'forced' element, the one that has a value that depends on the interval's previous elements (to the left). Since the last position of two intervals will never be equal, we do not need to worry about overlaps causing incompatible values. We can always fill the remaining non-independent positions (with any combination of numbers from (1 to p-1, inclusive). The dependent positions, marked with an X will be filled automatically in order for each interval to give the required product. In the example, we filled the question marks with 1, 2 and 3. The remaining cells were all found automatically. The green cell is a special case, because it is always 4 as its interval covers a single cell. In order to get the red cell we just find that 1 x 3 = 3 (mod 5). After filling that cell we have that the product inside the blue interval is (3 x 2) x 3 = 3 (mod 5). Later (3 x 3) x 4 = 1 (mod 5) and finally, 4 x 4 = (1 mod 5) for the yellow interval.

final int MOD = 1000000007;

long theInputPrime(int p, int N, int[] Qfrom, int[] Qto, int[] output)
{
    int t = Qfrom.length;
    
    boolean[] cant0 = new boolean[N];
    long res = 1;
    
    for (int i=0; i<t; i++) {
        if (output[i] != 0) {
            for (int j=Qfrom[i]; j<=Qto[i]; j++) {
                cant0[j] = true;
            }
        }
    }
    
    // #1: Elements that can be 0.
    long[][] dp = new long[N+1][N+1];
    //
    // dp[N][first0] : Number of ways to fill the elements that
    // allow0 among the first N elements. Such that the 0-intervals
    // are correct and we can assume that first0 is the position of
    // the first 0 element >= N
    //
    for (int first0=0; first0<=N; first0++) {
        dp[0][first0] = 1;
    }
    for (int i=1; i<=N; i++) {
         for (int first0=i; first0<=N; first0++) {
             dp[i][first0] = 0;
             // Are we forced to place a 0 at (i-1) ? 
             boolean must0 = false;
             for (int j=0; j<t; j++) {
                 if ( (output[j]==0) && (Qfrom[j]==i-1) && (Qto[j] < first0) ) {
                     must0 = true;
                 }
             }
             if (cant0[i-1]) {
                 // Verify it is possible to leave this cell
                 // as non-zero.
                 dp[i][first0] = ( must0? 0 : dp[i-1][first0] );
             } else {
                 // decide what to do with element (i-1)
                 // a) place a 0
                 dp[i][first0] += dp[i-1][i-1];
                 // b) dont place a 0.
                 if (! must0) {
                     dp[i][first0] += (p - 1)*dp[i-1][first0];
                 }
                 dp[i][first0] %= MOD;
             }
         }
    }
    res = ( res * dp[N][N] ) % MOD;

    // Precalculate the modular multiplicative inverse
    int[] inverse = new int[p];
    for (int i=0; i<p; i++) {
        for (int j=0; j<p; j++) {
            if ( (i * j) % p == 1 ) {
                inverse[i] = j;
            }
        }
    }
    // ====================================================
    // The iterative process:
    //
    boolean cut = true;
    boolean[] erased = new boolean[t];
    int[] from = new int[t];
    int[] to   = new int[t];
    for (int i=0; i<t; i++) {
        if (output[i] == 0) {
            erased[i] = true;
        } else {
            from[i] = Qfrom[i];
            to[i]   = Qto[i];
        }
    }
    while( cut ) {
        cut = false;
        for (int i=0; i<t; i++) if (! erased[i]) {
            for (int j=0; j<t; j++) if ( (! erased[j]) && (j!=i) ) {
                if (from[i] == from[j] && to[i] == to[j]) { 
                    // For each pair of identical intervals:
                    if (output[i] == output[j]) {
                        // Same outputs, one is redundant:
                        erased[j] = true;
                    } else {  
                        // Different outputs, inconsistent.
                        System.out.println("Found inconsistency: "+from[i]+" -> "+to[i]);
                        return 0;
                    }
                } else if ( (from[i] == from[j]) && (to[i] < to[j]) ) {
                    // Replace the larger interval with one that is disjoint
                    // with the smaller interval.
                    // [    ]i
                    // [          ]j
                    //cut j
                    from[j] = to[i]+1;
                    output[j] = ( output[j] * inverse[output[i]] ) % p;
                    cut = true;
                } else if ( (to[i] == to[j]) && (from[i] > from[j]) ) {
                    //    [       ]i
                    // [          ]j
                    // cut j
                    to[j] = from[i]-1;
                    output[j] = ( output[j] * inverse[output[i]] ) % p;
                    cut = true;                        
                }
            }
        }
    }
    // Count remaining intervals and cells:
    int non0cells = 0;
    int non0intervals = 0;
    for (int i=0; i<t; i++) {
        if (! erased[i]) {
            non0intervals++;
        }
    }
    for (int i=0; i<N; i++) {
        if (cant0[i]) {
            non0cells++;
        }
    }
    // The number of ways to fill the remaining cells is:
    // (p-1) ^ (non0cells - non0intervals).
    for (int i=1; i<=non0cells - non0intervals; i++) {
        res = (res * (p-1)) % MOD;
    }
    
    return res;
}

int[] outputMod(int[] output, int p)
{
    int[] res = new int[output.length];
    for (int i=0; i<output.length; i++) {
        res[i] = output[i] % p;
    }
    return res;
}

public int theInput(int N, int[] Qfrom, int[] Qto, int[] output)
{
    long x = theInputPrime(2, N, Qfrom, Qto, outputMod(output, 2) );
    long y = theInputPrime(5, N, Qfrom, Qto, outputMod(output, 5) );
    
    return ( int)( (x * y) % MOD );
}

Alternative solutions and additional comments.

<PLACE YOUR COMMENTS HERE>

By vexorian
TopCoder Member