## 10360 - Rat Attack

Moderator: Board moderators

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

### This should work...

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... lskull
New poster
Posts: 1
Joined: Sat Sep 28, 2002 4:41 pm

### 10360 Rat Attack

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. Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

### Why I got Runtime Error (SIGSEGV)10360

Why I got RunTime Error(SIGSEGV)?

This is my code.   [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;
int m,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
Contact:
No need to take such a big array like
int s;
int m
just take
int s
int m
then u will over come the prob.
But change the algorithm otherwise
u will see a Time limit exeed Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

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. playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

### 10360 WA - Help Please

[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
Py:=1; Px:=1;
For I:=1 To N Do
Begin
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
[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
Py:=1; Px:=1;
For I:=1 To N Do
Begin
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.

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

### 10360 - AC but...

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 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++)
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 Cheers!

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 10360 - Rat Attack

May be tomorrow is a better day............ Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 10360 - Rat Attack

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

Code: Select all

``removed``
May be tomorrow is a better day............ Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10360 - Rat Attack

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

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,G,R,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

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

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

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
``````