Bowling
Time limit1sMemory limit1024 MB
Each player has G scores that may be permuted independently; for every player find the minimum and maximum number of games they can win, where a win means a strictly higher score than all other players in that game.
- Level
Hard8 of 10
- Topics
- Greedy, Sorting, Math, Combinatorics
- Solved
- No attempts yet
Problem
Last Saturday, Paul, Ivo and Nick went to a bowling alley. They hired a lane for one hour and played three games. Playing casually, they simply counted the number of games each of them won: the overall winner would be the one who won the most games. (In case of a tie, they would have had to figure out another way to name the winner.)
This time, Paul won two games and Nick one, so Paul was named the winner. Ivo wondered how it was possible that he lost all three games even though he felt his scores were not too bad. So he looked again at the scoreboard and saw this:
Paul indeed won two games, and Nick one, but Ivo noted that if he had played his games in another order, namely 112-98-73, he would have won two games, and Paul none.
Ivo's remark is not as unreasonable as one might think at first glance: in bowling, each game is played independently of the other players, except perhaps for some psychological side effects. The successive scores of an individual player can also be assumed to be more or less independent and identically distributed.
Ivo wisely kept his remarks to himself last Saturday, but later he started to think about using his idea of 'potential number of wins' as a measure of performance. He concluded that it would also be interesting to know the minimum number of wins for each player. Also, it would be nice not only to allow permutation of the games of the player whose number of wins is being maximized or minimized, but also permutation of the games of the other players. Finally, Ivo has to define when exactly a player 'wins' a game: a player wins a game if and only if his score is strictly greater than the score of each of the other players.
Ivo asks you to write a program that calculates for each player i:
- mi, the minimal number of games player i would have won, regardless of the permutation of the scores of each individual player, and
- Mi, the maximal number of games player i could have won if the scores of each individual player were permuted optimally to that purpose
Input
The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
- One line with two integers P and G, separated by a single space, that indicate the number of players and the number of games respectively (2 ≤ P ≤ 100, 2 ≤ G ≤ 1000).
- P lines, one for each player, each with G integers, separated by single spaces: the successive scores for that player.
Each score is between 0 and 300 (both inclusive).
Output
For every test case in the input, the output should contain P lines, one for each player in the input. On the ith line should be two integers, separated by a single space: mi, followed by Mi.