NEED HELP
There are N contestants (numbered 1 through N) who want to participate in Snackdown; let's denote the skill level of the i-th contestant by Si. These people want to pair up in N/2 teams; each team should consist of two people.
Clearly everyone wishes for their teammate to be as skilled as possible, so everyone wants to maximize their teammate's skill level. We call a pairing (an unordered N/2-tuple of teams) valid if there are no two teams consisting of people (A,B) and (C,D) such that SD>SB and SA>SC — in that case, A and D would both prefer to be on the same team rather than with their current teammates.
Find the number of valid pairings. Since this number can be large, compute it modulo 1,000,000,007.
Example Input
2
4
1 7 3 8
4
2 3 2 2
Example Output
1
3
Explanation
Example case 1: The only valid pairing is for contestant 2 to be paired with contestant 4 (so contestants 1 and 3 form the other team).
Example case 2: Since person 2 has the highest skill level and all others have the same skill levels, person 2 can choose anyone among the other three as a teammate. The remaining two people also form a team, so the number of pairings is 3.
Clearly everyone wishes for their teammate to be as skilled as possible, so everyone wants to maximize their teammate's skill level. We call a pairing (an unordered N/2-tuple of teams) valid if there are no two teams consisting of people (A,B) and (C,D) such that SD>SB and SA>SC — in that case, A and D would both prefer to be on the same team rather than with their current teammates.
Find the number of valid pairings. Since this number can be large, compute it modulo 1,000,000,007.
Example Input
2
4
1 7 3 8
4
2 3 2 2
Example Output
1
3
Explanation
Example case 1: The only valid pairing is for contestant 2 to be paired with contestant 4 (so contestants 1 and 3 form the other team).
Example case 2: Since person 2 has the highest skill level and all others have the same skill levels, person 2 can choose anyone among the other three as a teammate. The remaining two people also form a team, so the number of pairings is 3.
can u please tell me if (5,8) and (5,9) then is 8 and 9 would be prefer to be on same team ? as
Sd>Sb but Sa<=Sc
Sd>Sb but Sa<=Sc
Topic archived. No new replies allowed.