Connection Status:
Competition Arena > ExtendableTriangles

ExtendableTriangles

TCO09 Round 2 · 2009-02-24 · by ivan_metelsky

TCO09 Round 2 · 2009-02-24 · by ivan_metelsky · Brute Force, Geometry, Greedy
Class Name: ExtendableTriangles
Return Type: int
Method Name: getCount
Arg Types: (vector<string>)
Problem Statement

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.

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

Submissions are judged against all 150 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ExtendableTriangles with a public method int getCount(vector<string> grid) · 150 test cases · 2 s / 256 MB per case

Submitting as anonymous