Hi Lasse,
another example to make this clear:
Let the given words be:
CODEJAM
NODEJAM
MODEJAM
JAM
The longest common suffix to of at least 2 words currently is "ODEJAM".
So if you choose to put the accent on the "O" of that suffix, then you can
pair 2 words with that suffix:
- either CODEJAM <==> NODEJAM
- or CODEJAM <==> MODEJAM
- or MODEJAM <==> NODEJAM
BUT you can ONLY pair EXACTLY TWO of them.
Lets choose to pair CODEJAM <==> NODEJAM.
If you now remove all the words ending on "ODEJAM" only JAM will be left in
the list of words and can not be paired.
But MODEJAM and JAM are pairable with the accent suffix "JAM", so MUST
NEVER remove UNPAIRED words, just because they share
a suffix with a pair you already build, because there is a chance, that one
of the unpaired words shares a SHORTER suffix with another
unpaired word.
Am Do., 25. Apr. 2019 um 13:30 Uhr schrieb Lasse <[email protected]>:
> On Wednesday, April 24, 2019 at 7:28:41 PM UTC+2, Xiongqi ZHANG wrote:
> > why would you ignore “scent”? even though “scent”
> > also has “cent” as a suffix, it can still be used to match other words
> with different suffix, e.g “went” with rhyme “ent”.
> >
> >
> >
> >
> > On Wed, Apr 24, 2019 at 8:12 AM Lasse <[email protected]> wrote:
> > Hi /dev/joe,
> >
> >
> >
> > thank you for the reply. I think our understanding is the same. With
> your example, I first match rhyme "cent", which is shared by "cent" and
> "recent", then "scent" must be ignored in the other matches, right?
> >
> >
> >
> > I did so and my submission is wrong, but when I retained "scent" and
> only ignored "cent" and "recent", my code works with small dataset.
> >
> >
> >
> > Lasse
> >
> >
> >
> > On Tuesday, April 23, 2019 at 10:59:35 PM UTC+2, /dev/joe wrote:
> >
> > > 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/73c01868-d7e5-430d-a130-78efac477b76%40googlegroups.com
> .
> >
> > For more options, visit https://groups.google.com/d/optout.
>
> Hi,
>
> if I retain scent and scent has rhyme "ent" with maybe "went", then it
> violates the rule "and with none of the words in other pairs", right? Then
> "cent" has rhyme "cent" also with "scent" in pair "scent" and "went".
>
> --
> 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/4103246a-6f22-47c9-8058-752e8a93d706%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/CAEWn8oimVL8uj-thMPU%2BtrHtUTvawfVh8rXPRLeX1%3DE40c4R0Q%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
