Connection Status:
Competition Arena > EllysRansom

EllysRansom

2021 TCO 1A · 2021-04-13 · by espr1t

2021 TCO 1A · 2021-04-13 · by espr1t · Graph Theory
Class Name: EllysRansom
Return Type: String
Method Name: getRansom
Arg Types: (string, string, string)
Problem Statement

Problem Statement

Elly wants to send a ransom note. And everybody knows how to produce a proper ransom note: by cutting out letters from a newspaper and pasting them to a sheet of paper.


Elly has one page from a newspaper as her source of letters. Her page has text on both sides and she can use letters from both sides in the ransom note. But, of course, once she cuts out a letter and glues it to the ransom note, she can no longer use the letter that was on the other side of that piece of paper.

The letters in Elly's newspaper are perfectly aligned: whenever she cuts out a letter from the page, the cutout will have exactly one letter on the other side as well.


The girl has asked you to help her find one possible way in which she can produce the desired ransom note.

You will be given the Strings A, B and T.

The Strings A and B both have the same length N. These strings describe the newspaper page: A are the letters on the front side and B are the corresponding letters on the back side of the page. The order of letters in A and B is such that for each index i the letters A[i] and B[i] are opposite each other.

The String T is the text of the ransom note Elly wants to write.


Return a string of N characters. For each i, character i of the returned string must be one of A[i], B[i] and '_' (underscore). Here, A[i] and B[i] mean that you are using that character somewhere in the ransom note and '_' means that this character will remain unused.

A solution is valid if T can be obtained by rearranging the letters that appear in the returned string. Any valid solution will be accepted. If no valid solution exists, return "NO SOLUTION" instead (quotes for clarity).

Constraints

  • A and B will each contain between 1 and 1000 characters, inclusive.
  • A and B will contain the same number of characters.
  • T will contain between 1 and N characters, inclusive, where N is the number of characters in A.
  • All strings will contain only uppercase letters from the English alphabet ({'A'-'Z'}).
Examples
0)
"GOODLUCKANDHAVEFUNN"
"RPSETSUJMITITUOHTIW"
"TOPCODER"
Returns: "RPOET_C___D___O____"

The answer "RPOET_C___D___O____" is one of multiple valid answers for this test case. According to this answer, we take the letters 'R' and 'P' from the back side of the page, 'O' from the front, 'E' and 'T' from the back, then we skip a letter, then we take 'C' from the front, skip 3 more letters, take a 'D' from the front, skip 3 more letters, and finally we take an 'O' from the back of the page. In total, we have cut out exactly eight letters: R, P, O, E, T, C, D, O. These can be rearranged to spell "TOPCODER" exactly.

1)
"HELP"
"ELLY"
"HELL"
Returns: "NO SOLUTION"

The last letter is useless: we do not need 'P' or 'Y' for our ransom note. The other three letters are not enough to form a four-letter ransom note.

2)
"NEVERMINDTHENOISEYOUHEARD"
"DEBRUOYREDNUTSAEBATSUJSTI"
"ENTERSANDMANYEAH"
Returns: "NE_ERMYNDTHENSA__A____A__"
3)
"THISWASATRIUMPHIMMAKINANOTEHEREHUGE"
"EVILALLITSERAOHWELPOEPEHTROFSSECCUS"
"APERTURESCIENCEPORTALHASEVILTESTS"
Returns: "TVISALSATRERAPHIELPOENE_TTE_SRECCUS"
4)
"GOODLUCKANDHAVEFUNN"
"WITHOUTITIMJUSTESPR"
"TOPCODER"
Returns: "_OTDO_C_______E__PR"

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 EllysRansom with a public method string getRansom(string A, string B, string T) · 114 test cases · 2 s / 256 MB per case

Submitting as anonymous