This round needed at least one problem out entirely, and if it wasn’t the third problem you needed the whole second problem or the small input for the third.\u00a0 So it looks like it may not have been quite as easy as R1B.<\/p>\n
Q1) Given n lines which all start and end with one of 2 x coordinates, and the list of y coordinates for each endpoint which are all distinct, and a guarantee that there will be no coincidence of intersections (no places where 3 or more lines cross), how many intersections are there. Constraint of n < 1000 for the big input.<\/p>\n
A1) This is a simple O(N^2) problem, for each line it crosses another if the y coordinate order of one end is the opposite of the other.\u00a0 I think I recall there being a way to do this faster… indeed the contest analysis mentions that this can be done in O(N log N), it is called the number of inversions in a permutation.\u00a0 That is first sort the lines by their first end point, then determine how many pairs switch ordering when you sort by the second end point.\u00a0 Apparently a merge sort can be adapted to perform this calculation, which is equal to the number of neighbour swaps required to sort them, which I have seen in previous problems which I have also solved using O(N^2) because the problem input size has never needed anything else.\u00a0 I should probably look at adding this merge sort trick to TMD.Algo.<\/p>\n
Q2) Given a known range which contains the maximum number of simultaneously connections a computer can handle (the upper end is known failure, lower end known success) and a requirement to reduce that range such that the top end is less than C times larger than the lower end (where C is an integer between\u00a0 2 and 10, inclusive), what is the minimum number of tests required to guarantee that in the worst case.<\/p>\n
A2) Bit of an odd question, one would first think a binary search would be idea, the size of the range would reduce consistently.\u00a0 However, our target is not the size of the range but ratio of top to bottom.\u00a0 Therefore we want a skewed binary search where the selection point is the one which results in A\/S = S\/B so our selection point is the sqrt(AB).\u00a0 Now since the load tests can only be performed on integers, we’ll have to choose one of the 2 integers near the value of the square root.\u00a0 In order to be ideal we must choose the one which has the best worst ratio, might as well use fractions just to be safe in comparing them. Then we simulate this process until the ratio is less than or equal to C.\u00a0 The sample answer is not quite the same, however given that based on the selection point chosen, the ratio is sqrt(A\/B) after n steps that is (A\/B)^(1\/(2^n)),\u00a0 If we want that to be <=C then A\/B <= C^(2^n), which is exactly the formula in the sample answer, so I think my approach is correct and should produce the required results.<\/p>\n
Q3) Given a rectangle patterned with white and black squares, you need to make chessboards, starting with the largest chessboards (which can be larger than 8×8) all the way down to the smallest chessboards (1×1).\u00a0 The largest chessboard available is always taken first, if there are multiple of equal size, top most and then left most are subsequent tie breakers.\u00a0 Small problem set the input size is 32×32, large problem set the input size is 512×512.<\/p>\n
A3) The small problem size isn’t too bad, we can simply brute force it, with a bit of caching to speed things up by a constant factor or 2.\u00a0 The large problem size however is an entirely different story, an O(N^5) solution most certainly isn’t going to cut it.\u00a0 Even an O(N^3) solution will likely fail to run in time.\u00a0 This probably has something to do with the low success rate that this problem had.\u00a0 So can the problem be done in O(N^2) ?<\/p>\n
One trick is to construct the chessboards efficiently, every chessboard is itself a lot of smaller chessboards.\u00a0 We require overlap to ensure consistency, so if you first identify all 2×2 chessboards. Those 2x2s can be used to create 3x3s.\u00a0 3x3s can be used to create 4x4s and 5x5s, 4x4s can be used to create 6×6 and 7×7,5×5 can create 8×8 and 9×9.\u00a0 If we try to race to the largest size and then work our way down filling the gaps in, this has potential. However each time we cut a chessboard out, we need to invalidate efficiently as well, all chessboards which overlap with the area need to be invalidated.\u00a0 I still am not sure this is fast enough – it looks awfully like even with the best care and data structures it’ll be O(N^3) in the worst case.\u00a0 Time to check out the sample solution I think…<\/p>\n
So yes it can be done better than O(N^3), O(N^2 log N) in fact and the solution is very smart.\u00a0 First of all we use dynamic programming to find the largest chessboard which has its top left corner positioned at that location.\u00a0 I’ve seen this before but I’m so rusty I had clean forgotten it.\u00a0 First check if it is the top left of a 2×2 chessboard, if not the answer is 1. Otherwise it is 1+ the minimum of the largest chessboard sizes for each of the other 3 locations in that 2×2 chessboard.\u00a0 If we store each cell into a heap ordered by its largest size, y and x coordinates, we have the order to remove things in, the trick becomes the invalidation due to removal.\u00a0 When you remove an area, every cell in that area now has a largest square of 0, but other cells may need their largest square being updated as well.\u00a0 As it happens since we just removed the largest square, we know that no locations more than double that square away overlap.\u00a0 So the number of locations to invalidate, recalculate and re-add to a heap is 4 times the number of locations removed, and since each cell can only be removed once, the number of invalidations is worst case 4*N^2.\u00a0 Since each invalidation is a heap removal and addition, which is O(log N) each, we get O(N^2 log N)<\/p>\n
All in all I suspect I would have placed in the top 300 in this round. top 400 in the previous. Even allowing for the fact I had a below average run in round 1A I probably would have only made top 400 in that round (maybe 250 on a good day).\u00a0 So it doesn’t look good for getting top 500 and a t-shirt this year unless I do some serious improving.<\/p>\n","protected":false},"excerpt":{"rendered":"
This round needed at least one problem out entirely, and if it wasn’t the third problem you needed the whole second problem or the small input for the third.\u00a0 So it looks like it may not have been quite as easy as R1B. Q1) Given n lines which all start and end with one of … Continue reading GCJ10 R1C<\/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-151","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\/151","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=151"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/151\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=151"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=151"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=151"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}