SPOJ 5732 - PARADOX - Paradox

A paradox is a statement or group of statements that leads to a contradiction. Consider the following two statements.

"The statement below is false."
"The statement above is true."

If we assume that 1st statement is true then according to 1st statement the 2nd statement is false. Since the 2nd statement is false and it says that 1st statement is true, 1st statement must be false which is a contradiction. If we assume that 1st statement is false then the 2nd statement must be true (since 1st statement says 2nd statement is false). Then according to 2nd statement 1st statement must be true which is a contradiction. Thus the statement cannot be classified as true or false. This is a paradox.

Given N statements of the form "Statement X is true/false", 1<=X<=N, your task is to find if these set of statements are paradoxical or not. A set of statements is paradoxical if one or more statements cannot be classified as true or false.

Input

Multiple test cases. Each test cases begins with an integer N representing the number of statements. 1<=N<=100. Then follow N lines, representing N statements in the order 1,2,3, ...,N. Each line contains an integer X and a string S separated by a space. 1<=X<=N. S is either "true" or "false" (quotes for clarity), which means the statement is "Statement X is S". N=0 indicates the end of testcases and should not be processed. There are atmost 10000 testcases.

Output

For each test case print "PARADOX" if the set of statements are paradoxical, else print "NOT PARADOX", in a separate line.

Example

plaintext

Input:
2
2 false
1 true
2
2 false
1 false
0

Output:
PARADOX
NOT PARADOX

Solution

It is a simple graphic drawing problem.

First, define graph $G(N, E)$ :

For each $Statement(i, x, s)$ , there two nodes in node set $N$ :

$True(i) \in N$ : represents $Statement(i)$ is $true$ .
$False(i) \in N$ : represents $Statement(i)$ is $false$ .

As for the edge set $E$ :

if $s = True$ :

$Edge(True(i) \rightarrow True(x)) \in E$
$Edge(False(i) \rightarrow False(x)) \in E$

if $s = False$ :

$Edge(True(i) \rightarrow False(x)) \in E$
$Edge(False(i) \rightarrow True(x)) \in E$

Now, the problem is equal to verify if each $True(i)$ and $False(i)$ are in the same directed component.

Source Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// #define DEBUG

#define TRUE "true"
#define FALSE "false"

#define PARADOX "PARADOX"
#define NOT_PARADOX "NOT PARADOX"

#define MAX_N 100
#define MAX_S 10

#define NO_COLOR -1

#define true_position(x) ((x - 1) << 1)
#define false_position(x) (((x - 1) << 1) | 1)

struct edge {

  struct edge *next;
  
  int dest;
};

struct edge *new_edge(int dest, struct edge *next) {

  struct edge *edge = (struct edge*)malloc(sizeof(struct edge));

  edge->next = next;
  edge->dest = dest;

  return edge;
}

struct edge *link[MAX_N * 2];

int color[MAX_N * 2];

void try_draw(int x, int target_color) {

  struct edge *ptr;

  if (NO_COLOR == color[x]) {

    color[x] = target_color;

    #ifdef DEBUG
    printf("draw %d = %d\n", x, target_color);
    #endif

    for (ptr = link[x]; ptr != NULL; ptr = ptr->next) {

      try_draw(ptr->dest, target_color);
    }
  }
}

int main(int argc, char **argv) {

  int n, x, i, paradox;
  char s[MAX_S];

  for(;;) {

    scanf("%d", &n);

    if (0 == n) {
      break;
    }

    for (i = 0; i < (n << 1); i++) {

      link[i] = NULL;
      color[i] = -1;
    }

    for (i = 1; i <= n; i++) {
      scanf("%d%s", &x, s);

      if (0 == strcmp(s, TRUE)) {

        // TRUE(i) -> TRUE(x)
        link[true_position(i)] = new_edge(true_position(x), link[true_position(i)]);

        #ifdef DEBUG
        printf("link %d -> %d\n", true_position(i), true_position(x));
        #endif
 
        // FALSE(i) -> FALSE(x)
        link[false_position(i)] = new_edge(false_position(x), link[false_position(i)]); 

        #ifdef DEBUG        
        printf("link %d -> %d\n", false_position(i), false_position(x));
        #endif
      } else {

        // TRUE(i) -> FALSE(x)
        link[true_position(i)] = new_edge(false_position(x), link[true_position(i)]);
        
        #ifdef DEBUG        
        printf("link %d -> %d\n", true_position(i), false_position(x));
        #endif

        // FALSE(i) -> TRUE(X)
        link[false_position(i)] = new_edge(true_position(x), link[false_position(i)]);
        
        #ifdef DEBUG        
        printf("link %d -> %d\n", false_position(i), true_position(x));
        #endif
      }
    }

    for (paradox = 0, i = 1; i <= n; i++) {

      try_draw(true_position(i), true_position(i));
      try_draw(false_position(i), false_position(i));

      if (color[true_position(i)] == color[false_position(i)]) {

        paradox = 1;
        break;
      }
    }

    printf("%s\n", paradox ? PARADOX : NOT_PARADOX);
  }

  return 0;
}