Algorithm代做 | assignment – Algorithm question

Algorithm question

Algorithm代做 | assignment – 该题目是一个常规的Algorithm的练习题目代写, 涵盖了Algorithm等方面, 该题目是值得借鉴的assignment代写的题目

COMP3121/9101 22T2 assignment 4, Question 4 (Algo Rhythm, z1234567)

Question 4

There are 2nplayers who have signed up to a chess tournament. For all 1i 2 n, theith player has a known skill level ofsi, which is a non-negative integer. LetS=

P 2 n i=1si, the total skill level of all players.

In the tournament, there will benmatches. Each match is between two players, and each player will play in exactly one match. Theimbalanceof a match is the absolute difference between the skill levels of the two players. That is, if a match is played between theith player and thejth player, its imbalance is|sisj|. Thetotal imbalanceof the tournament is the sum of imbalances of each match.

The organisers have provided you with a valuemwhich they consider to be the ideal total imbalance of the tournament.

Design an Algorithm which runs inO(n^2 S) time and determines whether or not it is possible to arrange the matches in order to achieve a total imbalance ofm, assuming:

4.1 [4 marks]allsiare either 0 or 1;

Problem:find the maximum total imbalance of tournament with total skill levelSand 2n
players.
Subproblems:for all 0sSand 1kn, letP(s, k) be the problem determining
opt(s, k) which is the maximum total imbalance of tournament with total skill levelsand 2k
players.
Recurrence:

opt(s, k) = max{opt(s 2 , k1),1 +opt(s 1 , k1), opt(s, k1)}

Base cases:opt( 1 , k) =opt(0, k) = 0,for all 0kn, andopt(s,0) = 0,for all  1 
sS.
We can solve the subproblems in increasing order ofsor in increasing order ofk. The overall
solution isopt(S, n). EachO(Sn) subproblems can be solved in constant time, so the time
complexity isO(nS).
An arrange the matches can be defined as a bijection mapmatchfrom{ 1 , 2 ,... , 2 n}to itself,
such thatmatch(i) be the unique playerjwho is in the same match with playeri.
Given such a map, we can define two players sets

P 0 (match) ={ 1 i 2 n|si= 1, sj= 0, match(i) =j}

and
P 1 (match) ={ 1 i 2 n|si= 1, sj= 1, match(i) =j}

Define
M={ 0 iopt(S, n)|iS mod 2}
then a numbermis total imbalance if and only ifmM.
Ifmis total imbalance, then there is a mapmatchsuch thatm=|P 0 (match)|and
since|P 1 (match)|is always an even number, thusm=|P 0 | S=|P 0 |+|P 1 | mod 2, and
0 mopt(S, n) by definition, that ismM.

1

COMP3121/9101 22T2 Assignment 4, Question 4 (Algo Rhythm, z1234567)

Sinceopt(S, n) is the maximum total imbalance, then there is a mapmatchsuch that the
total imbalance equals toopt(S, n). we can find another arrange of matches such that the
total imbalance equals to anymMas follows:
Given a mapmatch, denoteP 0 =P 0 (match) for simplicity, then if|P 0 | 2 we can always
select two playersi 1 , i 2 P 0 , letj 1 =match(i 1 ), j 2 =match(i 2 ), rearrange the match gives a
new mapmatchsuch thatmatch(i 1 ) =i 2 andmatch(j 1 ) =j 2 , andmatch(i) =match(i)
for any otheri{i 1 , i 2 , j 1 , j 2 }, then the total imbalance formatchwill be reduced by two.
Since the elements inMis not exceedS, thus we can check ifmis a total imbalance inO(S)
time, thus the total runtime isO(nS) +O(S) =O(nS).

4.2 [16 marks]thesiare distinct non-negative integers.

Your answer here.

2