10525 - New to Bangladesh?

[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

[anupam]

[anupam]

there may be more than one reports for a road.

[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!

[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 !

[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..

[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 ?

[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)!

[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

[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.

[carneiro]

Is the spacing between output blocks according to the specification ?

[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.

[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.

[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

[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?