Programming Forums > Application Development > Software Design and Algorithms

Sane · Jul 1st, 2008, 11:45 AM

Attached to this post is the test data for escalator troubles.

Escalator Troubles (Senior)

Escalators was a classic problem in graph theory.

A floor represents a "vertex" (or node), and an escalator represents a "directed edge". All the floors and escalators together form a map, referred to as a "directed graph" (or Digraph).

Given a directed graph, test whether or not every vertex is reachable from every other vertex.

Titanium emerged as the victor for this problem with the only perfect. Considering it was a tough problem, everyone who submitted also did very well.

 C Syntax (Toggle Plain Text) 
/* 
 * SMAC #2
 * titaniumdecoy
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct escalator 
{
	int to_floor;
	struct escalator *next;
} 
escalator_t;
 
void build_escalator(escalator_t **es, int from, int to)
{
	escalator_t *new_es = NULL;
 
	new_es = malloc(sizeof(escalator_t));
	new_es->to_floor = to;
 
	new_es->next = es[from];
	es[from] = new_es;
}
 
void can_reach_all_floors(escalator_t **es, int n, int *visited, int x)
{
	escalator_t *es_ptr = es[x];
 
	while (es_ptr != NULL) {
		if (visited[es_ptr->to_floor] == 0) {
			visited[es_ptr->to_floor] = 1;
			can_reach_all_floors(es, n, visited, es_ptr->to_floor);
		}
		es_ptr = es_ptr->next;
	}
}
 
int main()
{
	int i = 0, j = 0;
	int n = 0, e = 0;
	int from = 0, to = 0;
	escalator_t **es;
	int havoc = 0;
 
	freopen("escalator.in", "r", stdin);
	freopen("escalator.out", "w", stdout);
 
	scanf("%d %d", &n, &e);
 
	es = calloc(sizeof(escalator_t *), n);
 
	for (i = 0; i < e; i++)
	{
		scanf("%d %d", &from, &to);
		build_escalator(es, from - 1, to - 1);
	}
 
	int *visited = calloc(sizeof(int), n);
 
	for (i = 0; i < n; i++) {
		can_reach_all_floors(es, n, visited, i);
 
		for (j = 0; j < n; j++)
			if (visited[j] == 0) {
				havoc = 1;
				goto end;
			}
 
		for (j = 0; j < n; j++)
			visited[j] = 0;
	}
 
end:
	if (havoc)
		printf("Bob is going to get fired!\n");
	else
		printf("Vladimir's plan failed.\n");
 
	return 0;
}
/* 
 * SMAC #2
 * titaniumdecoy
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct escalator 
{
	int to_floor;
	struct escalator *next;
} 
escalator_t;

void build_escalator(escalator_t **es, int from, int to)
{
	escalator_t *new_es = NULL;
	
	new_es = malloc(sizeof(escalator_t));
	new_es->to_floor = to;
	
	new_es->next = es[from];
	es[from] = new_es;
}

void can_reach_all_floors(escalator_t **es, int n, int *visited, int x)
{
	escalator_t *es_ptr = es[x];
	
	while (es_ptr != NULL) {
		if (visited[es_ptr->to_floor] == 0) {
			visited[es_ptr->to_floor] = 1;
			can_reach_all_floors(es, n, visited, es_ptr->to_floor);
		}
		es_ptr = es_ptr->next;
	}
}

int main()
{
	int i = 0, j = 0;
	int n = 0, e = 0;
	int from = 0, to = 0;
	escalator_t **es;
	int havoc = 0;
	
	freopen("escalator.in", "r", stdin);
	freopen("escalator.out", "w", stdout);
	
	scanf("%d %d", &n, &e);
	
	es = calloc(sizeof(escalator_t *), n);
	
	for (i = 0; i < e; i++)
	{
		scanf("%d %d", &from, &to);
		build_escalator(es, from - 1, to - 1);
	}
	
	int *visited = calloc(sizeof(int), n);
	
	for (i = 0; i < n; i++) {
		can_reach_all_floors(es, n, visited, i);
	
		for (j = 0; j < n; j++)
			if (visited[j] == 0) {
				havoc = 1;
				goto end;
			}
		
		for (j = 0; j < n; j++)
			visited[j] = 0;
	}
	
end:
	if (havoc)
		printf("Bob is going to get fired!\n");
	else
		printf("Vladimir's plan failed.\n");
	
	return 0;
}

I have come up with 4 different solutions to this problem.

1 is fast.
1 is very fast.
1 is intuitive.
1 is an easy to code DP algorithm.

All of them run in time since an "n" of 100 is very small. I will start from the simplest and work towards the most difficult solution.

------------------

Solution #1 (Slowest)

This was one of the expected solutions, and is the simplest to understand.

The idea is to take every single pair of vertecies and test whether or not 'a' can reach 'b'.

For example, if n = 3,

(Toggle Plain Text)

(a,b)
-----
(1,2)
(1,3)
(2,1)
(2,3)
(3,1)
(3,2)

For each pair, you start at 'a', and try to find a route to 'b'.

If there's ever a pair that does not work, Bob is getting fired.

If every pair is successfull, Vladimir's plan has failed.

A way to find a route from 'a' to 'b' is by using recursion, with some very similar ideas to the solution from Junior's "Trapped".

You recursively branch off to each possible path (ride every possible escalator from a), and then make sure you don't try the same floor twice. This repeats until you find b, or run out of floors to try.

Marking a floor as visited is done in a "visited" array of 1s and 0s.

This fundamental algorithm to search a graph is called a Depth-First Search (DFS).

The reason this solution is very slow is because work is being repeated. In our search from a to b, we may encounter verticies c, d, e, and f. This tells us that 'a' can reach c, d, e, and f. Yet later, we still check for a path from a to c, a to d, a to e, and a to f. This repeated work can be eliminated by being a little smarter (see the 2nd and 3rd solutions).

 C Syntax (Toggle Plain Text) 
#include <stdio.h>
#define MAX 101
 
int adj[MAX][MAX] = {0};
int visited[MAX];
int n;
 
int find(int i, int dest) {
    int j;
 
    if(i == dest) return 1;
    if(visited[i]) return 0;
    visited[i] = 1;
 
    for(j=0; j<n; j++) if(adj[i][j]) if (find(j, dest)) return 1;
    return 0;
}    
 
int main() {
    int i, j, u, v;
 
    freopen("escalator.in", "rt", stdin);
    freopen("escalator.out", "wt", stdout);
 
    scanf("%d %d", &n, &i);
    while(i--) {
        scanf("%d %d", &u, &v); u--; v--;
        adj[u][v] = 1;
    }
 
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            memset(visited, 0, sizeof(visited)); 
            if(!find(i,j)) {
                printf("Bob is going to get fired!\n");
                return 0;
            }
        }
    }
 
    printf("Vladimir's plan failed.\n");
    return 0;
}
#include <stdio.h>
#define MAX 101

int adj[MAX][MAX] = {0};
int visited[MAX];
int n;

int find(int i, int dest) {
    int j;
    
    if(i == dest) return 1;
    if(visited[i]) return 0;
    visited[i] = 1;
    
    for(j=0; j<n; j++) if(adj[i][j]) if (find(j, dest)) return 1;
    return 0;
}    

int main() {
    int i, j, u, v;
    
    freopen("escalator.in", "rt", stdin);
    freopen("escalator.out", "wt", stdout);
    
    scanf("%d %d", &n, &i);
    while(i--) {
        scanf("%d %d", &u, &v); u--; v--;
        adj[u][v] = 1;
    }
    
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            memset(visited, 0, sizeof(visited)); 
            if(!find(i,j)) {
                printf("Bob is going to get fired!\n");
                return 0;
            }
        }
    }

    printf("Vladimir's plan failed.\n");
    return 0;
}

------------------

Solution #2 (Fast)

This solution is very similar to #1, except we make one (rather significant) improvement.

Instead of checking every pair, we only need to count how many vertecies are reachable from a. If 'a' can reach 'n' vertecies (including itself), then it can reach every floor. This eliminates the need to check all other combinations involving 'a', thus the number of depth-first searches becomes linear rather than quadratic.

This was the "ideal" solution to Escalators.

 C Syntax (Toggle Plain Text) 
#include <stdio.h>
#define MAX 101
 
int adj[MAX][MAX] = {0};
int visited[MAX];
int n;
 
int count(int i) {
    int j, s=0;
 
    if(visited[i]) return 0;
    visited[i] = 1;
 
    for(j=0; j<n; j++) if(adj[i][j]) s += count(j);
    return s+1;
}    
 
int main() {
    int i, j, u, v;
 
    freopen("escalator.in", "rt", stdin);
    freopen("escalator.out", "wt", stdout);
 
    scanf("%d %d", &n, &i);
    while(i--) {
        scanf("%d %d", &u, &v); u--; v--;
        adj[u][v] = 1;
    }
 
    for(i=0; i<n; i++) {
        memset(visited, 0, sizeof(visited)); 
        if(count(i) < n) {
            printf("Bob is going to get fired!\n");
            return 0;
        }
    }
 
    printf("Vladimir's plan failed.\n");
    return 0;
}
#include <stdio.h>
#define MAX 101

int adj[MAX][MAX] = {0};
int visited[MAX];
int n;

int count(int i) {
    int j, s=0;
    
    if(visited[i]) return 0;
    visited[i] = 1;
    
    for(j=0; j<n; j++) if(adj[i][j]) s += count(j);
    return s+1;
}    

int main() {
    int i, j, u, v;
    
    freopen("escalator.in", "rt", stdin);
    freopen("escalator.out", "wt", stdout);
    
    scanf("%d %d", &n, &i);
    while(i--) {
        scanf("%d %d", &u, &v); u--; v--;
        adj[u][v] = 1;
    }
    
    for(i=0; i<n; i++) {
        memset(visited, 0, sizeof(visited)); 
        if(count(i) < n) {
            printf("Bob is going to get fired!\n");
            return 0;
        }
    }

    printf("Vladimir's plan failed.\n");
    return 0;
}

------------------

Solution #3 (Very Fast)

There is one last improvement that can be made to solutions #1 and #2 to come to the fastest known algorithm.

It only requires one observation, which when heard, is almost astoundingly obvious:

If 'a' can reach every node, and every node can reach 'a', then every node can reach every node!

As an algorithm:

Step 1) Check to see if 'a' can reach every node
Step 2) Check to see if every node can reach 'a'

Done!

Why is this true? Say you want to get from 'c' to 'b'. If every node can reach 'a', then 'c' can reach 'a'. And if 'a' can reach every node, then 'a' can reach 'b'. So 'c' goes to 'a' goes to 'b'. This may not be the fastest route, but the efficiency of the route is completely irrelevant in this problem.

But is the inverse always true? If every node is reachable from every other node, 'a' must be able to reach every node and every node must be able to reach 'a'. Therefore, the algorithm must be correct.

Checking if 'a' can reach every node uses the same DFS from solution #2.

Checking if every node can reach 'a' requires a little ingenuity. There are a couple ways, but the easiest way is to flip the direction of the edges and run another DFS. By flipping the edges, we travel the graph backwards from 'a' and reveal which nodes can reach 'a'.

 C Syntax (Toggle Plain Text) 
#include <stdio.h>
#define MAX 101
 
int forwadj[MAX][MAX] = {0};
int backadj[MAX][MAX] = {0};
int visited[MAX];
int n;
 
int count(int i, int adjmatrix[MAX][MAX]) {
    int j, s=0;
 
    if(visited[i]) return 0;
    visited[i] = 1;
 
    for(j=0; j<n; j++) if(adjmatrix[i][j]) s += count(j, adjmatrix);
    return s+1;
}    
 
int main() {
    int i, j, u, v;
 
    freopen("escalator.in", "rt", stdin);
    freopen("escalator.out", "wt", stdout);
 
    scanf("%d %d", &n, &i);
    while(i--) {
        scanf("%d %d", &u, &v); u--; v--;
        forwadj[u][v] = backadj[v][u] = 1;
    }
 
    memset(visited, 0, sizeof(visited)); 
    i = count(0, forwadj); // Traverse the Digraph forwards
    memset(visited, 0, sizeof(visited)); 
    j = count(0, backadj); // Traverse the Digraph backwards
 
    if(i<n || j<n) printf("Bob is going to get fired!\n");
    else           printf("Vladimir's plan failed.\n");
 
    return 0;
}
#include <stdio.h>
#define MAX 101

int forwadj[MAX][MAX] = {0};
int backadj[MAX][MAX] = {0};
int visited[MAX];
int n;

int count(int i, int adjmatrix[MAX][MAX]) {
    int j, s=0;
    
    if(visited[i]) return 0;
    visited[i] = 1;
    
    for(j=0; j<n; j++) if(adjmatrix[i][j]) s += count(j, adjmatrix);
    return s+1;
}    

int main() {
    int i, j, u, v;
    
    freopen("escalator.in", "rt", stdin);
    freopen("escalator.out", "wt", stdout);
    
    scanf("%d %d", &n, &i);
    while(i--) {
        scanf("%d %d", &u, &v); u--; v--;
        forwadj[u][v] = backadj[v][u] = 1;
    }
    
    memset(visited, 0, sizeof(visited)); 
    i = count(0, forwadj); // Traverse the Digraph forwards
    memset(visited, 0, sizeof(visited)); 
    j = count(0, backadj); // Traverse the Digraph backwards
    
    if(i<n || j<n) printf("Bob is going to get fired!\n");
    else           printf("Vladimir's plan failed.\n");

    return 0;
}

------------------

Solution #4 (DP)

There is another solution that uses Dynamic Programming to find the answer very elegantly.

It is called the Floyd-Warshall algorithm, which can be modified to check for transitive closure.

You initially consider every pair of nodes 'i' and 'j', which may or may not have an edge between them.

Then you take another node, called 'k', and introduce it to each pair. For each (i,j) pair, if (i,k) and (k,j) are reachable, then so is (i,j). Thus, an edge can be drawn from 'i' to 'j'.

This essentially built an updated graph where an edge between i and j represents closure between i and j with or without k. And each introduction of a new k updates the graph according to what can now use k.

Once every possible k has been introduced, an edge drawn between i,j means i can reach j if it uses some combination of the k intermediate nodes.

Thus, after a run of Warshall's algorithm, if there is any (i,j) pair which does not have an edge between them, Bob is getting fired.

 C Syntax (Toggle Plain Text) 
#include <stdio.h>
#define MAX 101
 
int adj[MAX][MAX] = {0};
int n;
 
int main() {
    int i, j, k;
 
    freopen("escalator.in", "rt", stdin);
    freopen("escalator.out", "wt", stdout);
 
    scanf("%d %d", &n, &k);
    while(k--) {
        scanf("%d %d", &i, &j); i--; j--;
        adj[i][j] = 1;
    }
 
    for(k=0; k<n; k++)
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                adj[i][j] |= adj[i][k] && adj[k][j];
 
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            if(!adj[i][j]) {
                printf("Bob is going to get fired!\n");
                return 0;
            }     
 
    printf("Vladimir's plan failed.\n");
    return 0;
}
#include <stdio.h>
#define MAX 101

int adj[MAX][MAX] = {0};
int n;

int main() {
    int i, j, k;
    
    freopen("escalator.in", "rt", stdin);
    freopen("escalator.out", "wt", stdout);
    
    scanf("%d %d", &n, &k);
    while(k--) {
        scanf("%d %d", &i, &j); i--; j--;
        adj[i][j] = 1;
    }
    
    for(k=0; k<n; k++)
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                adj[i][j] |= adj[i][k] && adj[k][j];

    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            if(!adj[i][j]) {
                printf("Bob is going to get fired!\n");
                return 0;
            }     

    printf("Vladimir's plan failed.\n");
    return 0;
}

titaniumdecoy · Jul 1st, 2008, 4:09 PM

Sane, can you explain Solution #2 (Fast) a little more? As I understand your explanation, if floor A can reach every other floor, then it doesn't matter which floors can reach A. But that doesn't make sense, since you could have the following: AA, AB, BB. Then you cannot reach floor A from floor B.

What am I missing?

Sane · Jul 1st, 2008, 10:48 PM

The solution I describe in #2 is your solution. I think I just confused you by how I said "combinations involving 'a'". I really meant all of the pairs starting with 'a'. But in short, just refer to your solution, as it's the same as my #2 solution.

titaniumdecoy · Jul 1st, 2008, 11:20 PM

I am fairly certain my solution is #1; notice that the can_reach_all_floors function is recursive, which makes it O(N*E). I will take a closer look at your explanation.

Sane · Jul 1st, 2008, 11:26 PM

Your "canreachallfloors" function, by name, is solution #2. Solution #2 checks to see if every node can reach all floors. That's all.

Solution #1 checks to see if every pair of nodes can reach each other. That's probably the most obvious thing to try, but also the slowest. No one did solution #1.

titaniumdecoy · Jul 1st, 2008, 11:29 PM

Ah, I misread your analysis. So Solution #2 itself is not linear, but the number of depth-first searches necessary is linear. That makes sense.

Jul 1st, 2008, 11:26 PM	#5
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,835 Rep Power: 5	Re: SMAC #2 [06-08] - Escalator Troubles (Senior) Your "canreachallfloors" function, by name, is solution #2. Solution #2 checks to see if every node can reach all floors. That's all. Solution #1 checks to see if every pair of nodes can reach each other. That's probably the most obvious thing to try, but also the slowest. No one did solution #1. __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Jul 1st, 2008, 11:29 PM	#6
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 843 Rep Power: 3	Re: SMAC #2 [06-08] - Escalator Troubles (Senior) Ah, I misread your analysis. So Solution #2 itself is not linear, but the number of depth-first searches necessary is linear. That makes sense.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
SMAC #1 [05-08] - Results	Sane	Software Design and Algorithms	6	Jun 2nd, 2008 4:56 PM
SMAC #1 [05-08] - Ranged Reach (Senior)	Sane	Software Design and Algorithms	0	Jun 2nd, 2008 4:21 PM
SMAC #1 [05-08] - Hurtles (Senior)	Sane	Software Design and Algorithms	0	Jun 1st, 2008 3:59 PM
Ideas for my Senior Project?	joshbax88	Java	1	Apr 26th, 2008 5:57 AM
Senior Capstone-Spying Screen Saver	Hounder	Project Ideas	23	Dec 16th, 2005 7:00 PM

Jul 1st, 2008, 4:09 PM	#2
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 843 Rep Power: 3	Re: SMAC #2 [06-08] - Escalator Troubles (Senior) Sane, can you explain Solution #2 (Fast) a little more? As I understand your explanation, if floor A can reach every other floor, then it doesn't matter which floors can reach A. But that doesn't make sense, since you could have the following: AA, AB, BB. Then you cannot reach floor A from floor B. What am I missing?

Jul 1st, 2008, 10:48 PM	#3
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,835 Rep Power: 5	Re: SMAC #2 [06-08] - Escalator Troubles (Senior) The solution I describe in #2 is your solution. I think I just confused you by how I said "combinations involving 'a'". I really meant all of the pairs starting with 'a'. But in short, just refer to your solution, as it's the same as my #2 solution. __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Jul 1st, 2008, 11:20 PM	#4
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 843 Rep Power: 3	Re: SMAC #2 [06-08] - Escalator Troubles (Senior) I am fairly certain my solution is #1; notice that the can_reach_all_floors function is recursive, which makes it O(N*E). I will take a closer look at your explanation.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > Software Design and Algorithms

SMAC #2 [06-08] - Escalator Troubles (Senior)