TopCoder SRM 544 - miss the match

DIV 2 250 - ElectionFraudDiv2

http://community.topcoder.com/stat?c=problem_statement&pm=11946

You are given a list of of integers \(\{0, 5, 100\}\) that represent the percentages received by each of the candidates of an election. You are ask to write a program that detect if the election is fraudulent, or if the reported percentages are rounded. In that case, return "YES", otherwise, "NO". For more details of the problem statement please check the link below.

In my opinion this problem was little bit more tricky than a normal DIV 2 250 the 19.10% of success rate confirm my thoughts...

To solve this problem we need to consider the following three cases:

Case #1: The sum of percentages equal to 100%

In this case we assume the elections were not fraudulent. The answer for this case is "NO".

Case #2: The sum of the percentages is greater than 100%

In this case we need to check if the sum is greater than 100% because of a rounded up error. For example if the percentage for a certain candidate is 13% means that the real percentage value (not rounded) of the elections for that candidate is in the range \([12.5\%, 13.49\%]\). To check that occurred a round error we substitute each of the candidate percentage for the minimum value in this range and sum them up. If we get a percentage sum less or equal to 100% means that the results are not fraudulent. The reason is because we can always get 100% with some combination of the rounded up error. In this case we should be careful with 0% is not possible to get 0% as a result of a rounded up error. For example:

3 candidates 

\(A1 = \{34\% , 34\%, 34\%\}\)

\(sum\_percentage = 102% \)

\(A2 = {33.5\%, 33.5\%, 33.5\%}\)

\(sum\_percentage = 100.5%\)

The results of this elections still fraudulent even after fixed the rounded up errors.

Case #3: The sum of the percentages is less than 100%

Similar to case #2 but taking the maximum value of the candidate percentage range.

DIV 2 500 - BoardSplitting

http://community.topcoder.com/stat?c=problem_statement&pm=11951

You are given a unlimited amount of boards of length \(actualLength\) and using those  you need to create \(desiredCount\) boards of length \(desiredLength\). You are allow to glue the boards and also cut them. If there are multiple ways to use the same number of boards, pick the one that perform as few cuts as possible. Return the number of cuts they will perform.

The strategy that I follow to solved this problem was greedy + simulation. As in the previous problem there are also three main cases to consider:

Case #1 desiredLength is equal to actualLength

In this case the answer is 0 because each of the \(actualLength\) boards has the desired length and we have unlimited supply of this boards we just take \(desiredCount\) of them.

Case #2 desiredLength is greater than actualLength

In this case the boards in our supply are smaller that our target. The best possible scenario is when the \(desiredLength\) is a multiple of the actualLength in that case our answer is 0 because we don't need to perform any cut. Otherwise, the optimal strategy is to glue as much boards of length actualLength as we can and after that deal with the remainder. Because the \(desiredLength\) of all the board is the same thus the remainder for each of the boards is going to be the same. However, the cases where the remainder portion of the actualLength is not enough to complete the \(desiredLength\), in this cases we just glue this board and take the missing part for the next board. The following example explain this idea:

\(desiredCount = 159\)
\(actualLength  = 25\)


 


\(desiredLength = 314\)

In this case the remainder of \(desiredLength % actualLength\) is 14. Which means that we first glue 12 boards of \(actualLength\) and what remains is a left over of 14 units length. This left over is the amount that we should complete for each of the \(desiredLength\) boards and the only part that actually require cuts of the board with \(actualLength\). In the pictures bellow we can see that when we cut the board with \(actualLengh = 25\) we end up with a board of 11 units. This board is further use for the next board of \(desiredLength\) we need to complete.

Case #3 desiredLength is less than actualLength

This cases can be reduced to the previous one. The only difference is that the remainder is now the \(desiredLength\).

DIV 1 500 - FlipGame

http://community.topcoder.com/stat?c=problem_statement&pm=11974

Given a binary matrix:

00000000
00100000
01000000
00001000
00000000

You have to toggle the bits of the matrix until all of them become 0s. At each step you are allow to toggle the bits that are below certain shortest path from the upper-left corner to the lower-right corner. They ask you to return the minimum number of steps required to change all bits to 0s.

The strategy to solve this problem is greedy. Let's say that the \(i\)-th element represent the row of the matrix and the \(j\)-th element the columns. For each row we pick the the highest set bit for the \(j\)-th column. If for a certain row the highest set bit is less than one of the predecessor highest set bits we keep the position of the one with greater value of \(j\). The reason to pick the highest set bit is because the problems ask us to pick paths that are shortest paths. This procedure is guaranteed to finish because keep toggle the highest set bits until all the bits become 0s.