{"id":845,"date":"2016-06-12T11:32:42","date_gmt":"2016-06-12T11:32:42","guid":{"rendered":"http:\/\/www.themissingdocs.net\/wordpress\/?p=845"},"modified":"2016-06-12T11:32:42","modified_gmt":"2016-06-12T11:32:42","slug":"distributed-code-jam-2016-round-1","status":"publish","type":"post","link":"https:\/\/www.themissingdocs.net\/?p=845","title":{"rendered":"Distributed Code Jam 2016 Round 1"},"content":{"rendered":"

So this year, the structure is a bit different 2 rounds before the grand final for distributed and more people eligible to compete in DCJ.<\/p>\n

As usual I’ve been busy, so Round 2 is almost about to happen, I figured it was time to write up my analysis of Round 1.<\/p>\n

Unlike round 2 of the main code jam, I think I would have had a chance of advancing to round 2 of DCJ this year if I was competing. \u00a0I usually say there is practically no chance of me writing up 4 solutions in 3 hours, but this round the questions seemed pretty easy (except for the large of the last one), so I think there would have been a real chance of me getting a top 200 placing.<\/p>\n

Q1) Given some inefficient source code, write an equivalent, but efficient version.<\/strong><\/p>\n

A1) So the detail is of course in the provided source code. \u00a0It is of course a bit convoluted, but the net result is its calculating the largest difference between any two values in the input.<\/p>\n

Of course the best way to do that is to calculate the global maximum and global minimum and take their difference. \u00a0The large input there is too much data to do this all in one node (of course), but if you break the input in to approximately equal chunks per server, each server calculates min\/max – sends to central server which calculates the min of mins and max of maxs. \u00a0Then the difference of those two is the largest difference and that central server can print it out.<\/p>\n

I suspect the biggest chance of failing this question is in breaking up the input incorrectly. \u00a0Its a very common task in DCJ, you always want to keep the code around to do this, you need to handle cases where there is less input then there are nodes, or if you try to allocate equal size to each node that some nodes won’t get any. \u00a0If you want to get tricky and try dividing up the input by modulo rather than blocks (which can seem\u00a0easier) remember to write your loop using += modulus rather than checking every number against the mod. \u00a01 billion divisions is going to time out…<\/p>\n

Another risky move would be to read all the values you need into memory rather than just calculating the min\/max on the stream of values as you read them in. \u00a0This should only take 80MB of ram per node in the worst case, but if you are using a doubling resizeable data structure like vector, you will be very likely to hit 128MB instead, maybe even higher… \u00a0Reserve the required space to avoid this.<\/p>\n

Q2) Determine who wins a giant rock paper scissors competition if everyone always plays a specific move, and in case of draws the person with lower id wins.<\/strong><\/p>\n

A2) The large input size is only 2^28 unlike the 1 billion for the first problem, but its still easily\u00a0large enough for you to time out if you tried to read all of the values on a single node. \u00a0Breaking the input up in to approximately equal chunks across all servers is not a good strategy this time, a much better option is to break it up into a number of exactly equal chunks which is the largest power of 2 which is less than the number of servers. \u00a0This means each server is running its own isolated competition with a single winner. \u00a0Each single winner can then be passed to the central server and it can continue from there.<\/p>\n

This one doesn’t seem very risky so long as you break your input up by powers of two. \u00a0Only 4 million characters, you can read them all in to memory, and even not bother reserving, or reusing vectors as you run the contest (even if you happen to be using 16bit characters…). \u00a0Run time should be pretty fast too.<\/p>\n

Q3) Determine the minimum number of moves to restructure a bunch of piles of crates to have the specified almost uniform height across all piles. (All equal, or one higher for some of the earlier stacks if the total isn’t exactly dividable amongst the number of stacks.<\/strong><\/p>\n

A3) Definite step up in difficulty here. \u00a0The contest analysis describes one approach, I’m going to describe a slightly different one which I think is a bit simpler logically, although its a bit more difficult to code to be fast enough…<\/p>\n

First phase we need to know how high each stack should be. \u00a0To know this we need to know how many crates there are in total. \u00a0So every node takes a chunk and sums it up and sends to central server which sums the sums, and then rebroadcasts that grand total back to everyone…<\/p>\n

The core trick the problem is that because the crates can only be moved one at a time to a neighbouring stack, the problem can be solved left to right one stack at a time. \u00a0First stack knows how high it should be, how high it actually is. \u00a0If its too high, k moves to move the excess to the next. \u00a0If its too low,\u00a0it needs to steal from its neighbours to the right, so walk right stealing until you have enough. \u00a0Steal from the closest first, and as you get further away you each steal costs multiple moves to move through all the intervening stacks.<\/p>\n

