10543 - Traveling Politician

UFP2161 · Post by **UFP2161** » Sat Jun 12, 2004 10:34 pm

I used two queues, both of size 52. I don't know why you need one that's much bigger than that.

shamim · Post by **shamim** » Sun Jun 13, 2004 6:50 am

I used two queues, both of size 52. I don't know why you need one that's much bigger than that.

One thing I don't understand is, if a small size queue works, then why shouldn't a bigger one.

I remember solving this problem using STL(C++) queue, I got Memory Limit Exceeded. I couldn't understand why. Now STL queue dynamically sizes it self, so the queue should never get big enough to cause MLE.

Later I used a circular queue of MAX size 1000000 and I got AC.

UFP2161 · Post by **UFP2161** » Sun Jun 13, 2004 7:08 am

It depends on how you're using your queue.. maybe queue is the wrong term for what I did.. a better term would be having used two min cost arrays.. one for current depth, one for next depth..

Rajib · Post by **Rajib** » Sun Jun 13, 2004 9:46 am

I don't understand how you use two '52 size' Que to solve the problem

. It can happen that there is a loop in the graph and after traversing the loop for savarel times we can reach the destination city.

Can you explain how you use those two Que.

UFP2161 · Post by **UFP2161** » Sun Jun 13, 2004 2:16 pm

After some number of speeches my array holds a 1 if the city can be reached, and a 0 if it cannot, and thus can traverse from there. You only need to know whether a city can be reached w/ some number of speeches before it.

Abednego · Post by **Abednego** » Thu Jun 17, 2004 7:27 pm

I don't think there is a bug like that in the judge's solution. ;-) It doesn't use any queues or BFS at all.- just 3 arrays of size 50x50.

anupam · Post by **anupam** » Fri Jul 02, 2004 12:50 pm

I have solved the problem withuot using any queue or bfs at all.
I used three arrays.
Let the adj matrix is a[1..N][1..N] where a[j]=1 if it is given in input otherwise it is 0.
Then
A^n=A^(n-1)*A given you the a matrix where each entry denotes the number of way to reach the destination from the source with n length path.
SO check for only such entry.

anupam · Post by **anupam** » Fri Jul 02, 2004 12:51 pm

I have solved the problem withuot using any queue or bfs at all.
I used three arrays.
Let the adj matrix is a[1..N][1..N] where a[j]=1 if it is given in input otherwise it is 0.
Then
A^n=A^(n-1)*A given you the a matrix where each entry denotes the number of way to reach the destination from the source with n length path.
SO check for only such entry.

Nemo · Post by **Nemo** » Mon Jun 13, 2005 9:02 pm

what's wrong with this code? gets WA.....

Code: Select all


#include <iostream.h>
#include <stdio.h>
#include <math.h>

void main()
{

	int n, m, k, u, v, p, q, r, i;

	scanf(" %d %d %d ", &n, &m, &k);
	while (n || m || k) {
		int g[50][50] = {0};
		int temp1[50][50] = {0};
		int temp2[50][50] = {0};

		for (i = 0; i < m ; i++) {
			scanf(" %d %d ", &u, &v);
			g[u][v]++;
			temp1[u][v]++;
		}

		if (k == 2 && g[0][n - 1]) {
			printf("2\n");
			scanf(" %d %d %d ", &n, &m, &k);
			continue;
		}


		for (i = 2; i < 20 ; i++) {
			for (p = 0; p < n ; p++) 
				for (q = 0; q < n ; q++) 
					if (i % 2 == 0) {
						temp2[p][q] = 0;
						for (r = 0; r < n ; r++) 
							temp2[p][q] += temp1[p][r] * g[r][q];
					}
					else {
						temp1[p][q] = 0;
						for (r = 0; r < n ; r++) 
							temp1[p][q] += temp2[p][r] * g[r][q];
					}
				
			if (i % 2 == 0)
				if (temp2[0][n - 1] && i >= k - 1)
					break;
			else
				if (temp1[0][n - 1] && i >= k - 1)
					break;

		}

		if (i == 20)
			printf("%s\n", "LOSER");
		else
			if (i % 2 == 0)
				if (temp2[0][n - 1] && i >= k - 1)
					printf("%d\n", i + 1);
				else
					printf("%s\n", "LOSER");
			else
				if (temp1[0][n - 1] && i >= k - 1)
					printf("%d\n", i + 1);
				else
					printf("%s\n", "LOSER");
			
		scanf(" %d %d %d ", &n, &m, &k);
	}

}

Nemo · Post by **Nemo** » Sun Jun 19, 2005 11:45 am

What's wrong with this? gets WA.......

Code: Select all

#include <iostream.h> 
#include <stdio.h> 
#include <math.h> 

void main() 
{ 

   int n, m, k, u, v, p, q, r, i; 

   scanf(" %d %d %d ", &n, &m, &k); 
   while (n || m || k) { 
      int g[50][50] = {0}; 
      int temp1[50][50] = {0}; 
      int temp2[50][50] = {0}; 

      for (i = 0; i < m ; i++) { 
         scanf(" %d %d ", &u, &v); 
         g[u][v]++; 
         temp1[u][v]++; 
      } 

      if (k == 2 && g[0][n - 1]) { 
         printf("2\n"); 
         scanf(" %d %d %d ", &n, &m, &k); 
         continue; 
      } 


      for (i = 2; i < 20 ; i++) { 
         for (p = 0; p < n ; p++) 
            for (q = 0; q < n ; q++) 
               if (i % 2 == 0) { 
                  temp2[p][q] = 0; 
                  for (r = 0; r < n ; r++) 
                     temp2[p][q] += temp1[p][r] * g[r][q]; 
               } 
               else { 
                  temp1[p][q] = 0; 
                  for (r = 0; r < n ; r++) 
                     temp1[p][q] += temp2[p][r] * g[r][q]; 
               } 
             
         if (i % 2 == 0) 
            if (temp2[0][n - 1] && i >= k - 1) 
               break; 
         else 
            if (temp1[0][n - 1] && i >= k - 1) 
               break; 

      } 

      if (i == 20) 
         printf("%s\n", "LOSER"); 
      else 
         if (i % 2 == 0) 
            if (temp2[0][n - 1] && i >= k - 1) 
               printf("%d\n", i + 1); 
            else 
               printf("%s\n", "LOSER"); 
         else 
            if (temp1[0][n - 1] && i >= k - 1) 
               printf("%d\n", i + 1); 
            else 
               printf("%s\n", "LOSER"); 
          
      scanf(" %d %d %d ", &n, &m, &k); 
   } 

}

jurajz · Post by **jurajz** » Sat May 05, 2007 10:26 pm

Thank you for this thread, little joey!

I am Pascal programmer, and I had many WA's. I wrote the same code from Pascal to C and have AC, with the first submit.

OJ Board

10543 - Traveling Politician

10543 - Travelling politician