Connection Status:
Competition Arena > MatchString

MatchString

SRM 398 · 2008-04-15 · by boba5551

SRM 398 · 2008-04-15 · by boba5551 · Greedy, Simple Search, Iteration, String Manipulation
Class Name: MatchString
Return Type: int
Method Name: placeWords
Arg Types: (string, vector<string>)
Problem Statement

Problem Statement

You are given a goal word as a String matchString and puzzle words as a String[] matchWords. The number of puzzle words is equal to the number of letters in the goal word. Assume all letters in all words have the same width and height.


You want to play a game. At the beginning of the game, all the words from matchWords are arranged one below another, in the order that they're given. The words are horizontally aligned so that the first letters of all the words form a vertical line. You may then shift each of the words any number of places (zero or more) to the right, where one place is the width of a single letter. The goal of the game is to shift the puzzle words such that the goal word can be read vertically from top to bottom in a straight line. See examples for clarification.


Your score is the sum of the number of places each puzzle word was shifted. Return the minimal score you can obtain while achieving your goal, or -1 if it is impossible.

Constraints

  • matchWords will contain between 1 and 50 elements, inclusive.
  • Each element of matchWords will contain between 1 and 50 characters, inclusive.
  • Each element of matchWords will contain only uppercase letters ('A'-'Z').
  • matchString will contain the same number of characters as the number of elements in matchWords.
  • matchString will contain only uppercase letters ('A'-'Z').
Examples
0)
"TOP"
{"TIK", 
 "PPPO", 
 "OP"}
Returns: 5

The final arrangement is TIK PPPO OP The first word is shifted 3 places, and the last word is shifted 2 places. In this arrangement, the goal word can be read vertically in the fourth column from the right (shown in bold).

1)
"MUTO"
{"MAMA", "DUDU", "TIT", "EGO"}
Returns: 1
2)
"BAKAR"
{"BATA", "TATA", "OSKAR", "KRAJ", "RAJ"}
Returns: 5
3)
"EEA"
{"GEGA", 
 "TOPCODER", 
 "TEST"}
Returns: -1

The puzzle words must be used in the order they are given, so it is impossible to form the goal word in this case.

4)
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
{"ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABBB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBAB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA"}
Returns: 1225
6)
"AB"
{"ABA", 
 "ABAB"}
Returns: 1

One possible arrangement is ABA ABAB

45)
"FIND"
{"VERYFAST", 
 "OPINION", 
 "SPENDING", 
 "ODD"}
Returns: 3

VERYFAST OPINION SPENDING ODD

46)
"TOP"
{"OUTTHERE", 
 "FROM", 
 "NOPQRSTU"}
Returns: 0

The final arrangement can be made without shifting at all: OUTTHERE FROM NOPQRSTU

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

Coding Area

Language: C++17 · define a public class MatchString with a public method int placeWords(string matchString, vector<string> matchWords) · 98 test cases · 2 s / 256 MB per case

Submitting as anonymous