CCO '99 P2 - Common Words - Olympiads Online Judge

CCO '99 P2 - Common Words

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 16M

Problem type

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

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

Input Specification

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

Output Specification

For each input data set, determine the $k^\text{th}$ $k^{th}$ most common word(s). To be precise, a word $w$ $w$ is the $k^\text{th}$ $k^{th}$ most common if exactly $k-1$ $k - 1$ distinct words occur more frequently than $w$ $w$ in the data set. Note that $w$ $w$ might be multiply defined (i.e. there is a tie for the $k^\text{th}$ $k^{th}$ most common word) or $w$ $w$ might not exist (i.e. there is no $k^\text{th}$ $k^{th}$ most common word). For each data set, print a title line indicating $k$ $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}$ $k^{th}$ most common word. A blank line should follow the last word for each data set.

Sample Input

Copy

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

Sample Output

Copy

2nd most common word(s):
red

3rd most common word(s):

1st most common word(s):
the
wash

Comments

0

mculiver commented on Oct. 8, 2021, 10:56 p.m. ← edit 2 →

What if $k = 0$ $k = 0$

5

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

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

0

DoYouWantToHearWhatISaidAgain commented 33 days ago ← edit 2 →

what do you mean by "WA'd"

2

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

Output Specification

To be precise, a word $w$ $w$ is the $k^\text{th}$ $k^{th}$ most common if exactly $k-1$ $k - 1$ distinct words occur more frequently than $w$ $w$ in the data set.

What happens if, for example, there is an $m$ $m$ value of $10$ $10$ and a $k$ $k$ value of $3$ $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$ $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$ $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.

2

TypicalToxic commented on Nov. 11, 2016, 12:30 a.m. ← edited →

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

12

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, ...