- Forum
- General C++ Programming
- Getting Wrong Answer in Basic Graph Theo
Getting Wrong Answer in Basic Graph Theory Question
Pages: 12
Here's the question :-
Here's my solution :-
But i am getting Wrong Answer for 7 test case and correct answer for only 3 test case ! Can anyone find a flaw or tell corrected code pls ?
| Heroes in Indian movies are capable of superhuman feats. For example, they can jump between buildings, jump onto and from running trains, catch bullets with their hands and teeth and so on. A perceptive follower of such movies would have noticed that there are limits to what even the superheroes can do. For example, if the hero could directly jump to his ultimate destination, that would reduce the action sequence to nothing and thus make the movie quite boring. So he typically labours through a series of superhuman steps to reach his ultimate destination. In this problem, our hero has to save his wife/mother/child/dog/... held captive by the nasty villain on the top floor of a tall building in the centre of Bombay/Bangkok/Kuala Lumpur/.... Our hero is on top of a (different) building. In order to make the action "interesting" the director has decided that the hero can only jump between buildings that are "close" to each other. The director decides which pairs of buildings are close enough and which are not. Given the list of buildings, the identity of the building where the hero begins his search, the identity of the building where the captive (wife/mother/child/dog...) is held, and the set of pairs of buildings that the hero can jump across, your aim is determine whether it is possible for the hero to reach the captive. And, if he can reach the captive he would like to do so with minimum number of jumps. Here is an example. There are 5 buildings, numbered 1,2,...,5, the hero stands on building 1 and the captive is on building 4. The director has decided that buildings 1 and 3, 2 and 3, 1 and 2, 3 and 5 and 4 and 5 are close enough for the hero to jump across. The hero can save the captive by jumping from 1 to 3 and then from 3 to 5 and finally from 5 to 4. (Note that if i and j are close then the hero can jump from i to j as well as from j to i.). In this example, the hero could have also reached 4 by jumping from 1 to 2, 2 to 3, 3 to 5 and finally from 5 to 4. The first route uses 3 jumps while the second one uses 4 jumps. You can verify that 3 jumps is the best possible. If the director decides that the only pairs of buildings that are close enough are 1 and 3, 1 and 2 and 4 and 5, then the hero would not be able to reach building 4 to save the captive. Input format The first line of the input contains two integers N and M. N is the number of buildings: we assume that our buildings are numbered 1,2,...,N. M is the number of pairs of buildings that the director lists as being close enough to jump from one to the other. Each of the next M lines, lines 2,...,M+1, contains a pair of integers representing a pair of buildings that are close. Line i+1 contains integers Ai and Bi, 1 ≤ Ai ≤ N and 1 ≤ Bi ≤ N, indicating that buildings Ai and Bi are close enough. The last line, line M+2 contains a pair of integers S and T, where S is the building from which the Hero starts his search and T is the building where the captive is held. Output format If the hero cannot reach the captive print 0. If the hero can reach the captive print out a single integer indicating the number of jumps in the shortest route (in terms of the number of jumps) to reach the captive. Test Data: You may assume that 1 ≤ N ≤ 3500 and 1 ≤ M ≤ 1000000. Further, in at least 50% of the inputs 1 ≤ N ≤ 1000 and 1 ≤ M ≤ 200000. Example: Here are the inputs and outputs corresponding to the two examples discussed above. Sample Input 1: 5 5 1 3 2 3 1 2 3 5 4 5 1 4 Sample Output 1: 3 Sample Input 2: 5 3 1 3 1 2 4 5 1 4 Sample Output 2: 0 |
Here's my solution :-
|
|
But i am getting Wrong Answer for 7 test case and correct answer for only 3 test case ! Can anyone find a flaw or tell corrected code pls ?
Last edited on
int i,j,steps=1,n,m,s,t,tmp,tmp1,visited[1000001];I see this in your code a lot. You're not being charged per letter. If you give your variables meaningful names, you'll be able to read your own code and see the mistakes in logic.
Explain how is your graph formed.
white-space is free.
You aren't initializing your variables.
¿where do those limit come from?
white-space is free.
You aren't initializing your variables.
|
|
@Moschops , i really used the variables with meaningfull names , n & m & s & t are used as given in Input Format so that it becomes easier to understand and yes tmp and tmp1 are temporary variables used for input only while i & j as usual are counter variables :)
@ne555 , here's how my 2D-array 'buildings' will be after input will look like for given sample input :-
Here 0th coloumn stores nos. of neigbours of every ith row (representing buildings.
Thus , 1st row tells about building 1 which has 2 buildings close enough to it and they are 3 & 2.
The graph is obviously an undirected one .
In my undirected graph , all buildings that are close enough to be able to move through are connected and we start our search of target building from starting building , we are using BFS (Breadth First Search Algorithm) , we start it by initializing queue 'tovisit' (which tracks all buildings to visit next) with neighbours of starting building and mark starting building as marked (by marking array 'visited[s]' as 1 , ie at that nos. of intial building .
After initializing 'tovisit' with initial building's neighbours , we push '-1' into queue to track nos. of steps . Then we begin a while loop that runs till queue is empty ( or we exit when found target) , we first check if building is target or not , if yes then print steps and exit or else simply proceed on. Then we check if queue's value is not -1 (its like marker stone for us , for separating buildings of same distance for initial building and counting that distance) . If it is -1 then we increment 'steps' and pop this -1 from list . Then check if queue is empty , if it is we print 0 else we proceed by adding -1 at end of queue to separate upcoming buildings that will be of 1 unit more distance.
Then we use a for loop that runs till the nos. of that buildings neighbour of times (which is given by "buildings[tovisit.front()][0]" ) . ie if a building has 4 neighbours then for loop runs 4 times . Then we check if it is not visited , if it is not visited then we push its neghbours . This goes on & on till finally we get 0 or some other nos. as output .
Okay i had got a bug while describing this all :)
Here's edited code :-
(Edit on 26th line for pushing all its neghbours)
Also now i am getting "Correct Answer" in only 2 and "Wrong Answer" in 1 and rest i get is "Runtime Error: ABRT
Description: Aborted (got SIGABRT)" !!!
@ne555 , here's how my 2D-array 'buildings' will be after input will look like for given sample input :-
0 1 2 3 4 5 -------------------------------- 1 | 2 3 2 2 | 2 3 1 3 | 3 1 2 5 4 | 1 5 5 | 2 3 4 |
Here 0th coloumn stores nos. of neigbours of every ith row (representing buildings.
Thus , 1st row tells about building 1 which has 2 buildings close enough to it and they are 3 & 2.
The graph is obviously an undirected one .
In my undirected graph , all buildings that are close enough to be able to move through are connected and we start our search of target building from starting building , we are using BFS (Breadth First Search Algorithm) , we start it by initializing queue 'tovisit' (which tracks all buildings to visit next) with neighbours of starting building and mark starting building as marked (by marking array 'visited[s]' as 1 , ie at that nos. of intial building .
After initializing 'tovisit' with initial building's neighbours , we push '-1' into queue to track nos. of steps . Then we begin a while loop that runs till queue is empty ( or we exit when found target) , we first check if building is target or not , if yes then print steps and exit or else simply proceed on. Then we check if queue's value is not -1 (its like marker stone for us , for separating buildings of same distance for initial building and counting that distance) . If it is -1 then we increment 'steps' and pop this -1 from list . Then check if queue is empty , if it is we print 0 else we proceed by adding -1 at end of queue to separate upcoming buildings that will be of 1 unit more distance.
Then we use a for loop that runs till the nos. of that buildings neighbour of times (which is given by "buildings[tovisit.front()][0]" ) . ie if a building has 4 neighbours then for loop runs 4 times . Then we check if it is not visited , if it is not visited then we push its neghbours . This goes on & on till finally we get 0 or some other nos. as output .
Okay i had got a bug while describing this all :)
Here's edited code :-
|
|
(Edit on 26th line for pushing all its neghbours)
Also now i am getting "Correct Answer" in only 2 and "Wrong Answer" in 1 and rest i get is "Runtime Error: ABRT
Description: Aborted (got SIGABRT)" !!!
Last edited on
You know what's even easier to understand than
n? inputIntegerN. When I see n, it means nothing. When I see inputIntegerN, I know it's the input integer 'n'. Just because requirements are written horrifically doesn't mean the code has to be as well.
I have to agree with ne555. Whitespace is free. It is very difficult to read:
Much easier would be:
And I'm not talking about whether the opening curly braces should be on the same line as the "if" or "for". That's a personal style decision (my choice is obvious). By using new lines and consistent indentation, it become much easier for you or others to see the structure of the program without having to keep a mental logic stack while reading it. You already do it for the opening "for" and the "while", do it for the "if"s and nested "for"s, too.
Your grade does not depend on how few lines of code you write or how few pages of paper it takes to print it out (or at least it shouldn't). Do yourself a big favor now and learn to use white space (new lines, indentation, blank lines) to organize your code for easier reading and comprehension.
Edit - missed a new line
|
|
Much easier would be:
|
|
And I'm not talking about whether the opening curly braces should be on the same line as the "if" or "for". That's a personal style decision (my choice is obvious). By using new lines and consistent indentation, it become much easier for you or others to see the structure of the program without having to keep a mental logic stack while reading it. You already do it for the opening "for" and the "while", do it for the "if"s and nested "for"s, too.
Your grade does not depend on how few lines of code you write or how few pages of paper it takes to print it out (or at least it shouldn't). Do yourself a big favor now and learn to use white space (new lines, indentation, blank lines) to organize your code for easier reading and comprehension.
Edit - missed a new line
Last edited on
I think that inputIntegerN is as descriptive as n. Better would be number_of_buildings
So you are using a list of neighbours.
Out of bounds generates undefined behaviour.
So you are using a list of neighbours.
int buildings[3501][300]; ¿Who told you that there is a '300' limit? Out of bounds generates undefined behaviour.
okay next time i will try to exploit white space more , use more descreptive variables and use more lines .
@ne555 , 3501*300 is the maximum size that site's compiler allows :( . Thats why i am looking for better option .
@ne555 , 3501*300 is the maximum size that site's compiler allows :( . Thats why i am looking for better option .
Then use a dynamic structure for your list of neighbours. Maybe std::vector (of course just use the memory that you actually need)
¿why did you waste time? There was no reason to suppose such a limit. So if your approach use too much resources, then change the approach.
¿why did you waste time? There was no reason to suppose such a limit. So if your approach use too much resources, then change the approach.
Could you please tell me about dynamic structure for my list of neighbours ? or a reference/link to it because i dont want to realter my complete program :)
And i had not thought of this problem , so i started with algorithm that would be fastest possibly that i could think and didn't bother about memory at all .
And i had not thought of this problem , so i started with algorithm that would be fastest possibly that i could think and didn't bother about memory at all .
@OP
This is a perfect example of an SSSPP, which can be solved with the Dijkstra algorithm. Since your main problem seems to be sloppy code, I'd suggest trying the Dijkstra algorithm, since it's very simple and "self-structured".
This is a perfect example of an SSSPP, which can be solved with the Dijkstra algorithm. Since your main problem seems to be sloppy code, I'd suggest trying the Dijkstra algorithm, since it's very simple and "self-structured".
There are no weights (or all the weights are the same). BFS will work just fine, and would behave equivalent to Dijkstra.
I didn't explain it clearly. If you weren't worried about memory then you should have used
So your question should have been, '¿how can I create a really big matrix?'
choose one (wisely) http://cplusplus.com/reference/stl/
I didn't explain it clearly. If you weren't worried about memory then you should have used
int buildings[3501][3501] from the start. Then you would realize that the stack can't hold that much.So your question should have been, '¿how can I create a really big matrix?'
| Could you please tell me about dynamic structure for my list of neighbours ? |
choose one (wisely) http://cplusplus.com/reference/stl/
BFS will definitely work, but I find it much harder to properly structure that code. The Dijkstra algorithm is very clean by itself, making it easy for "beginners" who still have trouble with code design/organization (like myself). It's also a great introduction to more advanced data structures!
Of course, this is just an aside-suggestion. BFS will definitely get you there (and probably outperform Dijkstra's)!
Of course, this is just an aside-suggestion. BFS will definitely get you there (and probably outperform Dijkstra's)!
@ne555 , yeah i would have really made that question as topic but there really was a little bug when i posted this question , then i corrected it and edited it here instantly , then i got this new problem so this explains why i had choosen that line as topic .
@Gaminic , i had seen Dijkstra's algorithm , i would definatly try now
@Gaminic , i had seen Dijkstra's algorithm , i would definatly try now
Last edited on
Ummm , @ne555 as you had advised me to choose a better container , i thought to give a try to 'vectors' . I changed my code a little at declaration , but my compiler (Dev-C++ 4.9.9.2) is giving me error by opening "stl_vector.h" giving me loads of error -
and so on ... maybe i didn't get the vector concept for 2Dimension , can you please help me ? Here's my edited code :-
1)110 C:\Dev-Cpp\include\c++\3.4.2\bits\stl_vector.h instantiated from `std::_Vector_base<int, int>' 2)142 C:\Dev-Cpp\include\c++\3.4.2\bits\stl_vector.h instantiated from `std::vector<int, int>' 3)159 C:\Dev-Cpp\include\c++\3.4.2\bits\stl_vector.h `int' is not a class, struct, or union type 4)16 E:\c++\greatescape_iarcs.cpp no match for 'operator[]' in 'buildings[tmp1]' |
and so on ... maybe i didn't get the vector concept for 2Dimension , can you please help me ? Here's my edited code :-
|
|
A vectors of vectors would be
Accessing out of bounds is still an error, the vector will not grow in that case.
To expand it you could use the push_back() method.
Also, a vector keeps track of its size.
Remember that the index starts at 0
Liar
vector< vector<int> >Accessing out of bounds is still an error, the vector will not grow in that case.
To expand it you could use the push_back() method.
Also, a vector keeps track of its size.
|
|
| OP wrote: |
|---|
| okay next time i will try to exploit white space more , use more descreptive variables and use more lines . |
@ne555 , i am getting Runtime error fetching 0 points . Could you please tell me the places where i would need to edit in my programme ?
Ans yes - me no liar , by next time i meant next problem :P , okay but i am rediting my whole code with more descriptive variables and lines very soon :)
Ans yes - me no liar , by next time i meant next problem :P , okay but i am rediting my whole code with more descriptive variables and lines very soon :)
Here's it @ne555
|
|
Pages: 12