Connection Status:
Competition Arena > TheKingsArmyDiv1

TheKingsArmyDiv1

SRM 643 · 2014-08-25 · by Witaliy

SRM 643 · 2014-08-25 · by Witaliy · Brute Force, Dynamic Programming, Greedy, Simple Search, Iteration
Class Name: TheKingsArmyDiv1
Return Type: int
Method Name: getNumber
Arg Types: (vector<string>)
Problem Statement

Problem Statement

The King of Byteland has an army. The army consists of 2N soldiers. The King has arranged the soldiers into 2 rows by N columns. Two soldiers are neighbors if they are located next to each other in a row or in a column.

Currently, some of the soldiers are happy and some are sad. You are given the current states of all soldiers in a String[] state. For each i and j, state[i][j] is 'H' if soldier in row i, column j is happy, or 'S' if that soldier is sad. (All indices are 0-based.)

The King knows that a happy army is a strong army, therefore he wants all his soldiers to be happy. The soldiers can talk to other soldiers. Whenever soldier X talks to soldier Y, soldier Y changes his state to the state of soldier X. For example, if X is currently sad, Y becomes sad as well. The state of soldier X does not change when X talks to Y.

You can now give some soldiers orders to talk to other soldiers. There are three types of valid orders:

  1. Choose a single soldier and call him X. Choose a single neighbor of X and call him Y. X will talk to Y.
  2. Choose any contiguous group of soldiers in one of the rows. Each of these soldiers will talk to their neighbor in the other row.
  3. Choose any column A. Choose any column B adjacent to column A. Each soldier in column A will talk to their neighbor in column B.

You are given the String[] state. Return the smallest non-negative integer X such that there is a sequence of X valid orders such that after the orders are executed, one after another, all the soldiers will be happy. If there is no such sequence of orders, return -1 instead.

Constraints

  • N will be between 1 and 200, inclusive.
  • state will contain exactly 2 elements.
  • Each element of state will contain exactly N characters.
  • Each element of state will consist of characters 'H' and 'S'.
Examples
0)
{"HSH", 
 "SHS"}
Returns: 2

Here is one optimal solution: First, give an order of the first type, choosing the soldier in row 1, column 1 (0-based indices) as X and the soldier in row 0, column 1 as Y. Next, give an order of the second type, choosing the entire row 0.

1)
{"HH", 
 "HH"}
Returns: 0

All soldiers are already happy, hence the answer is 0.

2)
{"HHHHH", 
 "HSHSH"}
Returns: 1

One optimal solution is to give an order of the second type, choosing soldiers in columns 1 through 3 in row 0.

3)
{"S", 
 "S"}
Returns: -1

It is impossible to achieve the goal in this case.

4)
{"HSHHSHSHSHHHSHSHSH", 
 "SSSSHSSHSHSHHSSSSH"}
Returns: 8

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

Coding Area

Language: C++17 · define a public class TheKingsArmyDiv1 with a public method int getNumber(vector<string> state) · 135 test cases · 2 s / 256 MB per case

Submitting as anonymous