TopCoder problem "FullMonitor" used in CRPF Charity Finals (Division I Level One)

Problem Statement


A company is developing a 3-dimensional computer monitor. The monitor has a resolution of 1024 by 1024 by 1024 pixels. The monitor is a cube, with a grid of lasers on three sides of the cube, all of which share an edge (that is, no grid is on the face directly opposite another grid). As a result, one of these grids is in the XY-plane of the monitor, another is in the YZ-plane, and the third is in the XZ-plane. To "light up" a pixel, the laser on each grid which corresponds to the pixel's coordinate needs to be on, and the intersection of these three lasers is what creates the point of light.

Create a class FullMonitor containing a method numLasers which takes as an argument a String[] pixels, representing the lit pixels, and returns the total number of lasers that must be activated. If the given String[] of pixels cannot be turned on without turning on other pixels (see example 4) then return -1.

For example, if we wish to light the point (4,4,3), the XY-plane would have to light up the laser at (4,4), the YZ-plane would have to light up the laser at (4,3), and the XZ-plane would have to light up the laser at (4,3). In total, 3 lasers would have to be activated. If we were to then light the point (4,3,3), the following lasers would have to be activated: XY-plane (4,3), YZ-plane (3,3), XZ-plane (4,3). Since the XZ-plane's (4,3) laser is already activated, a total of 5 lasers would have to be activated.

Each element of pixels is formatted as (quotes added for clarity) "X,Y,Z" where X, Y, and Z are the respective coordinates of the pixel. Each coordinate is an integer between 0 and 1023 inclusive (with no extra leading zeroes).



Method signature:int numLasers(String[] pixels)
(be sure your method is public)


-Each laser grid has 1024*1024=1048576 lasers, for a total of 3145728 possible activated lasers. However, this situation requires more lit pixels than can be represented using the input.


-pixels will contain between 0 and 50 elements, inclusive.
-each element of pixels will be formatted as (quotes added for clarity) "X,Y,Z" where X, Y, and Z are integers between 0 and 1023, inclusive, with no extra leading zeroes
-each element of pixels will be unique.


Returns: 3
Only one pixel is lit, and it requires 3 lasers to be displayed.
Returns: 5
2 pixels are lit, but share the same XY laser at point (25,25), so only 5 lasers are lit.
Returns: 8
Returns: -1
Returns: -1
These three pixels cannot be lit without lighting the pixel (1,1,1), so return -1.
Returns: 9
The previous example, with (1,1,1) activated to make it possible.
Returns: -1
Returns: 95
Returns: 31

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories:

Brute Force, String Parsing