UVa 515

From Algorithmist
Jump to navigation Jump to search

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.