Its been a while since I've posted an analysis, and seeing as this is the last round we'll be having in a while I thought I'd write up guidelines to solutions for this past DWITE.
#1:
The only thing you have to be careful about here is that the time is to be output in military format (i.e. 00:00:00 -> 23:59:59). There were a few teams who forgot the trailing 0s for the timestamp, or forgot to take the modulus of the hour by 24. Keeping these things in mind, you add the number of hours together with the total travel time and offset the current timestamp by that many hours, keeping the minutes and seconds unchanged.
#2:
The trick here is to go through every suffix of the word to check if it is also a prefix (i.e. once you have found a suffix of the word that is also a prefix don't just quit and use that). For example, the phrase aba aba has a as a common suffix/prefix, but continuing on ba is a suffix but isn't also a prefix. However you shouldn't then stop and assume that a is the largest overlap, as you can keep going and find that aba is the biggest overlap, yielding a final answer of aba aba aba. Thus iterating through the phrase backwards and matching the suffixes to prefixes along the way keeping track of the biggest one should do the trick.
#3:
I must admit, I am kind of proud of this question
. Unfortunately, due to the small bounds and the fact that large test cases are hard to test, the problem ended up being bruteforce-able (I was initially planning on suggesting this as a possible CCC question, but then decided that it was more at home in DWITE). However, still a tricky question! We iterate through the grid looking for the number of triangles with the topmost # being at the current location, incrementing a counter along the way. So at every location we check if it is a #, and then if we go one square down and check if the adjacent two squares are #, and we continue this way until we don't see any more triangles. Since iterating through the whole grid takes O(n^2), and since at each location we are potentially checking for triangles of up to a size of n, which takes O(1 + 3 + 5 + ... + (2n-1)) = O(n^2), the total runtime is a whopping O(n^4) (in the worst case). We can do better. In fact, we can get this down to O(n^2) by using an algorithm that is based on the technique of dynamic programming.
The first observation one makes is that the triangles can be split into 2 parts:
| code: |
# * * ### -> #* + *# ##### ##* *## |
Here the * represents the overlap in the two half triangles. Let?s call these halves 'left' and 'right' pieces. Let countLeft(i, j) be the number of left pieces whose top rightmost # is at location (i, j). Define countRight(i, j) in a similar way. Then the number of triangles whose topmost piece is at (i, j) is simply min(countLeft(i, j), countRight(i, j)), since we want a complete triangle (anything more than this will result in a triangle where one half ends up being slightly bigger). Both countLeft and countRight can be found in O(n^2) using the following recurrrence:
| code: |
if (grid[i][j]=='#') countR[i][j] = 1 + min(countR[i+1][j+1], countR[i+1][j]); /* * Since the number of right pieces at location (i, j) is the minimum of * the number of right pieces at locations (i+1, j+1) (i.e. bottom right) and * (i+1, j) (bottom) */ if (grid[i][j]=='#') countL[i][j] = 1 + min(countL[i+1][j-1], countL[i+1][j]); /* * Since the number of left pieces at location (i, j) is the minimum of * the number of right pieces at locations (i+1, j-1) (i.e. bottom left) and * (i+1, j) (bottom) */ |
Thus we can dynamically precompute the number of left and right pieces at all locations in O(n^2) time in a bottom-up fashion. All we have left now is the counting of the number of actual triangles which amounts to summing up the minimums of the number of left and right pieces at each location, which also takes O(n^2), yielding a total runtime of O(n^2+n^2) = O(n^2). Huzzah!
#4:
Apologies once again about the error in the testcase. Apart from that, most teams seem to have gotten the gist of this question. An empty square is to be fenced iff it is adjacent to an animal (including diagonally) and it is only non-diagonally adjacent to exactly one animal. Many teams seemed to have missed the second condition. Thus simply iterating through the grid counting the number of empty locations that follow these conditions suffices, yielding a total runtime of O(n^2).
#5:
I was originally considering posing the question for a general N by N board, but then we realized that this would be a bit too hard. Thus we stuck to the standard 3 by 3 grid. Once again a few teams missed the condition that stated: the path can't cross an unvisited vertex. This suggests that a path may cross a visited vertex (thus if the middle location in the first row has already been visited, you can potentially go from the top left corner to the top right corner with 1 edge). Thus performing a DFS regarding each of the 9 locations as a potential starting point, and making sure to quit the DFS once your path has either violated any of the conditions or has gone above the required length, should pass in time.
Now we noticed that a few teams hardcoded the values, which got me googling. I guess we should have known that this was a pretty commonly asked question, but I am giving the benefit of the doubt to you all
.
Let me know if you have any questions regarding this past round. I realize that CCC is coming up soon, go good luck to you all!