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
```

## No comments :

Post a Comment