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.
Ai1 , Ai2 , ...... , AiM is a permutation of the integers from 1 to M.
A11 A12 ...... A1M
A21 A22 ...... A2M
AN1 AN2 ...... ANM
Print the minimum possible number of the participants in the most favorite sport.
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
2 1 3
2 1 3
2 1 3
Test case Output
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.
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.
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