# UVa 515

## 515 - King[edit]

## Summary[edit]

A sequence of integers must satisfy a set of given constraints of the form: (where is one of the relations: <, >), for i=1..m.

The question is: does such a sequence exist?

## Explanation[edit]

First of all, simply the constraints. Consider a function , .

With this function, the constraints can be rewritten as: .

Furthermore, it's clear that the sequence exists if and only if a sequence of integers , satisfying the constraints in the above form exists.

The next step is to get rid of the strict inequalities. A contraint is equivalent to in integers.

Similarly, is the same thing as , or alternatively .

We are left with a system of equations of the form: , where all are integers, and .

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 , and each
constraint corresponds to an edge from vertex to
vertex of weight . Also, the graph has
a special vertex , and edges of weight 0 from
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 are integers.

## Implementation[edit]

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[edit]

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

## Output[edit]

lamentable kingdom successful conspiracy

## References[edit]

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