10360 - Rat Attack

[junjieliang]

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]

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]

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=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]

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

[Ghost77 dimen]

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.

[playerX]

[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]

[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]

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!

[Articuno]

Can anyone help me with some critical input? I am continuously getting WA. Please help.....

[Articuno]

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

[Shafaet_du]

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]

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]

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

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]

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]

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