arasmus's blog

By arasmus, history, 7 years ago, In English

Since know I have your attention.Can someone please explain how in the world do you go about solving a distributed codejam question? (Specifically ... how to write code ? ... what are messages and nodes ?...) There seems to be no meaningful tutorial available for it online .

  • Vote: I like it
  • -40
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +30 Vote: I do not like it

The main idea behind DCJ is, that you have to solve a huge task. So huge, that processing it on only 1 processor is way too slow. It would take multiple minutes to run, even with the most optimal algorithms and every optimization.

To speed up the solution, you have to distribute the task onto multiple processors (nodes). Each of which computes a subtask, and at the end you combine the results.Each of the nodes has an ID, so you can distinguish between the nodes. Your program will be run on each of the nodes in parallel.

To distribute the task, collect the intermediate results, ... you will need to communicate between the different processors. That's what messages are for. You can send a message (usually one or multiple ints) from any processor to any other processor.

Here is one easy example of such a program: code. The task is to sum up a huge number of integers. The idea is simple. Instead of one processor summing up all integers, each node sums up only a part of the integers. And at the end node 0 sends his result to node 1, node 1 sends the sum of his result and the result of node 0 to node 2, node 2 sends the sum of his and the sum of the previous nodes to node 3, ... And the last node prints the result.

If you have 100 nodes, then the program will execute about 100x faster than only with 1 node.

Here you can find a lot more information about the available functions, how to test the program locally, and much more: Quick-Start Guide: DCJ

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    And DCJ doesn't suck.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Fantastic. Thanks to you DCJ sucks a little less now