TopCoder problem "ExtendableTriangles" used in TCO09 Round 2 (Division I Level Two)



Problem Statement

    

Consider a rectangular grid of points on a plane with N rows and M columns. Each of the points is colored in one of three possible colors: red, green or blue. If we take any three distinct points (even those lying on the same straight line) and join them by line segments, we'll obtain a triangle (possibly degenerate). Such a triangle is called beautiful if all its vertices have distinct colors.

A beautiful triangle A is called extendable if there exists a beautiful triangle B such that A and B have two common vertices and the area of B is strictly greater than the area of A. Note that the area of a degenerate triangle is equal to 0.

You will be given a String grid, containing exactly N elements, representing rows of the grid, from top to bottom. Each element of grid will contain exactly M characters, representing colors of points in the corresponding row, from left to right ('R' for red, 'G' for green and 'B' for blue). Return the number of distinct beautiful extendable triangles that can be formed from points on the given grid. Two triangles are considered distinct if their sets of vertices are distinct.

 

Definition

    
Class:ExtendableTriangles
Method:getCount
Parameters:String[]
Returns:int
Method signature:int getCount(String[] grid)
(be sure your method is public)
    
 

Constraints

-grid will contain between 1 and 50 elements, inclusive.
-Each element of grid will contain between 1 and 50 characters, inclusive.
-All elements of grid will contain the same number of characters.
-Each element of grid will contain only characters 'R', 'G' and 'B'.
 

Examples

0)
    
{"RGB"}
Returns: 0
There's only one degenerate triangle and it's not extendable.
1)
    
{"RGB",
 "RGB"}
Returns: 6
There are 8 beautiful triangles and 6 of them are extendable. These triangles are listed below ('X' means triangle vertex): 
XXX  ...  XX.  ..X  .XX  X..
...  XXX  ..X  XX.  X..  .XX
2)
    
{"RRRRRRRR",
 "GGGGBBBB",
 "RRRRRRRR"}
Returns: 240
There are 256 beatiful triangles. The 16 of them which contain the leftmost green and the rightmost blue points are not extendable. Therefore the answer is 256 - 16 = 240.
3)
    
{"RBRBRBRB",
 "BRBRBRBR",
 "RBRBRBRB",
 "BRBRBRBR",
 "RRRRRRRR",
 "BBBBBBBB",
 "RRRRBBBB",
 "BBBBRRRR"}
Returns: 0
There are no beautiful triangles because there are no green points.
4)
    
{"RGB",
 "RBG",
 "GRB",
 "GBR",
 "BRG",
 "BGR"}
Returns: 208

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13760&pm=10103

Writer:

ivan_metelsky

Testers:

PabloGilberto , Yarin , Olexiy , marian

Problem categories:

Brute Force, Geometry, Greedy