Connection Status:
Competition Arena > AmoebaCode

AmoebaCode

SRM 493 · 2010-11-01 · by K.A.D.R

SRM 493 · 2010-11-01 · by K.A.D.R · Dynamic Programming
Class Name: AmoebaCode
Return Type: int
Method Name: find
Arg Types: (string, int)
Problem Statement

Problem Statement

Little Romeo likes cosmic amoebas a lot. Recently he found an ancient box, and he believes that there is an amoeba inside it. Unfortunately, the box is protected by a combination lock which contains a row of digits, each between 0 and K, inclusive. The initial combination, from left to right, is given in the String code. Romeo thinks that the lock will open if he replaces each 0 digit with some digit between 1 and K, inclusive, such that the minimal distance between any pair of equal digits is as big as possible. The distance between two numbers in positions A and B, respectively, is |A-B|. Return the maximal possible minimal distance that can be achieved.

Constraints

  • K will be between 1 and 7, inclusive.
  • code will contain between K+1 and 50 characters, inclusive.
  • Each character of code will be a digit between 0 and K, inclusive.

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

Examples
0)
"01"
1
Returns: 1
1)
"1001"
2
Returns: 1

There are only four possible ways to replace the '0's here: 1121 1211 1111 1221 In each of these combinations, the shortest distance between two equal digits is between consecutive equal digits (a distance of 1).

2)
"1010"
2
Returns: 2
3)
"01001"
3
Returns: 3

One possible combination is "31231". There are two pairs of equal digits here. The distance between the two '3's is 3, and the distance between the two '1's is 3.

4)
"10012031001"
3
Returns: 2

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

Coding Area

Language: C++17 · define a public class AmoebaCode with a public method int find(string code, int K) · 114 test cases · 2 s / 256 MB per case

Submitting as anonymous