## 10525 - New to Bangladesh?

Moderator: Board moderators

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

### 10525 - New to Bangladesh?

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
Kalo mau kaya, buat apa sekolah?

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
Last edited by anupam on Sun Aug 17, 2003 9:35 am, edited 1 time in total.
"Everything should be made simple, but not always simpler"

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

there may be more than one reports for a road.
Last edited by anupam on Sun Aug 17, 2003 9:33 am, edited 1 time in total.
"Everything should be made simple, but not always simpler"

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
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
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
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 !
[]s
Mauricio Oliveira Carneiro

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
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 ?
[]s
Mauricio Oliveira Carneiro

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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
``````

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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
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
"Everything should be made simple, but not always simpler"

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
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.``````
Last edited by carneiro on Mon Jul 14, 2003 1:49 am, edited 1 time in total.
[]s
Mauricio Oliveira Carneiro

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
Is the spacing between output blocks according to the specification ?
[]s
Mauricio Oliveira Carneiro

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
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.
[]s
Mauricio Oliveira Carneiro

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
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
"Everything should be made simple, but not always simpler"

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
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?
__nOi.m....