544 - Heavy Cargo

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

544 - Heavy Cargo

Post by zsepi » Sat Jan 04, 2003 10:35 pm

I just started to try graph related problems, and I got stuck on the first problem... this one. I took a pretty brute force, backtracking based approach, once arriving at a city, going to every linked one, recursively (isn't it what depth-first search is all about?).
My solution is giving the right answers for the sample input (OK, I know that they are easy), but once submitted I get TL
I just want to know if anyone got AC with backtracking, or should I start to look for some other approach?

thanx in advance :)
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Sat Jan 04, 2003 11:12 pm

This is a fairly typical graph problem [if such a thing exists :wink:]. Try looking at some well-known graph algorithms such as Dijkstra's Algorithm, Kruskal's Algorithm, or Prim's Algoirithm to get some ideas for a more efficient approach - you should have no trouble solving the problem in under 1 second.

If you are still having trouble with this problem, you may want to try some easier graph problems first. For example, problem 459 can be solved with a simpler algorithm (that is very similar to the one that you described).

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sat Jan 14, 2006 5:31 pm

hi, i am also getting tle. i used floyd-warshall maximin distance. and i used binary search tree for string searching. can't it be run within time limit applying these methods? here n can be as big as 200. and my program is O(n^3), is it acceptable?
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Sat Jan 14, 2006 6:45 pm

Your complexity .. O(n^3) which in worst case can result in about 8 x 10^6 iterations may be (or may not be) good enough for this problem. But as each of iterations also requires a search and a number of string compares the complexity actually rises by a factor that can get u TLE.

Here is how I solved the problem:
  • Represented each city by an integer for example say .. "Stuttgart" is represented by node 1 and "Ulm" is represented by 2. Then I try to find the shortest path between 1 and 2 instead of Stuttgart and Ulm. This I believe reduces the practical complexity of the problem, as I dont need string comparison in the main iterative portion of the problem. Applying Floyd Warshall along with this indexing SHOULD (I havent tested it myself though :P) get u AC.

    You actually dont need to use ALL PAIR SHORTEST PATH algorithm such as Floyd Warshall in this problem. Because u are given a single pair of cities for a single scenario. Finding the shortest path between all pairs is completely unnecessary, rather you can go for single source shortest path algorithm such as Dijkstra which will reduce the runtime significantly (using priority queue the complexity is O(nlogn) and without using PQ O(n^2) )
Hope it helps :)
Where's the "Any" key?

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Sat Jan 14, 2006 7:32 pm

After reading ayon's post I have just solved this using Floyd Warshall. Djikstra would be faster I think. My timing isn't one of the fastests but less than half a second. So I'll take it. Moreover I used STL which is thought to be slow. ayon, What do you do before BST? Another problem may be input processing.
Solaris wrote:Then I try to find the shortest path...
There is nothing like shortest path. This problem is similar to 10048 - Audiophobia.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Sat Jan 14, 2006 7:49 pm

You're right mamun. Before my previous post I just checked my old code, it had the function Dijkstra and also ayon mentioned floyd-warshall, and I thought that it was actually a shortest path problem :oops:

Sorry for my misleading post. Dijkstra without priority queue is quite fast though (around 0.05 seconds).

The actual problem is a modification of basic shortest path problem.
Where's the "Any" key?

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sun Jan 15, 2006 11:21 am

hmm, thank you all, i can use dijkstra, but now i know this problem can be solved using floyd-warshall. then why am i getting tle? i didnt use STL, i didn't compare strings in my O(n^3) loops.
here goes my code: to understand my code, i can tell you that, here insert() function return 1 after inserting, and if the string already exist the function return 0, and of course i represented each city by a number(k). i guess i didnt do anything wrong in input processing.

Code: Select all

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

typedef struct rec
{
	char s[35];
   int n;
   struct rec *left;
   struct rec *right;
} node;

node *head;

int min(int a, int b)
{
	return a < b? a : b;
}

int max(int a, int b)
{
	return a > b? a : b;
}

