|
|||||||||||
|
|||||||||||
|
tomek goes to the finals again by lbackstrom,
Antimatter was first to submit for 167.75 out of 175, in about 5 minutes. tomek was right on
his heels though, with 162.25, while the next 3 coders had between 139 and 144. bstanescu
skipped to a tricky hard problem, while tomek submitted the medium first, after about 50
minutes. It didn't take bstanescu too long to give up on the hard problem, and he went back to
the medium, submitting it much quicker than tomek, and taking a lead of slightly less than 50
points. qsort was next to submit, but was two challenges behind bstanescu. antimatter also
submitted the medium, and his impressive score on the first problem put him into third. When
the challenge phase started, bstanescu was winning, while tomek was in second, and antimatter
was in third.
if(k is on diagonal) best[k][j] = max-10<=i<=10(best[k-1][j-i] + count[k]*i) else best[k][j] = max-10<=i<=10(best[k-1][j-i-i] + count[k]*i) Another way to do it is initialize the score matrix to any valid matrix, and compute the score. Next, consider each possible change that you could make (while still maintaining the -10 to +10 range):
Robbery With the city constrained to be 30*30 or less, there are a total of 314 possible pairs of locations for the police and the robbers. However, while this number is fairly small, writing a solution that works with the different states is pretty tricky (though possible). A better solution is totally independent of city size. First off, lets define the parity between the robbers and police to be the manhattan distance between the two, mod 2. Therefore, if the robbers are at (1,1) and the police are at (2,2), the parity between them is 0. Now, there are a very limited number of things that the robbers need to consider doing. First off, the robbers may just ignore the shortcut, and try to run away from the police. If the parity between the police and robbers is 0, then the police will simply head towards the robbers along the horizontal or vertical roads each time, with their knowledge of where the robbers will go. Eventually, the robbers will be cornered, and the police will catch them in one of the locations adjacent to a corner. Furthermore, if the police make the correct choices, every one of their moves will be towards the corner that the robbers are caught in. By moving to the position that makes the maximum of the difference in x coordinates and the difference in y coordinates as small as possible, the police will never make an unnecessary move. Hence, the robbers best strategy in this case is to go the corner that is farthest from the police's initial position, and that the robbers can get to first. If the parity between the police and robbers is 1, but the robbers still ignore the shortcut, then the situation is similar. In this case the robbers will still get caught in a corner, but the police need to go through the shortcut before heading to the corner. Again, the robbers should go to the corner that it takes the police the longest to reach, but that the robbers can still get to first. Things are a little more complicated than this though because the police may need to make a choice about which way to go through the shortcut before they know where the robbers are going, and this choice may effect how long it takes to catch the robbers. As illustrated by example 4, the police may need to make a choice about which way to go through the shortcut before the robbers must commit to which corner they are going to, and hence the police must determine which of the two choices is best for them, before the robbers decide which corner to head to. If the robbers can go through the shortcut before the police get there, then it might be advantageous for them to do so. The robbers must consider going through the shortcut in one of the two directions and, as before, heading to the corner where they are eventually caught. If the parity is 0, then the police must also go through the shortcut after the robbers, and track them down. If the parity is 1, then the police don't need to go through the shortcut. As before, if the police need to go through the shortcut, their choice of which direction to go through it may effect which corner the robbers head to. Luckily for the competitors, most of these cases were well illustrated by the examples. For an alternate solution that takes advantage of the 30x30 limit, see the solution by lars2520 in the practice room (written by Yarin). |
|