CCO '99 P2 - Common Words

View as PDF

Submit solution

Points: 10
Time limit: 1.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^\text{th} most common word(s).

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 lowercase letters. There will be no more than 1\,000 words per data set.

Output Specification

For each input data set, determine the k^\text{th} most common word(s). To be precise, a word w is the k^\text{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^\text{th} most common word) or w might not exist (i.e. there is no k^\text{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^\text{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


  • -2
    mculiver  commented on Oct. 8, 2021, 10:56 p.m. edit 2

    What if k = 0


  • 4
    dxke02  commented on Nov. 22, 2020, 5:32 p.m.

    I WA'd 15 times before I realized that I read the question wrong


  • 2
    aeternalis1  commented on July 12, 2017, 1:52 p.m. edit 2

    Output Specification

    To be precise, a word w is the k^\text{th} 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)


    • 2
      SirLighton  commented on Sept. 9, 2021, 5:51 p.m. edited

      Now for k = 3. This time, there are two words to output, storm and brook, because they both have the same number of occurrences. Each of these words has exactly two words with more occurrences. This shows that we sometimes need to output more than one word.


  • 1
    TypicalToxic  commented on Nov. 11, 2016, 12:30 a.m. edited

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


    • 11
      Kirito  commented on Nov. 11, 2016, 2:57 a.m.

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