There is a paragraph in Analysis of Manhattan Crepe Cart that confuses me. The section titled "Test set 2: a (nearly) linear solution" explains an algorithm that creates a set of tuples consisting of three elements: coordinate, number of people at that coordinate facing west, and number of people at that coordinate facing east. It denotes the tuple as (C,W,E). Since we are only talking about the horizontal subproblem, it ignores N and S. Once all tuples have been created, it sorts the tuples in ascending order on C. All of this makes sense. Then we get into the next paragraph. It reads as follows:
Once we have sorted the tuples, we start by considering cell 0 as a candidate location, and we determine the votes for that cell. [1]We know that quantity is equal to W minus the number of people in cell 0, if any. We make a note of this number of votes and set 0 as our best candidate so far. Then, we look at the first tuple in our sorted list, which represents the people at some cell C (which might be cell 0). [2]The number of votes for cell C + 1 (the cell one unit to the east of C) should be the same as the number of votes we found for cell 0, plus the number of people in cell C facing east (which is all of them in this case), minus the number of people in cell C facing west. [3]If cell C is a better candidate, we store it and its number of votes. I have denoted my confusions by inserting [#] at the beginning of three sentences. Here is what I think: 1) As per the Limits of the problem, all people in cell 0 are either facing N or E. By that logic, there is nobody in cell 0 that is facing west. Since the number of votes for cell 0 is equal to the number of people facing west, and since all people facing west are east of cell 0, then the number of votes for cell 0 is equal to W. 2) The problem states that "if a person located at (x0,y0) is moving north, then they are moving toward all street intersections that have coordinates (x,y) with y>y0." This means that a person at y0 is not moving toward y0 and, therefore, is not voting for y0. By this logic, if there are people at C+1, and they are facing west, then we must remove their votes from the total for C+1. 3) The analysis states that the cart will always be either at (0,0) or at a intersection directly east of a populated intersection. Therefore, when we reach C in our set of tuples, we do not analyze C; we analyze C+1. The following paragraph is clear to me Once we have sorted the tuples, we start by considering cell 0 as a candidate location, and we determine the votes for that cell. We know that quantity is equal to W. We make a note of this number of votes and set 0 as our best candidate so far. Then, we look at the first tuple in our sorted list, which represents the people at some cell C (which might be cell 0). The number of votes for cell C + 1 (the cell one unit to the east of C) should be the same as the number of votes we found for cell 0, plus the number of people in cell C facing east (which is all of them in this case), minus the number of people in cell C facing west, minus the number of people in cell C+1 facing west. If cell C+1 is a better candidate than our previously best candidate, we store C+1 and its number of votes. Am I missing something? This is the first problem I have encountered for which the analysis is unclear. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/8a2c5c1b-f081-44dd-a6e0-213d37c2375f%40googlegroups.com.
