Solving this problem will likely be easier after Friday$$s Review Session, and even more so after Monday$$s$$lecture$.$ Or you could read ahead in the textbook on the analysis of the Earliest Deadline First$$algorithm$.$In this problem, we will look at how to manipulate the outcome of an election. In many elections,$$voters can only vote for one candidate $$ if so$,$ there is really only one reasonable voting rule, which$$is to choose the candidate with the largest total. But as you probably know, this leads to a lot of$$speculating to avoid $$wasting$$ one$$s vote on a candidate who won$$t win anyway. For that reason,$$some elections ask voters to rank all candidates from most favorite to least favorite; with this extra$$information$,$ one can then do a better job picking a $$good$$ candidate. There are a lot of different$$voting rules for choosing a candidate $$ you may have heard about Single Transferable Vote $($STV$),$also known as Ranked Choice voting. Another well$-$known method, and the one we will consider here,$$is the Borda Count, named after Jean$-$Charles de Borda, who invented it in the late $18$th century.$$Assume that there are m $>=2$ candidates and n voters. Each voter ranks all m candidates from most$$to least favorite. For voter v $=1,...,$ n$,$ their order is a permutation $\backslash$pi v$,$ and we write $\backslash$pi v$($i$)$ for the$$candidate that voter v has in position i$.$ Voter v$$s most favorite candidate is $\backslash$pi v$(1),$ and their least$$favorite is $\backslash$pi v$($m$).$ Under the Borda count rule, candidate c gets m $1$ points for each first$-$place vote$$they get, m $2$ for each second$-$place vote they get, and so on; with $0$ points for each last$-$place vote$$they get. The points are added up$,$ and the candidate with the largest total number of points wins$\mathrm{.}1$As an example, suppose that there are three voters and four candidates, and the rankings of the voters$$are $$A$,$B$,$C$,$D$,$B$,$C$,$ A$,$D$,$C$,$D$,$ A$,$B$.$ Because m $=4,$ candidate A gets $3+1+1=5$ points, B$$gets $2+3+0=5$ points, C gets $1+2+3=6$ points, and D gets $0+0+2=2$ points. Here, C would$$win$.$Now assume that you are voter n$,$ and your favorite candidate would be A$.$ You would like A to win.$$You can see all the ballots of all other voters. The question is: is there some ranking you can put$$on your ballot such that A is the unique winner, i$.$e$.,$ A gets strictly more points than every other$$candidate $($no ties$)?$ Clearly, sometimes this will be impossible, and other times, it is possible. For$$instance$,$ in the example above, if you were the fourth voter, you could write $$A$,$B$,$D$,$C$$ on the ballot,$$and now, A would have $8$ points, B would have $7$ points, C would have $6$ points, and D would have$1$Let$$s not worry about tie breaking for now.$23$ points, so A would win. On the other hand, if everyone else had ranked A last and B first, there$$would have been nothing you could do$.$Give a polynomial$-$time algorithm to compute a ballot you can submit to make A win, or correctly$$conclude that no such ballot exists. Prove the correctness of your algorithm, and analyze its running$$time$.$