Hi,

Just wanted to double check if my solutions for Distributed Code Jam practice problems are reasonably correct. This is not the full description, but just ideas on how to solve:

Sandwich

Cut sandwich into number_of_nodes pieces. Every node is responsible for delivering four numbers to central node. Four numbers being "maximum eating from the left", "maximum eating from the right", "total sum", "maximum eating from both ends". Central node having all this numbers can do any algorithm (even O(n^4) if you wish) to come up with an answer, as n is not more than 100 at that point.

Majority

Population is split evenly between every node. Every node sends to central node the best candidate and the runner-up candidate. Central node combines No'1 and No'2 candidates and picks two most frequent (maybe one is enough?). Central node sends request to all other nodes to provide vote count for two most frequent candidates. Nodes respond, central node adds votes up and produces result. (UPD — wrong approach — see in comments below)

Shhhh

I found it most interesting. My solution went like this — we have to go through the whole circle to get the answer, there is no way around it. We want to split work across nodes, but we can't do it evenly, as we don't know where each person sits. Randomization helps (was it intended solution?). I played with numbers a little bit to see that if we have 100*number_of_nodes "key numbers", every node can start from each of it's 100 key_numbers and go right until getting to another key_number. Then send to the central node information in form "from key number x to key number y distance is D". Central node combines all this data and give out result. I think we are protected by statistics from situation where one node might get unusually long sequence leading to TLE.

Load Balance

Classical partitioning problem. I only used 8 nodes for small and 64 nodes for large (not 100). With 52 numbers you can split them into 64 sub-tasks with 45 numbers each. 45 numbers are solvable by "meet in the middle" algorithm for sub sequence sum search. So each node receives 45 numbers and sum to search for. Sum to search for is Total / 2 adjusted depending on whether you include first 7 numbers in this sub-task or not.