TopCoder problem "CrouchingAmoebas" used in SRM 493 (Division II Level Three)



Problem Statement

    Little Romeo is being attacked by amoebas crouching on the floor of his room. His room can be represented as a Cartesian plane, and the amoebas can be represented as points on that plane. You are given int[]s x and y, where the i-th amoeba is at point (x[i], y[i]). Multiple amoebas can exist at the same coordinates.



To escape, Romeo must destroy as many amoebas as possible. He has two powers at his disposal. First, he can choose one amoeba and move it along either of the axes by one unit. He can do this at most T times, choosing any amoeba each time. Then, he can choose an AxA square on the plane and use his SuperAmoebaDestroyer to destroy all amoebas inside or on the border of that square. The square must have sides parallel to the axes.



Return the maximum number of amoebas Romeo can destroy.
 

Definition

    
Class:CrouchingAmoebas
Method:count
Parameters:int[], int[], int, int
Returns:int
Method signature:int count(int[] x, int[] y, int A, int T)
(be sure your method is public)
    
 

Constraints

-x and y will each contain between 1 and 30 elements, inclusive.
-x and y will have the same number of elements.
-Each element of x and y will be between -1,000,000,000 and 1,000,000,000, inclusive.
-A will be between 1 and 1,000,000,000, inclusive.
-T will be between 1 and 15, inclusive.
 

Examples

0)
    
{0,0}
{0,1}
1
1
Returns: 2
All the amoebas are already in a 1x1 square, so Romeo can immediately use the SuperAmoebaDestroyer without having to move any amoebas.
1)
    
{0,1,2}
{1,2,0}
1
1
Returns: 2
Romeo can't put all the amoebas in a 1x1 square in one move.
2)
    
{0,1,2}
{1,2,0}
1
2
Returns: 3
Moving the last amoeba left and then up puts all the amoebas in the 1x1 square with lower left corner at (0,1).
3)
    
{0,0,3,3}
{0,3,0,3}
2
4
Returns: 4
4)
    
{-1000000000,1000000000}
{-1000000000,1000000000}
1
15
Returns: 1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11214

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14422&pm=11214

Writer:

maksay

Testers:

PabloGilberto , ivan_metelsky , K.A.D.R

Problem categories:

Geometry, Search