Connection Status:
Competition Arena > SubrectanglesOfTable

SubrectanglesOfTable

SRM 429 · 2008-12-11 · by darnley

SRM 429 · 2008-12-11 · by darnley · Simple Math, Simple Search, Iteration
Class Name: SubrectanglesOfTable
Return Type: long[]
Method Name: getQuantity
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Tanya has a rectangular table filled with letters.

First, she makes four copies of this table, and arranges the copies as a 2×2 rectangle.

Then she lists all subrectangles of the resulting table.

For example, for the following original table:

OK

she will arrange the copies like this:

OKOK
OKOK
and then she will list the following 30 subrectangles (dots for clarity only): 
OKOK .... OKOK OKO. .... OKO. .KOK .... .KOK
OKOK OKOK .... OKO. OKO. .... .KOK .KOK ....

OK.. .... OK.. .KO. .... .KO. ..OK .... ..OK 
OK.. OK.. .... .KO. .KO. .... ..OK ..OK .... 

O... .... O... .K.. .... .K.. ..O. .... ..O. ...K .... ...K 
O... O... .... .K.. .K.. .... ..O. ..O. .... ...K ...K ....

(Note that she is considering all subrectangles based on their positions rather than their content, so the same subrectangle might appear multiple times in the list. In this case, subrectangle "K" appears four times because it occurs at four different positions.)

Tanya wonders how frequently each letter of the alphabet occurs among all these subrectangles. You are given a String[] table, where the j-th character of the i-th element is the letter at row i, column j of the original table. Return a long[] containing exactly 26 elements, where the i-th element is the number of occurrences of the i-th letter in the alphabet among all of Tanya's subrectangles. 'A' is the 0-th letter, 'B' is the 1-st letter, etc.

Constraints

  • table will contain between 1 and 50 elements, inclusive.
  • Each element of table will contain between 1 and 50 characters, inclusive.
  • Each element of table will contain the same number of characters.
  • Each element of table will contain only uppercase letters ('A'-'Z').
Examples
0)
{"OK"}
Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 40, 0, 0, 0, 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

The 30 Tanya's rectangles are listed above. There is a total of 40 Ks and 40 Os in these rectangles.

1)
{"TOPCODER"}
Returns: {0, 0, 448, 432, 400, 0, 0, 0, 0, 0, 0, 0, 0, 0, 848, 432, 0, 352, 0, 352, 0, 0, 0, 0, 0, 0 }
2)
{"GOOD", "LUCK"}
Returns: {0, 0, 320, 280, 0, 0, 280, 0, 0, 0, 280, 280, 0, 0, 640, 0, 0, 0, 0, 0, 320, 0, 0, 0, 0, 0 }

The four copies form the following table: GOODGOOD LUCKLUCK GOODGOOD LUCKLUCK Tanya lists 360 rectangles that contain a total of 320 Cs, 280 Ds, 280 Gs, 280 Ks, 280 Ls, 640 Os, and 320 Us.

3)
{"TANYA",
 "HAPPY",
 "BIRTH",
 "DAYYY"}
Returns: {5168, 1280, 0, 1120, 0, 0, 0, 2560, 1472, 0, 0, 0, 0, 1344, 0, 3008, 0, 1536, 0, 2592, 0, 0, 0, 0, 6320, 0 }
4)
{"Z"}
Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16 }

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

Coding Area

Language: C++17 · define a public class SubrectanglesOfTable with a public method vector<long long> getQuantity(vector<string> table) · 83 test cases · 2 s / 256 MB per case

Submitting as anonymous