# UVa 515

## Summary

A sequence of integers $(x_{1},x_{2},\dots ,x_{n})$ must satisfy a set of given constraints of the form: $\sum _{{j=s_{i}}}^{{s_{i}+n_{i}}}x_{j}R_{i}k_{i}$ (where $R_{i}$ is one of the relations: <, >), for i=1..m.

The question is: does such a sequence exist?

## Explanation

First of all, simply the constraints. Consider a function $S(k)=\sum _{{i=1}}^{k}x_{i}$, $S(0)=0$.

With this function, the constraints can be rewritten as: $[S(s_{i}+n_{i})-S(s_{i}-1)]R_{i}k_{i}$.

Furthermore, it's clear that the sequence $(x_{1},x_{2},\dots ,x_{n})$ exists if and only if a sequence of integers $(S(1),S(2),\dots ,S(n))$, satisfying the constraints in the above form exists.

The next step is to get rid of the strict inequalities. A contraint $a is equivalent to $a\leq b-1$ in integers.

Similarly, $a>b$ is the same thing as $a\geq b+1$, or alternatively $-a\leq -b-1$.

We are left with a system of equations of the form: $S(a_{i})-S(b_{i})\leq c_{i}$, where all $a_{i},b_{i},c_{i}$ are integers, and $0\leq a_{i},b_{i}\leq n$.

A system like this one is known as a system of difference constraints. In order to solve it, first construct a constraint graph, whose vertices are labelled with numbers from 0 to $n$, and each constraint corresponds to an edge from vertex $b_{i}$ to vertex $a_{i}$ of weight $c_{i}$. Also, the graph has a special vertex $s$, and edges of weight 0 from $s$ to every other vertex.

It is known that a system of difference constrains has a solution in integers, if and only if the corresponding constraint graph has no negative cycles, and all $c_{i}$ are integers.

## Implementation

A compact implementation of the above idea follows. It uses Bellman-Ford algorithm to detect negative cycles.

#include <stdio.h>

int X[1024], Y[1024], Z[1024], D[1024], M, m, n, x, y, z, i; char s[8];
void E(int x, int y, int z) { X[M]=x; Y[M]=y; Z[M++]=z; }

int main() {
while (scanf("%d %d",&n,&m)==2 && n>0) {
for (n+=2, M=0; m-- && scanf("%d %d %s %d", &x,&y,s,&z)==4;)
s[0]=='g' ? E(x+y+1,x,-z-1) : E(x,x+y+1,z-1);
for (i=1; i<n; i++) E(0,i,0);
for (D[0]=i=x=0; i<n; i++) D[i]=1<<30;
do for(i=z=0; i<M; i++) if (D[Y[i]]>D[X[i]]+Z[i]) z++, D[Y[i]]=D[X[i]]+Z[i]; while (z && x++<n);
printf(z ? "successful conspiracy\n" : "lamentable kingdom\n");
}
return 0;
}


## Input

4 2
1 2 gt 0
2 2 lt 2
1 2
1 0 gt 0
1 0 lt 0
0

## Output

lamentable kingdom
successful conspiracy

## References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 24.4: Difference constraints and shortest paths.