int insert(char s[], int k, int &i)
{
	node *T;
   T = head;
   if(head == NULL)
   {
   	head = new node;
      T = head;
   }
   else
   for(;;)
   {
   	if(strcmp(s, T->s) == 0)
      {
      	i = T -> n;
      	return 0;
      }
		if(strcmp(s, T->s) < 0)
      {
      	if(T -> left == NULL)
         {
         	T -> left = new node;
            T = T -> left;
            break;
         }
      	T = T -> left;
      }
      else
      {
      	if(T -> right == NULL)
         {
         	T -> right = new node;
            T = T -> right;
            break;
         }
      	T = T -> right;
      }
   }
   strcpy(T -> s, s);
   T -> n = k;
   T -> left = T -> right = NULL;
   i = k;
   return 1;
}

void freeBST(node *T)
{
	if(T == NULL)
   	return;
   freeBST(T -> left);
   freeBST(T -> right);
   free(T);
}

void main()
{
	int i, j, k, l, n, r, set = 0, d, load[201][201];
   char s1[32], s2[32];
	for(;;)
   {
   	scanf("%d%d", &n, &r);
      if(n == 0 && r == 0)
      	break;
      k = 0;
      memset(load, -1, sizeof(load));
      for(i = 0; i < n; ++i)
      	load[i][i] = 0;
      head = NULL;
      for(i = 0; i < r; ++i)
      {
      	scanf(" %s %s%d", s1, s2, &d);
			if(insert(s1, k, i))
         	++k;
         if(insert(s2, k, j))
         	++k;
         load[i][j] = load[j][i] = d;
      }
      for(l = 0; l < n; ++l)
       	for(i = 0; i < n ;++i)
           	for(j = i; j < n; ++j)
              	load[i][j] = load[j][i] = max(load[i][j], min(load[i][l], load[l][j]));
      scanf(" %s %s", s1, s2);
      insert(s1, 0, i);
      insert(s2, 0, j);
      printf("Scenario #%d\n%d tons\n\n", ++set, load[i][j]);
      freeBST(head);
   }
}
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Sun Jan 15, 2006 11:52 am

A typo mistake in inputting.

Code: Select all

      for(i = 0; i < r; ++i) 
      { 
         scanf(" %s %s%d", s1, s2, &d); 
         if(insert(s1, k, i)) 
            ++k; 
         if(insert(s2, k, j)) 
            ++k; 
         load[i][j] = load[j][i] = d; 
      } 
You're using the same variable, i for controlling the loop as well as indexing s1.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sun Jan 15, 2006 2:32 pm

ah, thanks mamun vai. i got accepted in 0.156 sec. that was a stupid mistake. i was wondered, why i was getting tle with vertices at most 200. but i could not find the mistake. it's very easy to use floyd-warshall than other graph algorithms, so i use this algorithm often for small inputs.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Bluefin
New poster
Posts: 20
Joined: Sat Jul 08, 2006 3:39 pm
Contact:

Post by Bluefin » Sun Nov 05, 2006 12:05 pm

I try to solve this problem, but always WA !!
Can anyone of you give me some critical IO ???

Thanks in advance ~~ :D
"It's nice to be important, but it's more important to be nice"

http://bluefintuna.wordpress.com/

albet_januar
New poster
Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia
Contact:

Post by albet_januar » Thu Apr 26, 2007 8:16 pm

can anybody help me???

i got CE, but i run well in my compiler..
thx..

Code: Select all

delete after AC..
Last edited by albet_januar on Sat Apr 28, 2007 5:36 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Fri Apr 27, 2007 3:51 am

Here.. :-)
albet_januar wrote:can anybody help me???

i got CE, but i run well in my compiler..
thx..

Code: Select all

   char input[ 1000 ], fr[ 100 ], to[ 100 ], bil[ 100 ], ;

albet_januar
New poster
Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia
Contact:

Post by albet_januar » Sat Apr 28, 2007 5:35 pm

thx.. i got my mistake..
Gbu..

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Tue Jul 03, 2007 12:59 pm

I was solving using the binary search (for weight of cargo) and then searching the path in the graph between these two cities. But it's giving WA. I think it is because my program gives answer +/- 1 to the right. Or is not? Can you have a look at binary search fragment of my code plz:

Code: Select all

    while (abs(w1-w2)>1) do
    begin
        w := (w1+w2) div 2;
Now I lay me down to sleep...
my profile

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Tue Jul 03, 2007 2:45 pm

well, i understood. I had to make additional checking after the search to decide what to take: X or X-1.
Now I lay me down to sleep...
my profile

Post Reply

Return to “Volume 5 (500-599)”