Topcoder SRM 540

Fun problem set. But I spent most of the time solving a problem that was much easier than 550. Instead of solving the real 550.

div1 250: The one with the intervals

All right all right. Let us count the number of correct arrays (a1, a2,... an+1) such that ai opi ai+1 = bi for all i Such that opi are operators (+ or -) and all ai are positive.

Let us say that a1 = x. We have x > 0 as the first condition. If op1 was -, then we would have to solve the equation: b1 = a2 - a1 = a2 - x. Or (a2 = b1 + x). We got a new condition: (b1 + x > 0). Likewise, if the first operator was positive we would have: b1 = a2 + x ; a2 = b1 - x. So the new condition will become b1 - x > 0.

Let us define for each i : ai = s * x + y. Such that s is 1 or -1 (the sign). For each i, you can find the values of s and y by using the values from (i-1) by using the equations. Then you have to use the condition: s * x + y > 0. Depending on the sign of x, this will become either a lower bound for x or an upper bound for x. At the end, you will have plenty of upper and lower bounds (if you do not have any upper bound, there are infinite results) (x must be positive, so the lower bound is at least 1). Pick the minimum upper bound and the maximum lower bound, then use a single subtraction to count the number of ways x can be set.

Implementation can be tricky. I would post my beautiful code I made during the match, but I am in a different computer and TopCoder won't let me CNP my own code.

So here it is:

#include <valarray>
#include <queue>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <cassert>
 
using namespace std;
 
typedef long long int64;
#define long int64
 
 
struct ImportantSequence
{
    int getCount(vector <int> B, string operators)
    {
        int n = B.size();
        int s = 1;
        long y = 0;
        const long INF = numeric_limits<long>::max();
        long lowBound = 1;
        long upperBound = INF;
        for (int i=0; i<=n; i++) {
            // value of the last number is
            // x*s + y  > 0
            // x*s > -y
            if (s == -1) {
                // -x > -y
                // x < y
                upperBound = std::min(upperBound, y);
            } else {
                // x > -y
                lowBound = std::max(lowBound, -y + 1);
            }
            
            if (i==n) {
                break;
            }
            if ( operators[i] == '-') {
                //new number is:
                //  B[i] = (x*s + y) - z
                //    z  = (x*s + y - B[i])
                y -= B[i];
            } else {
                //new number is:
                //  B[i] = (x*s + y) + z
                //   z   = B[i] - (x*s + y)
                //   z   = B[i] - x*s - y
                s *= -1;
                y = -y + B[i];
            }
            
                        
        }
        if (upperBound == INF) {
            return -1;
        }
        if (upperBound <= lowBound) {
            return 0;
        }
        return upperBound - lowBound;
        
    }
};
#undef long

div1 550: The one with the colors

I spent most of the match thinking that colors are independent. As such you can find the probability that each color will be ugly and then combine the 3 probabilities. I spent most of the match baffled as to why I failed the last test cases. From my analysis, I was certain the colors were independent, but examples suggested that was not the case. But I could not find a reason for this... Until, some few minutes before the end, I noticed that while all differences must be at most d2, only one of the differences between color components must be at least d1. Thus the colors are not independent. Yay.