544  Heavy Cargo
Moderator: Board moderators
544  Heavy Cargo
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 depthfirst 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 :)
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.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
This is a fairly typical graph problem [if such a thing exists ]. Try looking at some wellknown 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).
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).

 Experienced poster
 Posts: 161
 Joined: Tue Oct 25, 2005 8:38 pm
 Location: buet, dhaka, bangladesh
hi, i am also getting tle. i used floydwarshall 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

the world is nothing but a good program, and we are all some instances of the program

 Learning poster
 Posts: 99
 Joined: Sun Apr 06, 2003 5:53 am
 Location: Dhaka, Bangladesh
 Contact:
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:
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 ) 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) )
Where's the "Any" key?
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.
There is nothing like shortest path. This problem is similar to 10048  Audiophobia.Solaris wrote:Then I try to find the shortest path...

 Learning poster
 Posts: 99
 Joined: Sun Apr 06, 2003 5:53 am
 Location: Dhaka, Bangladesh
 Contact:
You're right mamun. Before my previous post I just checked my old code, it had the function Dijkstra and also ayon mentioned floydwarshall, and I thought that it was actually a shortest path problem
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.
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?

 Experienced poster
 Posts: 161
 Joined: Tue Oct 25, 2005 8:38 pm
 Location: buet, dhaka, bangladesh
hmm, thank you all, i can use dijkstra, but now i know this problem can be solved using floydwarshall. 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.
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

the world is nothing but a good program, and we are all some instances of the program
A typo mistake in inputting.
You're using the same variable, i for controlling the loop as well as indexing s1.
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;
}

 Experienced poster
 Posts: 161
 Joined: Tue Oct 25, 2005 8:38 pm
 Location: buet, dhaka, bangladesh
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 floydwarshall 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

the world is nothing but a good program, and we are all some instances of the program

 New poster
 Posts: 35
 Joined: Wed Apr 12, 2006 6:03 pm
 Location: jakarta, indonesia
 Contact:
can anybody help me???
i got CE, but i run well in my compiler..
thx..
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.
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 ], ;

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

 Experienced poster
 Posts: 109
 Joined: Sat Jun 23, 2007 9:53 pm
 Location: Brest, BELARUS
 Contact:
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(w1w2)>1) do
begin
w := (w1+w2) div 2;
Now I lay me down to sleep...
my profile
my profile

 Experienced poster
 Posts: 109
 Joined: Sat Jun 23, 2007 9:53 pm
 Location: Brest, BELARUS
 Contact:
well, i understood. I had to make additional checking after the search to decide what to take: X or X1.
Now I lay me down to sleep...
my profile
my profile