CCO '99 - Common Words

View as PDF

Submit solution


Points: 10
Time limit: 2.0s
Memory limit: 16M

Problem type

Canadian Computing Competition: 1999 Stage 2, Day 1, Problem 2

Given a sequence of m words from a newspaper article and an integer k, find the k^{th} most common word.

Input Specification

Input will consist of an integer n followed by n data sets. Each data set begins with a line containing m and k, followed by m lines, each containing a word of up to 20 lower case letters. There will be no more than 1\,000 words per data set.

Output Specification

For each input data set, determine the k^{th} most common word(s). To be precise, a word w is the k^{th} most common if exactly k-1 distinct words occur more frequently than w in the data set. Note that w might be multiply defined (i.e. there is a tie for the k^{th} most common word) or w might not exist (i.e. there is no k^{th} most common word). For each data set, print a title line indicating k using normal ordinal notation (1st, 2nd, 3rd, 4th, 5th, ...) followed by a number of lines giving all the possible values for the k^{th} most common word. A blank line should follow the last word for each data set.

Sample Input

3
7 2
the
brown
the
fox
red
the
red
1 3
the
2 1
the
wash

Sample Output

2nd most common word(s):
red

3rd most common word(s):

1st most common word(s):
the
wash

Comments


  • 0
    dugonix  commented on May 15, 2018, 1:48 p.m.

    Can someone take a look at my code?

    The first test case isn't working but the second works fine. I'm not sure what's wrong with my output. Does it have to do with the spacing of output? :(


  • 0
    aeternalis1  commented on July 12, 2017, 9:52 a.m. edited

    Output Specification

    To be precise, a word w is the kth most common if exactly k−1 distinct words occur more frequently than w in the data set.

    What happens if, for example, there is an m value of 10 and a k value of 3. If there is more than one 'most common word(s)' (e.g both the words 'hi' and 'hello' appear 3 times), would the third most common word be 'hey', appearing 2 times, due to the fact that there are 2 distinct words appearing as 'most common', or would 'hey' be the second most common? If the former, what would you do in a scenario when there are more words tied for 'most common word(s)' than the value of k? Would you just output all the 'most common word(s)'?

    EDIT I suppose my question is, if you have 2 words tied for the same place, do they register as both of those places, or just at the first one? (i.e does searching for 'most common' and '2nd most common' output the same if there are 2 'most common' words)


  • 0
    chenj  commented on Nov. 11, 2016, 8:19 p.m. edit 2
    Order of Output

    Does the order of output matter? The question just states to output "a number of lines giving all the possible values for the kth most common word". Should the words be outputted based on their position in the input?

    Edit: My code passes on WCIPEG, so I suppose the ordering matters on DMOJ. If you keep getting WA and are certain your code is correct, try running it on WCIPEG.

    Edit 2: Issue fixed. Thanks Shinigami!


    • 0
      Kirito  commented on Nov. 11, 2016, 11:44 p.m. edit 3

      Order should not matter.

      EDIT: This was because I wrote the checker but forgot to include it. All submissions will be rejudged.


  • 0
    TypicalToxic  commented on Nov. 10, 2016, 7:30 p.m. edited
    11th or 11st?

    Expand on "normal ordinal notation" 11th or 11st


    • 3
      Kirito  commented on Nov. 10, 2016, 9:57 p.m.

      1st, 2nd, 3rd, 4th, 5th, 6th 7th, 8th, 9th, 10th, 11th, 12th, 13th, 14th, 15th, 16th, 17th, 18th, 19th, 20th, 21st, ...