TopCoder problem "LargestGap" used in SRM 402 (Division I Level Two)



Problem Statement

    

Given a String[] board, concatenate all its elements, in order, to get a single string representing a circular board consisting of uppercase 'X' and '.' characters. "Circular" means that the first and the last characters on the board are consecutive. Maximal consecutive groups of 'X' characters form blocks and maximal consecutive groups of '.' characters form gaps. The size of the gap is the number of '.' characters in it.

You want to remove exactly one block from the board, getting a circular board of smaller size. For each possible block to be removed consider the board after its removal, construct an array of all gaps' sizes on the board and sort this array in non-ascending order. Choose the block for which the described array is lexicographically maximal (see notes for the description of lexicographical array comparison). Return the smallest 0-based index among all characters in this block (indices are taken in the concatenated string). In case of a tie choose the block which results in the smallest return value.

 

Definition

    
Class:LargestGap
Method:getLargest
Parameters:String[]
Returns:int
Method signature:int getLargest(String[] board)
(be sure your method is public)
    
 

Notes

-Let int[]s A and B contain the same number of elements. Then A is lexicographically larger than B if A contains a larger value at the first position where A and B differ.
 

Constraints

-board will contain between 1 and 50 elements, inclusive.
-Each element of board will contain between 1 and 50 characters, inclusive.
-board will contain only uppercase 'X' and '.' characters.
-board will contain at least two blocks.
 

Examples

0)
    
{".....X.X......."}
Returns: 5
Remove the first block.
1)
    
{"XXXX","....","XXXX","....","XXXX","...."}
Returns: 0

There are three blocks whose smallest indices are 0, 8, 16, respectively.

The board after removing each of the blocks look as follows:

  • The 1st block: "....XXXX....XXXX....".
  • The 2nd block: "XXXX........XXXX....".
  • The 3rd block: "XXXX....XXXX........".

All three results produce the same gaps array {8,4}. So we return the smallest index among {0,8,16}.

2)
    
{"XXX.........XX...........XX..X"}
Returns: 12
There are three gaps and three blocks (recall that the board is circular).
3)
    
{"XXX","X.....","....XX..XXXXXX","X........X..",".XXX."}
Returns: 32
There are 5 blocks and 5 gaps. There are two ways to maximize the largest gap, but only one of them also maxmizes the second largest one.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12174&pm=8508

Writer:

srbga

Testers:

PabloGilberto , Olexiy , ivan_metelsky , Gassa

Problem categories:

Brute Force, Greedy, String Manipulation