## 10525 - New to Bangladesh?

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
Dear Noim,
When the contest was held, the statement was made clear by writing that
1)you should determine first sht est time.
2)if there is more than one path you should choose the shortest distance. among them.
and again, i made contact with them about the bug but they are very busy now with their new server and they give much more time in real time contest than in 24 hrs. so i posted in the board first and then after a lot of discussion till my post i think it's clear. any1 just watched once in the posts can easily find it and fix his/her bugs. and rejudgement was a hard work. that is why i have no other ways. for example, the sample out was wrong for the prob height to area. but as they are working, look at the boards please.
"Everything should be made simple, but not always simpler"

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm
carneiro,
I think your Program give WA for input like-
1

2 2
1 2 4 5
1 2 5 5
1
1 2
My AC code says output should be:
Distance and time to reach destination is 5 & 5.
I think your one gives-
Distance and time to reach destination is 4 & 5.
There is obviously some bugs in the problem.To get AC you have to overwrite the edges.

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
I am very teased with this problem. My program passes all test data I found on the forum or devised myself. What does overwriting edges mean?

longer
New poster
Posts: 2
Joined: Thu Nov 06, 2003 9:44 am

### What's wrong with the code?

I also tried some other combinations when the edges are over written. But all got WA.

int m,n;
//vector<int> nms;
int r[100][100];
int r1[100][100];

void main()
{
int t;
int i,j,k;
int q,q1;
int nm1,nm2;
cin>>t;
while(t)
{
//nms.clear();
cin>>n>>m; if(n>=100) m=n/(i-i);
for(i=0;i<n+1;i++)
for(j=0;j<n+1;j++)
r[j]=r1[j]=-1;
for(i=0;i<n+1;i++)
r=r1=0;
for(i=0;i<m;i++)
{
cin>>j>>k;
if(j>n || j<=0 || k>n || k<=0) m=m/(i-i);
cin>>q>>q1;
if(r[j][k]<0 || q<r[j][k] || (q==r[j][k] && q1<r1[j][k]))
{
r[j][k]=r[k][j]=q;
r1[j][k]=r1[k][j]=q1;
}
}
//n=nms.size();
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
if(r[j]>=0 && r[j][k]>=0)
{
q=r[j]+r[j][k];
q1=r1[j]+r1[j][k];
if(r[k]<0 || q<r[i][k] || (q==r[i][k] && q1<r1[i][k]))
{
r[i][k]=q;
r1[i][k]=q1;
}
}

cin>>q;
for(i=0;i<q;i++)
{
cin>>j>>k;
if(j>n || k>n ||j<=0 || k<=0) m=n/(i-i);
if(j<0 || k<0 || r[j][k]<0) cout<<"No Path."<<endl;
else cout<<"Distance and time to reach destination is "<<r1[j][k]<<" & "<<r[j][k]<<"."<<endl;
}
t--;
if(t) cout<<endl;
}
}
[cpp][/cpp][cpp][/cpp]

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

### what hs changed since last post, 'coz WA

I keep getting WA and it frustrates me quite a lot (not surprising, eh?)
After reading the forum, I became even more confused (usually the opposite happens), so I would like to ask a few questions

1) edge overwriting
So, when I add an edge, I should always keep the latest one, or should I keep the edge with shortest time and if time is same with, then overwrite only if new edge has shorter distance than existent one?
ie: if input is

Code: Select all

``````1

2 3
1 2 4 4
1 2 4 3
1 2 5 5``````
which is the right edge to use?

2) finding shortest path
I think it's clear, but just to be safe: the program should look for the minimal time with the shortest length, right? so, is the following comparison right:
[c]if(currentTime <= bestTimeSoFar) {
if(currentTime < bestTimeSoFar || currentDistance < bestDistanceSoFar)
update shortest path
}[/c]

3) we are dealing with an undirected graph, right?
None of the roads of Bangladesh are one ways
4) What is the maximum length of a shortest path?
I am using floyd-warshall to solve the problem, and i use infinity = 1 << 30 - there is no chance that a shortest path will be this long or longer, right?

Thanks in advance for replies.
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.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

### Re: what hs changed since last post, 'coz WA

1) Always the last one, for some obscure reason. I.e. 1 2 5 5 in this case.

2) Yup, that should work.

3) Yup.

4) I actually use 2^61 as infinity. I'm not sure this is something I did out of sheer paranoia when I got WA, or if it is actually needed.

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

### thanks per!

it's not paranoia..... 2^61 seems to be the right value for infinity. That was the only thing I changed, and got ac... stupid stupid bug
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.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I use a value of 1e9 for infinity and get accepted, so I don't think you need 64 bits. The thing is that during Floyd you do something like[c]newdist=dist[from][intermediate]+dist[intermediate][to];
if(newdist<dist[from][to]) dist[from][to]=newdist;[/c] so you should be able to deal with double infinity. If you use 32-bits signed integers and 2^30 as value for infinity, than newdist can become 2^30+2^30 = 2^31, which is smaller than zero!

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA
little joey wrote:If you use 32-bits signed integers and 2^30 as value for infinity, than newdist can become 2^30+2^30 = 2^31, which is smaller than zero!
joey, I'm aware of that problem, that's why I have in the comparison

Code: Select all

``````if(g[from][intermed].time != INF  &&  g[intermed]toj].time != INF) {

time = g[from][intermed].time + g[intermed][to].time;

....``````
so I don't know why, but when I changed the type of time from int to long long and "increased infinity", I got AC without any other modification and that made me think that 2^30 is not big enough.
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.

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
you don't have to use 2^61 you can just use 2^31-1 as infinity....

I got WA at the contest and after one year i got AC... <yupi>
Remember Never Give Up
Regrads
Miras

Guest
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Location: Dhaka, Bangladesh
Contact:

### 10525 New To Bangladesh

Hello,
Can anyone help me by answering the following questions:

1. The problem statement says "Places are numbered starting from 1.", does this mean 1 <= place_number <= max_node? Or do I need to map the numbers?
Ans: No need to map.

2. I'm using Floyd-Warshall, what could be the limit for maxnode and INF? I'm using 300 and 1000000000, respectively.
Ans: 200 is enough.

3. Is the following code segment correct? I'm using it in my Floyd-Warshall function.

Code: Select all

`` .. ``

Thank you.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### 10525 - NEW TO BANGLADESH?

i think my code is handling the duplicated roads very well.. but getting WA!!
please help me... Y.Y

map[][] is for time..
map2[][] is for distance..

Code: Select all

``````CUT AFTER AC
``````
Last edited by helloneo on Fri Jun 08, 2007 6:10 am, edited 3 times in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Code: Select all

``````rejudged..
``````
Last edited by helloneo on Thu Mar 23, 2006 1:14 pm, edited 1 time in total.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
-- CUT. This task has been rejudged. --
Last edited by Observer on Sat Mar 25, 2006 7:12 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### which prolem has been rejudged recently..?

i saw many people got -1 solved problems..
anybody know which problem it is..?