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.

Codeforces Round #121 - silly mistake

This was not a good match for me, I got pretty confident after solved the problem A relatively fast. I was careless in the problem B and forgot to consider an important case. I spend the rest of the match looking at problem C.

A. Funky Numbers

http://codeforces.com/contest/192/problem/A

In this problem we need to tell if a certain number can be expressed as the sum of two triangular numbers. At first the constraint of \(N \leq 10^{9}\) seems kind of scary... The key observation is that there are just 44,720 triangular numbers under the \(10^{9}\). Knowing this we can construct a sorted list of all triangular numbers under \(N\). The only question that remains is how to search efficiently into into this sorted list, the answer is simple binary search. For each number in our list greater or equal to \(N\) we used binary search to look for the number \(N - A[i]\) in the list, if we find a match we are done, which means it's possible to express this number as the sum of two triangular numbers, otherwise, is not. To make things clear let's check an example:

\(N = 256\)

\(T = \{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, \\ 190, 210, 231, 253, 276, ...\}\)

\(X = 256 - T[0] = 256 - 1 = 255\)

\(binary\_search(X)\) 
255 is not in the list; means 1 + 255 is not the sum of two triangular numbers.

\(X = 256 - T[1] = 256 - 3 = 253\)

\(binary\_search(X)\)
253 is in the list; means that 256 can be expressed as the sum of two triangular numbers 256 = 253 +3.

B. Walking in the Rain

http://codeforces.com/contest/192/problem/B

You are given a one-dimensional grid, each cell of the grid has a threshold of the amount of days can last, you need to move your troops along the grid, from position \(1\) to \(N\). From the \(i\)-th cell your troops are just allowed to move to the cells \(i + 1\) or \(i + 2\) as long as the cell is not destroyed. Output the maximum number of days that your troops can walk along this grid.

My guess is that on purpose the writer kept the constraints low enough to allow \(O(N^{2})\) solution to pass. During the match I was not thinking I tried to simulate the process... I forgot to consider the case where the troops where in the initial position. A better solution was to notice that we can't jump more that two cells at time, this means that  if we get block by two destroyed cells next to each other we are not going to be able to cross them. This means that for each pair of cells we calculate their maximum destroy time threshold and for all this value we stay with the minimum of all the pairs.