The problem is about matching pairs of rhymes. Apparently we know that the poems in this alien language only ever use each rhyming-ending twice. Or maybe it's that we want to see how complex the rhyme scheme could be, in terms of different rhyming endings. Since rhymes are determined based on the location of an accent in the word, and we don't know where the accents go, you are placing the accents anywhere and trying to determine the maximum number of rhymes possible as a way of helping to decide whether these words are from a poem. Here's the relevant text from the problem:
You believe that you can discard zero or more of these words, assign accented letters to the remaining words, and then arrange those words into pairs such that *each word rhymes only with the other word in its pair, and with none of the words in other pairs.* You want to know the largest number of words that can be arranged into pairs in this way. Example: Suppose you get the words bent, cent, dent, gent, lent, rent, recent, sent, scent, tent, and went. You can make two words rhyme with ending t, two with nt, two with ent, and two with cent. You will have three leftover words, but no more common endings which are not already used, so you can't make another pair even though the words have a common ending. Using the method of working from longest ending to shortest, you won't find any matches until you get to cent. There are three there, and you use and eliminate two and move on to the next ending. Then you get to ent, nt, and t, each of which have all the remaining words at that time. You use two each time, any two, and move on. When you are done, you have three words, each of which ends with t, nt, ent, and maybe even one of them with cent, but you are not allowed to rhyme more than two words with any ending, so you can't use them. If ascent was added to the list, you could rhyme ascent with scent (based on the ending scent), recent with cent, and three more pairs with the shorter endings, allowing you to use 10 words, but you would still have two left over which match their final three letters but can't be used because they don't have any common endings that are not already used. On Tue, Apr 23, 2019 at 2:04 PM Lasse <[email protected]> wrote: > I was playing with the question Alien Rhyme in round 1a 2019 and found > something strange. Please correct me if I was wrong or remind me when it > is already discussed. > > I tried to collect all matched rhymes and select from longest to > shortest, but when I filter all matched (with rhyme), the small dataset > failed; but when I removed only the first two matched words, at least > the small dataset succeeded. Actually I tried to use the method from > ACRushTC, when I used a similar method, both datasets passed when I > removed the first two matched but both failed when I removed all > matched. Did I understand the question in the wrong way? As I > understood, the words which have longer rhyme will be ignored. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/d8d001bc-124e-45cb-bfb5-3a6d1482b1f3%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAMAzhzguM6koNt5JPg-eJOkhBC_eQLKJnxr6kMbSTfocFpNGYA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
