Connection Status:
Competition Arena > ABBADiv1

ABBADiv1

SRM 663 · 2015-06-30 · by zxqfl

SRM 663 · 2015-06-30 · by zxqfl · Brute Force, Greedy, Simulation, String Manipulation
Class Name: ABBADiv1
Return Type: String
Method Name: canObtain
Arg Types: (string, string)
Problem Statement

Problem Statement

One day, Jamie noticed that many English words only use the letters A and B. Examples of such words include "AB" (short for abdominal), "BAA" (the noise a sheep makes), "AA" (a type of lava), and "ABBA" (a Swedish pop sensation).


Inspired by this observation, Jamie created a simple game. You are given two Strings: initial and target. The goal of the game is to find a sequence of valid moves that will change initial into target. There are two types of valid moves:

  • Add the letter A to the end of the string.
  • Add the letter B to the end of the string and then reverse the entire string. (After the reversal the newly-added B becomes the first character of the string).

Return "Possible" (quotes for clarity) if there is a sequence of valid moves that will change initial into target. Otherwise, return "Impossible".

Constraints

  • The length of initial will be between 1 and 49, inclusive.
  • The length of target will be between 2 and 50, inclusive.
  • target will be longer than initial.
  • Each character in initial and each character in target will be either 'A' or 'B'.
Examples
0)
"A"
"BABA"
Returns: "Possible"

Jamie can perform the following moves: Initially, the string is "A". Jamie adds a 'B' to the end of the string and then reverses the string. Now the string is "BA". Jamie adds a 'B' to the end of the string and then reverses the string. Now the string is "BAB". Jamie adds an 'A' to the end of the string. Now the string is "BABA". Since there is a sequence of moves which starts with "A" and creates the string "BABA", the answer is "Possible".

1)
"BAAAAABAA"
"BAABAAAAAB"
Returns: "Possible"

Jamie can add a 'B' to the end of the string and then reverse the string.

2)
"A"
"ABBA"
Returns: "Impossible"
3)
"AAABBAABB"
"BAABAAABAABAABBBAAAAAABBAABBBBBBBABB"
Returns: "Possible"
4)
"AAABAAABB"
"BAABAAABAABAABBBAAAAAABBAABBBBBBBABB"
Returns: "Impossible"

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

Coding Area

Language: C++17 · define a public class ABBADiv1 with a public method string canObtain(string initial, string target) · 91 test cases · 2 s / 256 MB per case

Submitting as anonymous