Connection Status:
Competition Arena > BlockDistance

BlockDistance

SRM 306 · 2006-06-08 · by soul-net

SRM 306 · 2006-06-08 · by soul-net · Dynamic Programming
Class Name: BlockDistance
Return Type: int
Method Name: minDist
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

The block distance from oldText to newText is defined as the least number of block insertions in oldText that are needed to make it equal to newText. A block insertion into oldText is the insertion of any string at any position. For example, if oldText is "herld" a possible block insertion is inserting "llo wo" before the 'r' which will give "hello world".

As an example, if oldText is "hello goodbye" and newText is "hello, how are you? goodbye have a nice day", the block distance between them is 2 because by inserting ", how are you? " and " have a nice day" properly, we can make oldText equal to newText.

You will be given oldText and newText as two String[]s. You must first concatenate all the elements within each of them to form two long strings, and then return the block distance between them. If there is no way to make oldText equal to newText using only block insertions, return -1.

Constraints

  • oldText and newText will each have between 1 and 20 elements, inclusive.
  • Each element of oldText and newText will have between 1 and 50 characters, inclusive.
  • Each character of each element of oldText and newText will have an ASCII value between 32 and 126, inclusive.
Examples
0)
{"hello goodbye"}
{"hello, how are you? goodbye have a nice day"}
Returns: 2

The example from the problem statement.

1)
{"aaaaa"}
{"ababababa"}
Returns: 4

Every b has to be added in a different block.

2)
{"aaaaaaaaaaaaaaaa"}
{"aaaaaaaaaaaaaaaa","t","aaaaaaaaaaaaaaaa"}
Returns: 1
3)
{"no way"}
{"No way!"}
Returns: -1
4)
{"x"}
{"x"}
Returns: 0
7)
{"abce","f","ij","klm","n","op","uvwx","z"}
{"ab","cdefg","hijklmnop","q","rs","tuv","wxyz"}
Returns: 4

You need to insert "d" before the 'e', "gh" before the 'i', "qrst" before the 'u' and "y" before the 'z'.

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

Coding Area

Language: C++17 · define a public class BlockDistance with a public method int minDist(vector<string> oldText, vector<string> newText) · 101 test cases · 2 s / 256 MB per case

Submitting as anonymous