For the distributed version each node needs to solve in isolation to be fast enough, so at some point you are going to dump a bunch of crates on to the next server, or you are going to need a bunch of crates from the next server. \u00a0For the purposes of stealing once you get the edge you just assume the other server will have moved them in to your last stack and you can count the cost of moving them from that stack to the right locations.<\/p>\n

So, since each server will need to know the flow at the serve edge to calculate the correct value, the central server might as well calculate that while its calculating the grand total. \u00a0Since all it needs to work that out is know what the desired height total for each server is, and the total. \u00a0Since it just worked out the grand total, the desired height total for each server isn’t much harder, with the one corner case of the server where the desired height changes. \u00a0Then going from left to right comparing the sum to the desired total it can work out the flow to the next server, and assuming the flow and next sum and compared to the next desired total it can determine the next flow after that….<\/p>\n

It then shares the flow to server before and server after to every server. \u00a0The initial and final flows are of course 0.<\/p>\n

Each server node then can process left to right. \u00a0First deal with the flow. \u00a0Positive flow in to this node you just add to the corresponding edge node. \u00a0Negative flow you start the standard stealing process to calculate. \u00a0Remembering to track the cost.<\/p>\n

Once the flows are fixed\u00a0you can just solve the problem locally given the desired height calculated from the grand total.<\/p>\n

Gotchas to watch out for.<\/p>\n

    \n
  1. Stealing from neighbours can cause you to run too slow if you try to check the same set of neighbours over and over. \u00a0You need to keep track of where you have already picked clean, and start one right of that any time you need to steal to ensure that the local calculation part is linear in the size of the section assigned.<\/li>\n
  2. Even though each stack size is only up to 1 billion, the flows calculated can be in the hundreds of millions of billions. \u00a0Therefore you must use 64 bit entries. \u00a0Given each node is dealing with up to 10 million entries, this means you must reserve to avoid the risk of hitting 128MB.<\/li>\n
  3. Because of the large flows that can travel across\u00a0nodes, when stealing the cost calculated from a single steal can overflow 64 bits. \u00a0Either do the product with 128bit types, or (more sensibly) ensure that you mod the number of crates\u00a0being moved before you multiply by the distance moved.<\/li>\n
  4. Mod everywhere – the product I mentioned above is the biggest individual risk, but there are plenty of other ways to overflow if you don’t remember to apply the mod during the process and not just at the end.<\/li>\n<\/ol>\n

    Q4) Determine the smallest positive integer in a set which is unique.<\/strong><\/p>\n

    A4) The small can be run on a single node, and is easy to write. \u00a0Just read the values in, sort them, return the first which is not equal to one of its neighbours. \u00a0Or zero if you get to the end of the array.<\/p>\n

    The large is only 35 Million, which if it wasn’t for the memory limit is\u00a0almost able to be processed in the 4 second time limit… \u00a0Well, maybe it would need 7-8 seconds…<\/p>\n

    The contest analysis solution is much safer, rather than trying to do a distributed merge sort, break the problem in to chunks and then combine the results. \u00a0Unlike the other problems where the chunks are segments of the input stream, (or stripes if you like for the first problem)\u00a0the appropriate chunks depends on the input. \u00a0In order for each section of input to be processed independently, we need to be sure that all duplicates of any given number are processed by the same node. \u00a0This can be achieved by a hash function. \u00a0Each node processes a segment, and after locally separating the dupes from the uniques, forwards values to other servers based on their hash. \u00a0Each server then receives a\u00a0two sets of values from other servers, the uniques and the dupes. \u00a0Since it now knows all copies of a specific value are together, it can make a call as to the lowest unique which has a specific hash assigned to this server. \u00a0It sends these locally lowest definitely globally unique values to the central server, which can then calculate the global lowest.<\/p>\n

    With the relatively small input size, if you are using all 100 nodes it would seem that there is no risk of running out of ram following the general strategy described above. \u00a0But if you don’t reduce the input sent to specific servers by hash down to the two sets and instead send all the values, a single server can easily be overwhelmed by the input case where all the values are the same. \u00a0If your hash is terrible (ie mod 100), similar problems can be had. \u00a0But if your hash is decent, and you do correctly filter the data down before sending it on, it should be pretty safe.<\/p>\n

     <\/p>\n","protected":false},"excerpt":{"rendered":"

    So this year, the structure is a bit different 2 rounds before the grand final for distributed and more people eligible to compete in DCJ. As usual I’ve been busy, so Round 2 is almost about to happen, I figured it was time to write up my analysis of Round 1. Unlike round 2 of … Continue reading Distributed Code Jam 2016 Round 1<\/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],"tags":[],"class_list":["post-845","post","type-post","status-publish","format-standard","hentry","category-code-competitions"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/845","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=845"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/845\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=845"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=845"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=845"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}