10360 - Rat Attack

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

Moderator: Board moderators

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

This should work...

Post by junjieliang » Thu Sep 19, 2002 12:35 pm

I haven't solved this problem yet, so this might not work, but it sounds logical enough though...

First, you iterate through every possible point, which will take O(1025*1025) in the worst case. Then for each point, you find the coordinates of the bounding rectangle and assuming you have solved "maximum sum (volume 1)", you will have a O(1) way of seeing how many rats are affected.

Therefore total time is O(n^2).

Hope it works... :D

lskull
New poster
Posts: 1
Joined: Sat Sep 28, 2002 4:41 pm

10360 Rat Attack

Post by lskull » Sat Sep 28, 2002 5:08 pm

Hi.

There is a simple algorithm to solve this problem:

1. Create an array [1025,1025] which will contain how many rats are killed in each point.
2. Iterate each rat, and in each position of the map that kills the nest (ie. the bounding box centered at the nest of size 2d*2d) add the number of rats killed.
3. Go through the array, the maximum gives you the number of rats killed its position the place to put the bomb.

In the worst case possible, it solves in O(1025*1025 + 20000*10000). (400 times faster)

I hope it's clear enough. 8)

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Why I got Runtime Error (SIGSEGV)10360

Post by Ghost77 dimen » Sun Sep 29, 2002 4:43 am

Why I got RunTime Error(SIGSEGV)?

This is my code. :cry: :cry: :cry:

[cpp]#include<stdio.h>
void main(void)
{
int t;
int d,n;
int u,v,i,j,g,h;
int x,y,b,min_x,min_y;
int s[1026][1026];
int m[1026][1026],max;
scanf("%d",&t);
while(t>0)
{
max=0,min_x=0,min_y=0;
for(u=0;u<1026;u++)
{
for(v=0;v<1026;v++)
{
s[v]=0;
m[v]=0;
}
}
scanf("%d%d",&d,&n);
for(u=0;u<n;u++)
{
scanf("%d%d%d",&x,&y,&b);
s[(x+1)][(y+1)]=b;
}
for(u=1;u<1026;u++)
{
for(v=1;v<1026;v++)
{
for(i=1;i<=u;i++)
{
for(j=1;j<=v;j++)
{
m[v]+=s[j];
}
}
}
}
for(u=1;u<1026;u++)
{
for(v=1;v<1026;v++)
{
i=u-d,j=v-d;
g=u+d,h=v+d;
if(i<1)
{
i=1;
}
if(j<1)
{
j=1;
}
if(g>1026)
{
g=1025;
}
if(h>1026)
{
h=1025;
}
if(m[g][h]+m[i-1][j-1]-m[g][j-1]-m[i-1][h]>max)
{
max=m[g][h]+m[i-1][j-1]-m[g][j-1]-m[i-1][h];
min_x=u-1;
min_y=v-1;
}
}
}
printf("%d %d %ld\n",min_x,min_y,max);
t--;
}
}[/cpp]

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Location: BANGLADESH
Contact:

Post by Jalal » Sat Jan 11, 2003 8:11 pm

No need to take such a big array like
int s[1026][1026];
int m[1026][1026]
just take
int s[100][100]
int m[100][100]
then u will over come the prob.
But change the algorithm otherwise
u will see a Time limit exeed :lol:

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen » Sun Jan 12, 2003 10:16 am

Thanks for your reply.

It's a stupid algorithm what I have used.

I have changed it to get a proper time to solve it.

It's the code scipting in early period of my learning programming, and

don't care it too much. Anyway, thanks again.

8)

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

10360 WA - Help Please

Post by playerX » Wed Apr 30, 2003 6:27 pm

