All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
-
Darko
- Guru
- Posts: 580
- Joined: Fri Nov 11, 2005 9:34 am
- Location: Calgary, Canada
Post
by Darko » Fri Dec 30, 2005 8:01 am
This is what my program does (Impossible.):
Code: Select all
0000100000
0010010000
0101111100
1001111100
0011111110
1001111100
1111111100
1111010001
1111000100
1111101110
Mind you, it keeps timing out, but I'm convinced it works.
You are, basically, drawing a circle around a point with the radius L. so, if L is 3, the spot 2 left and 2 down from the given spot should be inside it (because 2*2+2*2 <= 3*3).
Hope that helps.
Darko
-
Observer
- Guru
- Posts: 570
- Joined: Sat May 10, 2003 4:20 am
- Location: Hong Kong
Post
by Observer » Fri Dec 30, 2005 8:11 am
Well actually the case is not valid, since loudness >= 1 (Read the problem description again...)

-
Darko
- Guru
- Posts: 580
- Joined: Fri Nov 11, 2005 9:34 am
- Location: Calgary, Canada
Post
by Darko » Fri Dec 30, 2005 8:24 am
Well, just remove that Jigglypuff then! :)
(other than that my grid should work, right?)
I liked the whole set (although I got only 2 at the contest time), but I can't figure out why my BFS is too slow on OJ.
Did you guys make Java solutions? I know it's just an online contest, and we are supposed to learn from it (and I did!), but I think for the real thing, problem setters are supposed to provide the solutions in all languages accepted.
Darko
-
tan_Yui
- Experienced poster
- Posts: 155
- Joined: Sat Jul 10, 2004 12:41 am
Post
by tan_Yui » Fri Dec 30, 2005 10:04 am
Thanks, Darko and Observer.
Finally, I could get Accepted
My WA code was failed because I've ignored about 'Euclidean distance'.
I vaguely understood this until now.
I am glad to obtain this knowledge.
Best regards.
-
Solaris
- Learning poster
- Posts: 99
- Joined: Sun Apr 06, 2003 5:53 am
- Location: Dhaka, Bangladesh
-
Contact:
Post
by Solaris » Fri Dec 30, 2005 12:03 pm
I agree with Larry. I think 200*200 should be good enough size for the queue. No of enque in one step should be much less than that. No of total enque should always be less than 200*200.
I dont seem to understand the code of shihab that well .. but if you are enqueing the same cell more than once, no matter what size of queue u use, u can at best get TLE, if not RTE.
Where's the "Any" key?
-
shihabrc
- New poster
- Posts: 49
- Joined: Sun Sep 18, 2005 10:20 am
- Location: CSE,BUET
-
Contact:
Post
by shihabrc » Fri Dec 30, 2005 9:09 pm
Its true that my code is a bit clumsy, sorry 4 that. Inside main() i've mostly worked for taking the input and constructing the forest grid(adMat[][]). And no point is enqued more than once, since the entry colour[j] is maintained to check wheather a point adMat[j] was previously visited or not. So,i don't think this would cause a TLE. And still cannot find the reason 4 RTE. Plz hlp.
Shihab
Shihab
CSE,BUET
-
Solaris
- Learning poster
- Posts: 99
- Joined: Sun Apr 06, 2003 5:53 am
- Location: Dhaka, Bangladesh
-
Contact:
Post
by Solaris » Sat Dec 31, 2005 9:04 am
Your code is not clumsy, it just did not match my own spacing tradition
anyway, I went through your code. One reason for getting RTE can be
Your change1[2][4] array is traversed for k = 0 to 7
Where in your code do you consider the euclid distance between two cells ???
While considering the circle covered by JigglePuff it is not necessary that the covered cell will be in one of the eight directions from the center e.g. Let the center is (1,1) and we have loudness L=5, then the cell (2,3) will be dangerous.
Where's the "Any" key?
-
mamun
- A great helper
- Posts: 286
- Joined: Mon Oct 03, 2005 1:54 pm
- Location: Bangladesh
-
Contact:
Post
by mamun » Sat Dec 31, 2005 12:23 pm
Why don't you do what I've suggested? If I'm not very much mistaken then you should get of RTE (don't know about WA though, that's something else).
-
StatujaLeha
- Learning poster
- Posts: 91
- Joined: Tue May 31, 2005 2:01 pm
- Location: Russia
Post
by StatujaLeha » Tue Jan 03, 2006 2:01 am
Hello. I need some help.
This is sample input.
5 5
5
1 2
1 3
1 4
1 5
2 5
1
4 3 1
S - Start
F - Finish
# - border and blacked areas
X - Jigglypuff.
#######
#S#####
#_____##
#______#
#__X___#
#______F#
#######
Did I understand right this sample?
-
Emilio
- Experienced poster
- Posts: 163
- Joined: Sun Oct 17, 2004 8:31 pm
- Location: Murcia, Spain
Post
by Emilio » Tue Jan 03, 2006 2:15 am
Code: Select all
#######
#S#####
#____##
#__#__#
#_#X#_#
#__#_F#
#######
You must take into account Jigglypuff and
its loudness.
Its loudness is circular.
-
StatujaLeha
- Learning poster
- Posts: 91
- Joined: Tue May 31, 2005 2:01 pm
- Location: Russia
Post
by StatujaLeha » Tue Jan 03, 2006 12:12 pm
Emilio, Did I understand right that Euclidean distance is a distance between centers of places?
-
StatujaLeha
- Learning poster
- Posts: 91
- Joined: Tue May 31, 2005 2:01 pm
- Location: Russia
Post
by StatujaLeha » Tue Jan 03, 2006 12:24 pm
Emilio, thanks for you explanation. I got Acc.
-
shihabrc
- New poster
- Posts: 49
- Joined: Sun Sep 18, 2005 10:20 am
- Location: CSE,BUET
-
Contact:
Post
by shihabrc » Tue Jan 17, 2006 11:21 pm
I've changed my code now & has got rid of RTE. But now I'm getting WA. I just don't get it. Can anyone hlp. I've considered curtesian distance between cells while editing the map 4 jiggypuffs.
Code: Select all
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
#define INF 9999999
typedef struct Point{
int r,c;
} Point;
queue<Point> Q;
int row,col;
int map[205][205];
int d[205][205];
int visited[205][205];
int change[2][4];
void i_change(){
change[0][0]=-1;
change[1][0]=0;
change[0][1]=1;
change[1][1]=0;
change[0][2]=0;
change[1][2]=-1;
change[0][3]=0;
change[1][3]=1;
}
void init();
void BFS();
void main(){
int i,j,k,m,p,q,r,nr,nc;
i_change();
while(scanf("%d %d",&row,&col)==2){
if(!row && !col) break;
init();
//taking input of the obstacles and editing the map as necessary
scanf("%d",&m);
for(i=0;i<m;i++){
scanf("%d %d",&j,&k);
map[j][k]=0;
}
scanf("%d",&m);
//taking input 4 jiggypuffs and editing the map as necessary.
//considered curtesian distance
for(i=0;i<m;i++){
scanf("%d %d %d",&p,&q,&r);
nr=p-r;
nc=q-r;
for(j=nr;j<=p+r;j++){
for(k=nc;k<=q+r;k++){
if(j>=1 && j<=row && k>=1 && k<=col){
if(sqrt((j-p)*(j-p) + (k-q)*(k-q)) <=(double)r) map[j][k]=0;
}
}
}
}
if(map[1][1]) BFS();
if(d[row][col]!=INF) printf("%d\n",d[row][col]);
else printf("Impossible.\n");
}
}
void init(){
int i,j;
for(i=1;i<=row;i++){
for(j=1;j<=col;j++){
map[i][j]=1;
visited[i][j]=0;
d[i][j]=INF;
}
}
d[1][1]=0;
visited[1][1]=1;
}
void BFS(){
int j,nr=0,nc=0;
Point p;
p.r=p.c=1;
while(!Q.empty()) Q.pop();
Q.push(p);
while(!Q.empty()){
p=Q.front();
Q.pop();
for(j=0;j<4;j++){
nr=change[0][j]+p.r;
nc=change[1][j]+p.c;
if(nr>=1 && nr<=row && nc>=1 && nc<=col && map[nr][nc]==1 && !visited[nr][nc]){
visited[nr][nc]=1;
d[nr][nc]=d[p.r][p.c]+1;
p.r=nr;
p.c=nc;
Q.push(p);
}
}
}
}
Plz somebody hlp(Sugg,I/Os anything...).
-Shihab
Shihab
CSE,BUET
-
tan_Yui
- Experienced poster
- Posts: 155
- Joined: Sat Jul 10, 2004 12:41 am
Post
by tan_Yui » Thu Jan 19, 2006 1:30 pm
Hi, shihabrc.
I think the main source of your WA is the part of BFS or decision, simply.
And small condition (ex. when the start point and goal point are same) should be added.
Try the following input set.
Code: Select all
1 1
0
0
1 1
1
1 1
0
1 1
0
1
1 1 0
10 10
0
1
3 5 3
5 5
5
1 2
1 3
1 4
1 5
2 5
1
4 3 1
5 5
6
1 2
1 3
1 4
1 5
2 5
3 5
1
4 3 1
6 7
3
4 5
5 4
6 6
2
2 6 1
3 2 1
5 5
5
1 1
1 3
1 4
1 5
2 5
1
4 3 1
5 5
5
5 5
1 3
1 4
1 5
2 5
1
4 3 1
10 10
4
1 5
2 3
4 1
8 10
4
3 2 0
5 6 3
10 1 4
10 8 1
15 15
0
1
7 7 6
0 0
Output is :
Code: Select all
0
Impossible.
Impossible.
18
8
Impossible.
15
Impossible.
Impossible.
Impossible.
Impossible.
Best regards.
-
shihabrc
- New poster
- Posts: 49
- Joined: Sun Sep 18, 2005 10:20 am
- Location: CSE,BUET
-
Contact:
Post
by shihabrc » Sun Jan 22, 2006 2:57 am
Thanx a lt. Got AC.

Shihab
CSE,BUET