10360  Rat Attack
Moderator: Board moderators

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

 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[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=ud,j=vd;
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[i1][j1]m[g][j1]m[i1][h]>max)
{
max=m[g][h]+m[i1][j1]m[g][j1]m[i1][h];
min_x=u1;
min_y=v1;
}
}
}
printf("%d %d %ld\n",min_x,min_y,max);
t;
}
}[/cpp]
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[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=ud,j=vd;
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[i1][j1]m[g][j1]m[i1][h]>max)
{
max=m[g][h]+m[i1][j1]m[g][j1]m[i1][h];
min_x=u1;
min_y=v1;
}
}
}
printf("%d %d %ld\n",min_x,min_y,max);
t;
}
}[/cpp]

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

 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[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
Cheers!
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
Cheers!

 Learning poster
 Posts: 78
 Joined: Sun Nov 30, 2008 5:00 pm
 Location: IUTOIC, Dhaka, Bangladesh
Re: 10360  Rat Attack
Can anyone help me with some critical input? I am continuously getting WA. Please help.....
May be tomorrow is a better day............

 Learning poster
 Posts: 78
 Joined: Sun Nov 30, 2008 5:00 pm
 Location: IUTOIC, Dhaka, Bangladesh
Re: 10360  Rat Attack
Here is my code. Can anyone tell me what is wrong here? I am getting WA..please help.
Please someone reply........
Code: Select all
removed
May be tomorrow is a better day............

 Experienced poster
 Posts: 147
 Joined: Mon Jun 07, 2010 11:43 am
 Location: University Of Dhaka,Bangladesh
 Contact:
Re: 10360  Rat Attack
sample input:
output:
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
Code: Select all
2 4 21
4 4 21
UVa stats: http://felixhalim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
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[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][j1]+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,jP+1,j)  sum(iP,jP+1,j);
if(cur > best){
best = cur;
X = i;
Y = j;
}
}
}
printf("%d %d %I64d\n",max(0,XD),max(0,YD),best);
}
}
Re: 10360  Rat Attack
you can check whether you met this condition: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?
Code: Select all
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
keep study every day
http://felixhalim.net/uva/hunting.php?id=99497
http://felixhalim.net/uva/hunting.php?id=99497

 New poster
 Posts: 31
 Joined: Thu Nov 24, 2011 12:08 am
Re: 10360  Rat Attack
try this oneArticuno wrote:Can anyone help me with some critical input? I am continuously getting WA. Please help.....
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
Code: Select all
974 974 100000
2 4 21
4 4 21
5 5 30
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:
output:
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
Code: Select all
0 1 10
2 1 30