[pascal]
Program Mataratos;
Var Ratarray:Array[1..1025,1..1025]Of Integer;
D,N,Px,Py,I:integer;
P:Byte;
mx,my,rk:integer;
MaxX,MaxY:integer;
Procedure Solve;
Var I,J,IC,K,L:Integer;
Begin
mx:=1; my:=1;
For I:=1 To MaxY Do
Begin
For J:=1 To MaxX Do
Begin
IC:=0;
For K:=-D To D Do
For L:=-D To D do
Inc(IC,RatArray[J+k,I+l]);
If rk<IC Then
Begin
rk:=IC;
mx:=J;
my:=I;
End;
If rk=IC Then
Begin
If mx>J Then
Begin
mx:=J;
my:=I;
End;
If mx=J Then
Begin
If my>I Then
Begin
mx:=J;
my:=I;
End;
End;
End;
End;
End;
End;
Begin
ReadLn(Input,D);
ReadLn(Input,N);
Py:=1; Px:=1;
For I:=1 To N Do
Begin
ReadLn(Input,Px,Py,P);
Ratarray[Px,Py]:=P;
If Px > MaxX Then MaxX:=Px;
If Py > MaxY Then MaxY:=Py;
End;
Solve;
WriteLn(mx,' ',my,' ',rk);
End.
[/pascal]

Could somebody tell me why I got WA on this problem? Thanks...

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

Post by playerX » Wed Apr 30, 2003 6:31 pm

[pascal]
Program Mataratos;
Var Ratarray:Array[1..1025,1..1025]Of Integer;
D,N,Px,Py,I:integer;
P:Byte;
mx,my,rk:integer;
MaxX,MaxY:integer;
Procedure Solve;
Var I,J,IC,K,L:Integer;
Begin
mx:=1; my:=1;
For I:=1 To MaxY Do
Begin
For J:=1 To MaxX Do
Begin
IC:=0;
For K:=-D To D Do
For L:=-D To D do
Inc(IC,RatArray[J+k,I+l]);
If rk<IC Then
Begin
rk:=IC;
mx:=J;
my:=I;
End;
If rk=IC Then
Begin
If mx>J Then
Begin
mx:=J;
my:=I;
End;
If mx=J Then
Begin
If my>I Then
Begin
mx:=J;
my:=I;
End;
End;
End;
End;
End;
End;
Begin
ReadLn(Input,D);
ReadLn(Input,N);
Py:=1; Px:=1;
For I:=1 To N Do
Begin
ReadLn(Input,Px,Py,P);
Ratarray[Px,Py]:=P;
If Px > MaxX Then MaxX:=Px;
If Py > MaxY Then MaxY:=Py;
End;
Solve;
WriteLn(mx,' ',my,' ',rk);
End.[/pascal]
I posted it again cause I disabled BBCode on the original thread, sorry.

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

10360 - AC but...

Post by Zyaad Jaunnoo » Sat Apr 30, 2005 4:51 pm

Hi guyz...

Recently I solved 10360 - Rat Attack. It is an old problem and very old posts exist on the board concerning this problem.
I got nearly 1.9s to solve that problem. But there are solutions which used up to 0.12s I think.

Anyway, I dunno if I can get down to 0.12s but I would like to know the best way to solve it. Please help...

My algo is as follows:

initialise array[1025][1025] to 0 on each input set
read the strength of the bomb and the rat populations and taking care not to go out of bound
for (i=0; i<rat populations; i++)
read position (x, y)
x-- and y--
read number of rats at position (x, y)
increment the positions around (x, y) convering a radius given by the strength
end for

Then I iterate through the array to get the maximum sum at position (x, y)

Thats's it... is there a better way to solve this problem? Please advise :wink:

Cheers!

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10360 - Rat Attack

Post by Articuno » Mon May 25, 2009 7:23 pm

Can anyone help me with some critical input? I am continuously getting WA. Please help.....
May be tomorrow is a better day............ :)

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10360 - Rat Attack

Post by Articuno » Tue Jun 09, 2009 11:38 pm

Here is my code. Can anyone tell me what is wrong here? I am getting WA..please help.

Code: Select all

removed
Please someone reply........
May be tomorrow is a better day............ :)

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10360 - Rat Attack

Post by Shafaet_du » Fri Nov 19, 2010 8:39 pm

sample input:

Code: Select all

2

2
4
3 3 7
3 4 6
4 9 12
4 6 8

