Page 1 of 4
10525 - New to Bangladesh?
Posted: Thu Jul 03, 2003 3:00 pm
by titid_gede
this problem looks quite simple.. but i found no one can get AC for this problem, except the problem setter (in the contest). so what happened to this problem? is it really really so difficult?
titid
Posted: Thu Jul 03, 2003 4:19 pm
by anupam
Posted: Fri Jul 04, 2003 8:52 am
by anupam
there may be more than one reports for a road.
Posted: Mon Jul 07, 2003 5:48 am
by LittleJohn
I couldn't get AC on this problem.
What's the output for the same source and destination?
Any input/output will be appreciated!
Posted: Sat Jul 12, 2003 4:22 pm
by carneiro
I used the following input as a test :
6
3 2
1 2 2 5
2 3 3 6
1
1 3
4 2
1 2 5 2
2 3 6 3
1
1 4
3 1
1 2 5 5
1
1 3
2 2
1 2 5 5
1 2 4 5
1
1 2
4 4
1 2 5 5
2 4 5 5
1 3 7 5
3 4 1 5
2
1 4
4 4
2 0
1
1 2
my output for that is :
-------
Distance and time to reach destination is 11 & 5.
No Path.
No Path.
Distance and time to reach destination is 5 & 4.
Distance and time to reach destination is 10 & 8.
Distance and time to reach destination is 0 & 0.
No Path.
--------
But i'm still getting wrong answer, and I can't figure out why. I can't understand if there should be spaces between the blocks or not. I did it this way .
I couldn't understand what you mean by "there may be more than one reports for a road. " What is a report for a road ? By the problem description, there should be 1 report for each QUERY .... what does the road have to do with anything ?
Thank you for your clarifications !
Posted: Sun Jul 13, 2003 6:22 am
by Larry
I haven't tried it yet, but I think it means you can have something like:
1
2 3
1 2 2 2
1 2 3 4
1 2 3 5
1
1 2
I could be wrong, because I haven't tried it yet.. but ya.. it looks trivial..
Posted: Sun Jul 13, 2003 10:07 am
by carneiro
My program (WA) shows the following output
Distance and time to reach destination is 2 & 2.
I was treating different roads for two destinations. Could you show me your output for my input ?
Posted: Sun Jul 13, 2003 10:11 am
by Per
Carneiro: you could try the following input
Code: Select all
1
6 8
1 2 50 100
1 3 50 100
1 4 50 100
2 6 50 100
3 6 51 100
4 6 49 101
1 5 50 100
5 6 49 100
7
1 6
6 1
5 6
5 2
5 3
5 4
4 5
The answer is:
Code: Select all
Distance and time to reach destination is 200 & 99.
Distance and time to reach destination is 200 & 99.
Distance and time to reach destination is 100 & 49.
Distance and time to reach destination is 200 & 99.
Distance and time to reach destination is 200 & 100.
Distance and time to reach destination is 201 & 98.
Distance and time to reach destination is 201 & 98.
I had WA in the contest on this one, but when I sent my solution as 10525 it got AC (although now I see that the ranklist from the contest has been rejudged as well, good for me!
). Remember: first minimize time, then minimize distance (although the problem statement says the opposite)!
Posted: Sun Jul 13, 2003 10:30 am
by anupam
actually a clarification was given during the contest.
that is why it's tough to you to think about the statement.
we have cleared the statement during the contest.
--
Anupam
Posted: Mon Jul 14, 2003 1:33 am
by carneiro
Well, that was news to me. But I changed the program and the output was exactly that of Per, but I still get WA.
My input :
Code: Select all
7
3 2
1 2 2 5
2 3 3 6
1
1 3
4 2
1 2 5 2
2 3 6 3
1
1 4
3 1
1 2 5 5
1
1 3
2 2
1 2 5 5
1 2 4 5
1
1 2
4 4
1 2 5 5
2 4 5 5
1 3 7 5
3 4 1 5
2
1 4
4 4
2 0
1
1 2
2 3
1 2 2 2
1 2 3 4
1 2 3 5
1
1 2
has now the output:
Code: Select all
Distance and time to reach destination is 11 & 5.
No Path.
No Path.
Distance and time to reach destination is 5 & 4.
Distance and time to reach destination is 10 & 8.
Distance and time to reach destination is 0 & 0.
No Path.
Distance and time to reach destination is 2 & 2.
Posted: Mon Jul 14, 2003 1:47 am
by carneiro
Is the spacing between output blocks according to the specification ?
Posted: Mon Jul 14, 2003 5:03 pm
by Per
The spacing seems fine.
On your last test case, my program outputs 5 & 3, so I guess there are no such test cases in judge's input.
(The last cost given in input is the one my program uses.)
If you have the time and energy, try generating a big file of random inputs and I'll run my program on it.
Posted: Mon Jul 14, 2003 6:46 pm
by carneiro
Alright, accepted.
The problem is, the judge is wrong. It needs to overwrite the edges with different values. Oh god ... this is too much guessing for me.
Shouldn't this problem have a new judge program for it ? Or at least be completely re-written.
Thank you Per ! For all your help.
Posted: Tue Jul 15, 2003 1:24 pm
by anupam
actually the mistake was found during the contest and fixed then. but now upgraded in 24 hrs. so i request you to overwrite the preveous edges. and i think boards are useful when problems have bugs.
So, please whenever you found your problems please write to board. it's not all time possible for them to upgrade the problems at any moment. Actually they work too much hard. So please write your problems to board. it will help others to correct themselves
Posted: Fri Aug 15, 2003 11:31 am
by Noim
anupum vai,
i got 5 WA before AC this problem. i have two things to say.
1) why should i overwrite the edge while other minimum edge is availble?
what i think , fixing the judge input and output is better than telling bugs of the problem in the board. Not every one always receive help from the board after getting WA. and again when the judge input and output is being fixed, rejudgement will be then another problem.
2) one thing, first i have to admit i am very weak in english. do you mind to clear me the line:
You are to compute shortest distance having shortest time from the source to destination for each query.
reading this line i first understand that i have to determine the shortest distance. and having the same shortest distance for various path i have to choose that path from them which takes minimum time.
but i manage to ac the problem considering just opposite what i said in earlier paragraph.
i am again informing you that i may be wrong.
but Isn't that line confusing?