UVa 515

From Algorithmist
Jump to: navigation, search

515 - King[edit]


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?


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


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;


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


lamentable kingdom
successful conspiracy


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