So I blinked and I missed the fact that qualifying round 3 had already happened.\u00a0 I thought it was this coming weekend.\u00a0 Having got through in QR1, forgetting about it is no drama, but it does mean my analysis of the problems is a bit late.<\/p>\n
Q1) Given the top row and left column of a grid of numbers, where each number is supposed to satisfy the property of being equal to the sum of the 3 numbers to the bottom\/right\/bottom-right of it, determine the value of the bottom right number.\u00a0 If the result cannot be uniquely determined return 0. Maximum grid size 10×10.<\/p>\n
A1) First to get rid of the trivial cases.\u00a0 If row length is 1, return last column entry.\u00a0 If column length is 1, return last row entry.\u00a0 Otherwise we actually have to fill in the grid.\u00a0 This is pretty trivial since each cell is the sum of the 3 bottom\/right\/bottom-right, if you know the cell, the bottom and the right, you can subtract the bottom and the right to get the bottom-right cell.\u00a0 Given you have the top and left sides, you can fill 1 cell immediately.\u00a0 That cell lets you fill 2 more, and those, 3.\u00a0 So you could diagonally fill the grid.\u00a0 Or you could just fill row by row, or column by column.\u00a0 In any case the cannot be uniquely determined scenario doesn’t exist so it can be ignored.<\/p>\n
Q2) Given 6 numbers representing number of semitones to offset a guitar string (or -1 if that guitar string is not played), determine whether a major or minor cord is being played and if so which one.<\/p>\n
A2) When I first started reading this question I had dreaded flashbacks to an old Top coder problem which was very similar.\u00a0 However this one is relatively easy.\u00a0 Modulo arithmetic comes into play.\u00a0 Simply add the offsets (where not -1) to the numerical value of each guitar strings open note (as given in the problem for those who don’t play guitar) modulo 12.\u00a0 Then reduce your (upto 6) notes to the unique values.\u00a0 If you have more or less than 3 values you can return not-a-chord immediately.\u00a0 Otherwise, sort the 3 values.\u00a0 For each of the 3 values, check to see whether the next one (wrapping round if you start with the greatest value) is equal to the original + 4 or 3 modulo 12.\u00a0 Then check if the remaining value is equal to the original + 7 modulo 12.\u00a0 If both conditions are matched, return Major ‘letter’ by mapping the original value to the letters if the first condition was +4, or Minor ‘letter’ if the first condition was +3.\u00a0 Otherwise return not-a-chord.<\/p>\n
Q3) Given a pane of glass with width and height (both at most 1000), a starting position, and up to 2500 LRUD unit movements which cut the glass, starting from the starting position, how many pieces has the pane of glass been cut into?<\/p>\n
A3) This is a simulation problem combined with a disjoint set enumeration.\u00a0 The thing I find most annoying with problems like this is the data structure to store the results of the actions.\u00a0 So used to a grid, storing details about edges is just annoying.\u00a0 I usually end up storing the 4 edges of each cell and dealing with the fact that most edges belong to 2 cells by ensuring I always update both.\u00a0 A grid of numbers can be used with numbers between 0-15 indicating which combination of surrounding edges have been cut, you can store these in bytes even making the grid require 1meg of ram.\u00a0 Once the simulation is complete, calculating the pieces comes in to play.\u00a0 I would do this with a disjoint set tracker (copying my code from TMD.Algo – since this is top coder… or maybe just writing it from scratch using arrays instead of dictionaries), creating a node for every square, then for each square unioning it with every neighbour which is on the other side of a non-cut edge.\u00a0 Then for each square get the representative, and use a dictionary to accumulate the count of unique representatives.\u00a0 Disjoint set tracker is practically O(1) for union and get operations, so even though there are a million cell locations the running time will not be a problem.\u00a0 Memory usage will be a few megabytes, but within the 64meg limit.\u00a0 This is really just showing my bias to disjoint set tracker, which I think is awesome.\u00a0 For a similar approach which uses a tad less memory, you can just do floodfill counting using breadth or depth first searches which can’t pass the cut walls, which is also O(1) per grid cell.<\/p>\n
Alternatively one could construct a graph out of the path followed and the edges of the puzzle.\u00a0 Due to the limit on 2500 moves and 4000 edge positions, the memory usage will be much lower.\u00a0 You can then walk the graph starting at each edge using a turn right at intersection approach, mapping each location visited (and handling dead-ends by turning around and keeping on walking).\u00a0 Once you find a loop where you enter an edge from a direction other than the one you left it, you increment a counter and in any loop found case go back to starting at the next edge not already visited.\u00a0 Once done the counter is the number of pieces. Each edge is visited at most three times, so O(N) in edges (moves + perimeter), which is far more efficient.\u00a0 I would however consider it more complicated to implement, so I doubt I would have bothered.<\/p>\n
All in all this looks like it was a pretty easy set.\u00a0 Although being a qualifying round that is probably expected.<\/p>\n","protected":false},"excerpt":{"rendered":"
So I blinked and I missed the fact that qualifying round 3 had already happened.\u00a0 I thought it was this coming weekend.\u00a0 Having got through in QR1, forgetting about it is no drama, but it does mean my analysis of the problems is a bit late. Q1) Given the top row and left column of … Continue reading TCO10 QR3<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[],"class_list":["post-160","post","type-post","status-publish","format-standard","hentry","category-code-competitions","category-random-musings"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/160","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=160"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/160\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=160"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=160"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}