2
4
3 3 7
3 4 6
4 9 12
6 6 8

output:

Code: Select all

2 4 21
4 4 21

simp1eton
New poster
Posts: 2
Joined: Mon Dec 20, 2010 2:50 pm

Re: 10360 - Rat Attack

Post by simp1eton » Mon Dec 20, 2010 2:54 pm

Can someone help me and see what's wrong with my code? I keep getting WA but i dont know why. Or can someone give me more sample input?

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstring>
#define L 1025
using namespace std;

int T,D,N,X,Y,P;
long long int S[1050][1050],G[1050][1050],R[1050][1050],best,cur;

inline long long int sum(int i,int j1,int j2){
	if(i < 0) return 0;
	if(j1 < 0) return S[i][j2];
	else return (S[i][j2] - S[i][j1] + G[i][j1]);
}

int main(){
	scanf("%d",&T);
	while(T>0){
		--T;
		best = 0;
		memset(S,0,sizeof(S));
		memset(G,0,sizeof(G));
		memset(R,0,sizeof(R));
		scanf("%d%d",&D,&N);
		for(int i=0;i<N;++i){
			scanf("%d%d%I64d",&X,&Y,&cur);
			G[X][Y] = cur;
		}
		for(int i=0;i<=L;++i){
			for(int j=0;j<=L;++j){
				if(!j) S[i][j] = G[i][j];
				else S[i][j] = S[i][j-1]+G[i][j];
			}
		}
		P = 2*D+1;
		for(int j=0;j<=L;++j){
			cur = 0;
			for(int i=0;i<=L;++i){
				cur += sum(i,j-P+1,j) - sum(i-P,j-P+1,j);
				if(cur > best){
					best = cur;
					X = i;
					Y = j;
				}
			}
		}
		printf("%d %d %I64d\n",max(0,X-D),max(0,Y-D),best);
	}
}

surya ss
New poster
Posts: 22
Joined: Sat Jun 11, 2005 7:31 pm

Re: 10360 - Rat Attack

Post by surya ss » Sun May 22, 2011 4:21 am

simp1eton wrote:Can someone help me and see what's wrong with my code? I keep getting WA but i dont know why. Or can someone give me more sample input?
you can check whether you met this condition:
If there is more than one of these best positions then the location with the “minimal” position will be chosen. Positions are ordered first by their x coordinate and second by their y coordinate.

and you don't need long long for this problem the maximum value is only 20000 x 255 = 5100000
for long long the judge is use : %lld not %I64d

hope it help

mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

Re: 10360 - Rat Attack

Post by mostafiz93 » Tue Apr 17, 2012 12:31 am

Articuno wrote:Can anyone help me with some critical input? I am continuously getting WA. Please help.....
try this one
input:

Code: Select all

4
50
4
0 0 1000
1024 1024 100000
0 1024 10000
1024 0 10000

2
4
3 3 7
3 4 6
4 9 12
4 6 8

2
4
3 3 7
3 4 6
4 9 12
6 6 8

1
2
4 4 10
6 6 20
output:

Code: Select all

974 974 100000
2 4 21
4 4 21
5 5 30

bill8124
New poster
Posts: 8
Joined: Fri Jan 21, 2011 8:13 am

Re: 10360 - Rat Attack

Post by bill8124 » Sun Mar 10, 2013 7:20 pm

I think going through the array is slow because there might be many entry which is 0. My method is similar to lskull's but more faster:
1. Create an array [1025,1025], each entry contains how many rats will be killed if we put the bomb at this location.
2. Maintain best location (x, y) for bomb, initialized to (0, 0)
3. For each input of rat population, update the array and check whether this location is best or not while updating.
4. No need to go through the array. We already got the answer after all input was read.

Time Complexity: O(N x d x d) (N: number of rat population input / d: bomb strength)

input:

Code: Select all

2
2
1
2 3 10
2
2
3 2 10
4 3 20
output:

Code: Select all

0 1 10
2 1 30

Post Reply

Return to “Volume 103 (10300-10399)”