Connection Status:
Competition Arena > ApplesAndPears

ApplesAndPears

SRM 623 · 2013-12-22 · by standy

SRM 623 · 2013-12-22 · by standy · Brute Force
Class Name: ApplesAndPears
Return Type: int
Method Name: getArea
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

A square board is divided into N rows by N columns of unit square cells. Some cells of the board are empty. Each of the other cells contains either an apple or a pear. You are given the current state of the board as a String[] board. In board, the character '.' denotes an empty cell, 'A' denotes an apple, and 'P' denotes a pear.

You are allowed to perform at most K moves. In each move, you can pick up one fruit (an apple or a pear) and place it onto any empty cell. (The new cell doesn't have to be adjacent to the old one.) Note that you cannot remove fruit from the board, you are only allowed to move it onto different cells.

A rectangular section of the board is called uniform if all cells in the rectangle are the same: that is, either all those cells contain apples, or they all contain pears, or all of them are empty. After you are done moving the fruit, you want to have a uniform rectangle that is as large as possible somewhere on the board. Return the largest possible area of such a rectangle.

Constraints

  • N will be between 1 and 50, inclusive.
  • board will contain exactly N elements.
  • Each element of board will contain exactly N characters.
  • Each character in board will be '.', 'A', or 'P'.
  • K will be between 0 and 1000, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{".A",
 "P."}
0
Returns: 1

As K=0, you are not allowed to make any moves. Currently, the largest uniform rectangle is just a single cell.

1)
{".A",
 "P."}
1
Returns: 2

Move any piece of fruit onto any of the two currently empty cells. After the move, there will be two adjacent empty cells. These form a 2x1 uniform rectangle.

2)
{".PP", 
 "PPA", 
 "PAP"}
3
Returns: 6

In three moves, you can create a 3x2 rectangle of cells that contain pears.

3)
{"A.P.PAAPPA",
 "PPP..P.PPP",
 "AAP.A.PAPA",
 "P.PA.AAA.A",
 "...PA.P.PA",
 "P..A.A.P..",
 "PAAP..A.A.",
 "PAAPPA.APA",
 ".P.AP.P.AA",
 "..APAPAA.."}
10
Returns: 21
4)
{"AP",
 "PA"}
2
Returns: 1

This case is special as there is no empty cell.

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

Coding Area

Language: C++17 · define a public class ApplesAndPears with a public method int getArea(vector<string> board, int K) · 66 test cases · 2 s / 256 MB per case

Submitting as anonymous