Win a copy of Succeeding with AI this week in the Artificial Intelligence and Machine Learning forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Paul Clapham
• Ron McLeod
• Liutauras Vilda
• Junilu Lacar
Sheriffs:
• Tim Cooke
• Jeanne Boyarsky
• Knute Snortum
Saloon Keepers:
• Stephan van Hulst
• Tim Moores
• Tim Holloway
• Carey Brown
• Piet Souris
Bartenders:
• salvin francis
• fred rosenberger
• Frits Walraven

# What should be the approach to solve the following question?

Greenhorn
Posts: 1
Problem Statement

Mark is hosting a sports meet. There are 'N' people who will participate. These people are being conveniently numbered 1 through N. Also, there are M options of sports for this event. These sports are numbered 1 through M. Among these options, Mark will select one or more sports (possibly all) to be played in the event.

Mark knows that Person i's j- t h favorite sport is Sport A i j. Each person will only participate in his/her most favorite sport among the ones that are actually played in the event, and will not participate in the other sports.

Mark is worried that one of the sports will attract too many people. Therefore, he would like to carefully select sports to be played so that the number of participants in the most favorite sport is minimized. Find the minimum possible number of participants in the most favorite sport.

Constraints

1<=N<=300

1<=M<=300

Ai1 , Ai2 , ...... , AiM is a permutation of the integers from 1 to M.

Input Format

N M

A11 A12 ...... A1M

A21 A22 ...... A2M

::

AN1 AN2 ...... ANM

Output Format

Print the minimum possible number of the participants in the most favorite sport.

Sample Test case #0

Test case Input

4 5

5 1 3 4 2

2 5 3 1 4

2 3 1 4 5

2 5 4 3 1

Test case Output

2

Explanation

Assume that Sports 1, 3 and 4 are selected to be conducted. In this case, Person 1 will participate in sport 1, Person 2 in sport 3, Person 3 in sport 3 and Person 4 in sport 4. Here, the sport with the largest number of participants is sport 3, with two participants. There is no way to reduce the number of participants in the sport with the largest number of participants to 1. Therefore, the answer is 2.

Sample Test case #1

Test case Input

3 3

2 1 3

2 1 3

2 1 3

Test case Output

3

Explanation

Since all the people have the same taste in sports, there will be a sport with three participants, no matter what sports are selected. Therefore, the answer is 3.

Marshal
Posts: 69035
275
Welcome to the Ranch

I think the first stage is independent of languages, and can better be done with your computer turned off. Write down what you think that means and how you would solve it withoiut a computer.

Saloon Keeper
Posts: 3919
154
hi Tejendra,

well that exercise does not look easy, to say the least...

I follwed this strategy:

Say we have a Collection of sports. If that Collection contains the most popular sport, then it is likely that the largest group is pretty large (many sportsmen will be in the goup of that most popular group).

If, on the other hand, that Collection contains the least popular sport, then you can expect the sizes of the groups to be more spread, resulting in a smaller "largest" group.

So, what I did was:
1) create a List<Integer>, containing the sports from lowest to highest popularity.
2) we also have the int[][] preferences, that is simply the input.
3) have a Set<Integer> set
4) then for each sport in the List:
- add that sport to the set
- get the groups that go with this set and the preferences.
- if the largest group is smaller than the smallest group sofar, write it down
5) the result is then that smallest group.
6) We can shortcut 5), but I am thinking about a proof that what I did is correct.

I haven't proven yet that this strategy leads to the absolute correct answer, but I get both the results given in the examples.

Do you have some other examples?

Marshal
Posts: 25472
67

Tejendra Oberoi wrote:Mark is worried that one of the sports will attract too many people. Therefore, he would like to carefully select sports to be played so that the number of participants in the most favorite sport is minimized. Find the minimum possible number of participants in the most favorite sport.

I'm already stuck. I don't understand what "the most favorite sport" is.

Sure, I know what my favorite sport is if I'm in this tournament. But is the favorite sport supposed to mean the same thing for everybody?

 Honk if you love justice! And honk twice for tiny ads! ScroogeXHTML 8.7 - RTF to HTML5 and XHTML converter https://coderanch.com/t/730700/ScroogeXHTML-RTF-HTML-XHTML-converter