TSOC '16 Contest 2 #2 - Oh My!

View as PDF
Submit solution
Points: 10
Time limit: 2.5s
Memory limit: 256M
Authors:
bobhob314, moladan123, kobortor, gah111
Problem types

George Takei is busy writing a new screenplay. He wishes to finish it in time for April 20, a very significant day for him. While he has finished the rough draft, it is too full of errors to use. Help him correct it before the deadline! George knows that you can't fix everything, but you can at least help him trim his draft a little.

The only words the script should contain are variations on the phrase ohmy. Some letters may be duplicated, but this is okay as long as they are still in order (George needs to have good inflection, after all), so the phrases ooohhhhmmmyyyy and oooooooooooooooooooohmy, for example, are also valid ohmy phrases. Your task is to remove the minimum possible amount of letters needed to produce a screenplay with the maximum possible number of ohmy phrases. Additionally, every character in the screenplay must be a valid part of one of these phrases.

Input Specification

The first line of input is n (1 \le n \le 25), the number of characters in the screenplay. The second line of input contains the text of the screenplay in lowercase. There are no spaces.

Output Specification

An ohmy phrase, where the number of h's is the maximum possible number of ohmy phrases in the screenplay, and the number of y's is the minimum number of characters that must be removed. Note that an ohmy phrase must have a positive integer for the number of each letter. If 0 deletions are needed or there are 0 ohmy phrases in the screenplay, omit the corresponding letter in your output, but know that your output is not an actual ohmy phrase.

Sample Input 1

25
ohmyohhhhhmyyyhohmyohqqmy

Sample Output 1

ohhhhmyyy

Explanation of Sample Output 1

The sample input contains three errors:

ohmyohhhhhmyyyhohmyohqqmy

With these errors removed, the phrase becomes:

ohmyohhhhhmyyyohmyohmy

Which separates into four ohmy phrases:

ohmy-ohhhhhmyyy-ohmy-ohmy

Sample Input 2

22
ohhhhhhhhhohmymyohmymy

Sample Output 2

ohhmyyy

Explanation of Sample Output 2

The maximum number of ohmy phrases this screenplay could contain is two, so two h's are outputted. The best way to create a valid screenplay is by deleting three characters:

ohhhhhhhhhohmymyohmymy

Leaving:

ohhhhhhhhhhmyyohmmy

Which separates into two ohmy phrases:

ohhhhhhhhhhmyy-ohmmy

Comments


  • 1
    bobhob314  commented on April 21, 2016, 11:41 p.m.

    The test cases have been updated. Good thing the contest wasn't rated. Thanks for the heads up Fatal


  • -1
    bobhob314  commented on April 20, 2016, 11:19 p.m.

    I noticed someone's code had a comment,

    Minimize deletions and then maximize number of ohmys

    Actually, the opposite is true. The number of ohmys must be maximized first.


  • 3
    d  commented on April 20, 2016, 9:29 p.m.

    Should I remove 3 characters to get 1 phrase, or 8 characters to get 2 phrases?

    Should the answer be "ohhmyyy"? (max phrases + min characters removed)


    • 1
      moladan123  commented on April 20, 2016, 10:24 p.m.

      Maximize the number of phrases, then find minimal deletions to get to that maximum phrase.