# UVa 515

## Summary

A sequence of integers ${\displaystyle (x_{1},x_{2},\dots ,x_{n})}$ must satisfy a set of given constraints of the form: ${\displaystyle \sum _{j=s_{i}}^{s_{i}+n_{i}}x_{j}R_{i}k_{i}}$ (where ${\displaystyle 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 ${\displaystyle S(k)=\sum _{i=1}^{k}x_{i}}$, ${\displaystyle S(0)=0}$.

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

Furthermore, it's clear that the sequence ${\displaystyle (x_{1},x_{2},\dots ,x_{n})}$ exists if and only if a sequence of integers ${\displaystyle (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 ${\displaystyle a is equivalent to ${\displaystyle a\leq b-1}$ in integers.

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

We are left with a system of equations of the form: ${\displaystyle S(a_{i})-S(b_{i})\leq c_{i}}$, where all ${\displaystyle a_{i},b_{i},c_{i}}$ are integers, and ${\displaystyle 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 ${\displaystyle n}$, and each constraint corresponds to an edge from vertex ${\displaystyle b_{i}}$ to vertex ${\displaystyle a_{i}}$ of weight ${\displaystyle c_{i}}$. Also, the graph has a special vertex ${\displaystyle s}$, and edges of weight 0 from ${\displaystyle 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 ${\displaystyle 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.