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

 

Definition

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

Notes

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

Constraints

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

Examples

0)
    
{"25,25,25"}
Returns: 3
Only one pixel is lit, and it requires 3 lasers to be displayed.
1)
    
{"25,25,25","25,25,26"}
Returns: 5
2 pixels are lit, but share the same XY laser at point (25,25), so only 5 lasers are lit.
2)
    
{"25,25,25","25,25,26","25,26,26","25,26,25"}
Returns: 8
3)
    
{"1000,1005,20","20,50,20","30,90,10","1005,30,90",
 "90,1000,1005","30,90,20","1000,90,10","40,90,10",
 "1000,1000,1000"}
Returns: -1
4)
    
{"1,1,3","1,3,1","3,1,1"}
Returns: -1
These three pixels cannot be lit without lighting the pixel (1,1,1), so return -1.
5)
    
{"1,1,3","1,3,1","3,1,1","1,1,1"}
Returns: 9
The previous example, with (1,1,1) activated to make it possible.
6)
    
{"938,134,626","1015,310,957","427,741,13","388,513,56",
"914,169,526","716,540,478","796,461,500","506,886,866",
"44,185,744","474,104,631","557,402,744","992,132,804",
"440,499,122","895,845,612","711,576,984","281,846,475",
"781,620,301","305,632,954","874,659,36","17,978,393",
"765,481,372","612,316,8","902,281,515","272,125,1012",
"413,513,987","595,940,1014","858,1019,100","899,554,613",
"226,995,592","793,939,286","386,41,212","111,899,737",
"339,199,117","1014,710,638","413,187,56","301,691,368",
"387,285,286","546,356,739","366,356,660","877,461,737",
"538,301,629","707,116,7","701,730,70"}
Returns: -1
7)
    
{"286,596,559","502,325,84","303,56,960","28,678,821",
"542,57,303","233,418,91","13,520,124","645,129,889",
"438,433,951","835,953,56","921,531,943","416,159,446",
"513,426,1018","778,486,254","132,380,822","828,351,787",
"659,531,866","893,140,419","603,721,110","888,144,689",
"861,869,515","632,912,973","435,828,676","526,365,850",
"162,860,173","637,910,701","169,21,311","431,722,798",
"674,663,1012","451,343,584","132,380,1000","184,720,1011"}
Returns: 95
8)
    
{"1,0,0","4,1,2","0,2,0","0,0,0","4,4,3","2,3,2","0,4,3",
"4,2,3","4,4,1","2,2,0","4,1,1","4,0,1","1,0,2","1,3,2",
"0,2,3","4,0,2","2,2,3"}
Returns: 31

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4664&pm=1929

Writer:

chogyonim

Testers:

lbackstrom , brett1479

Problem categories:

Brute Force, String Parsing