zscoder's blog

Google Distributed Code Jam Online Round 1
By zscoder, history, 9 years ago, In English

Reminder that Google Distributed Code Jam Online Round 1 starts at this time.

Good luck to all people participating!

  • Vote: I like it
  • +42
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +43 Vote: I do not like it

I really hope they will not make Problem A "Test problem" again. Hopefully test problem will be Problem X or Z.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    No luck with this one. I still think that it is not convenient that what people call "first problem" is actually Problem B, but I am getting used to it already.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    +1. Please, X or Z would be much more convenient.

    → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I wonder whether qualifying to second round will require solving at least one large (or whether it will require getting more than smallest possible nonzero amount of points).

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    Isn't it 500 best placed?

    EDIT: Ok, I think I know who asked this question in the Round :p

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Swistakk meant: there won't be many more than 500 participants so maybe any large problem would be enough to be in top500.

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

        I think you are correct, sorry. Considering that there were like 350 people participating in training rounds + another (some of them the same, but still) 350 people participating last year, we have at most 700 people familiar with the system. So it is definitely not as competitive as the round yestersay.

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Wow, ~900 coders have participated, that's consoling :).

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

      Out of 3,000 eligible — that's sad.

      → Reply
»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Let's bet how many points are enough for to qualify (top500).

26 points, time 2:30:00

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    I'd bet around 33. Time 3:00:00.

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

    33 points, time 3:00:33

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    18 pts, 2:00:00

    UPD: A mistake I made when calculating the summation LOL, should be 26pts (same on time)

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Funny boundary. In the optimistic standings, there are 790 people with 30+, and 791st is 23. Let's see if 26 (B-full + CDE-smalls?) even appears in the standings after testing is over. Of course, your boundary may be exact even if 26 doesn't appear.

    I'll bet a score of 31 with time 99:99:99 will be enough to advance, then.

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

      I think that many will fail on large versions. Yes, my bet is exactly B-full + CDE-smalls.

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

    41 points, time 3:45:51

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

    I'll go with the still-optimistic "14 points and a fast time" :)

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

      They would have to disqualify a lot of people ;p

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does the round have T-Shirts?

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

    Top 500 get T-shirts.

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

      Just confirming my understanding of their language, T shirts will NOT be passed on to competitors beyond rank 500 right?

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

        You will get ONE T-shirt if you are in top 1000 in GCJ Round 2 and/or in top 500 DGCJ Round 1

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 4   Vote: I like it +5 Vote: I do not like it

          Completely rekked. Got rank 524. Had I been a little faster.. :(

          UPD: Only 544 people got a score of 33. Wouldn't it be nice if they change their criteria slightly to giving shirts to everyone with that score? Otherwise too I would guess around 25-30% of top 500 also placed in top 1000 in Round 2 :/

          UPD2: Everyone, please email this to codejam@google.com . Maybe they'll change their mind about it..

          → Reply
»
9 years ago, # |
  Vote: I like it +20 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    Collect same groups of numbers in the same nodes. So for each number there is only one node which sums up counts from all nodes specific to this number. Then each node sends lowest number with count 1 to main node. Main node choses smallest of them (or zero if there are none).

    The only challenge seemed to me to get fair distribution across nodes. If you just send number to node "number % node_count" they will have test case where all numbers will go to the same node. I tried "number % 997 % node_count". Not sure if it was enough.

    EDIT: It was enough. 11th place — first time in my life in any GCJ round. Reason — algorithmically problems were easy, so even I wasn't challenged algorithmically. The only problem was "Distributed Computing patterns", which I specifically trained for.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      What if all input numbers are the same?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        I send <number, count> pairs, so it would be the best case possible. Just 12 bytes sent from all nodes to single node.

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

          Another way is: if there are more than 2 such numbers, send only 2.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            Since you're sending signed numbers anyway, you could also send x if it is present only once, and  - x if it is present multiple times, that would save you ~50% memory.

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

              And potentially introduce some bug ;)

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

            True, I even typed:

            unordered_map<long long, char>, but then my disrepect to "char" made me change it to "int" (as message size constraints were insignificant) and at the point it didn't mean much difference whether to send 2 or actual number :)

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

      Doesn't this require reading every number at every node? This doesn't fit in 4 seconds.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        No, each node takes just portion of input.

        Basically Node A sends message to Node B saying "while processing my portion of input I found these numbers with these counts which belong to you based on hash value"

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

        You may also distribute it to every nodes!

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

      To make it theoretically correct, you'd choose a random long a at the root, send it to all the children and let them use the hash function x -> a*x % prime % node_count or another universal family.

      If this had been a Codeforces competition, just using number % 997 % node_count with no randomness would certainly have gotten you hacked ;-)

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

        I knew it was not Codeforces competition :)

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

      I didn't even consider solutions that involved passing messages containing 100,000+ integers because I somehow intuitively assumed that sending huge messages would incur a delay on the network. Turns out that transfer delays in DCJ are independent of message size.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I also wonder how much the time difference is between sending 100k messages of one int, and one message of 100k ints.

        As long as the price of sending 1 int isn't much more than reading it from the library, it's going to be dominated by that anyway.

        Maybe the most surprising thing is, that you can send n(n-1)/2 messages at the same time, without overloading the network.

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I just did distributed sorting -- sort the numbers in the segment and then pick the minimum out of heap of 100 elements and replace it with the next element. That is O(35M * log 100 + 350K * log 350K). It runs for 12 seconds on my PC, but I don't have 100 cores, so I have hopes that it might pass within the time limit. I couldn't test it on the server, since I was getting weird "Rule violation" errors when trying to submit it for A.

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

      In the worst case you'd have to send all the data to the root? Say every number is present exactly twice, except for a single instance of 10^18.

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

        Yeah, but why is this a problem? Every node has to send a single message of 2MB in size back to the master.

        → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks to everyone for a great competition!

Was there a solution to Crates, that didn't use BigNums? I tried to only use them in the root, but I felt they were needed to handle the large possible flows around 10^(9+9+6)?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    For every prefix, I computed the difference between how many crates are in that prefix versus how many crates should be in that prefix. The sums don't exceed 10^18, and we can take the mod at every step.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    But at any one time there are at most 10^18 crates in the warehouse?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Right, but if you move them 10^6 places, that's 10^24.

      I told each of my nodes how many crates were coming into them, so they could figure out how to distribute them. If a node decided to move all the 10^18 crates all the way through it, it would have to juggle some large numbers. Though now that I think about it, the 'overflow' could never be large, so you are actually right.

      Oh well, then the solution was just buggy :)

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

        You have to calculate the answer modulo 109 + 7.

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        I had the same concerns, until I found the line "1 ≤ GetStackHeight(i) ≤ 10^9, for all i". That means that we can work with long long and modulo is only necessary when adding to the variable, containing the total result.

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Aren't there at most 1018 crates? 109 stacks times 109 crates each.

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

      There goes my bignum code :( Didn't read the statement carefully.

      → Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Does anybody have a sense about how long it will take before people learn whether their Larges are accepted?

→ Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

When will the judging take place?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    From questions: " 3:06:14 We are finishing up our remaining judging and we intend to post the final results within the next half hour or so."

    → Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Let's bet number of accepted larges in last problem (309 submitted). My bet is 50 :P.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    42

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    26

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

    100

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    I didn't understand this:

    Maximum total size of messages a single node can send: 1 GB.

    It's almost four times more then all numbers. Looks like they just wanted to say "unlimited". Or trick people to send too large messages between the nodes and get TLE because of that.

    150!

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      That was a big hint: 1GB is about all inputs, that means we need to re-arrange all input.

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

    15

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

    70

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

    Btw, how to solve it?
    39.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it +10 Vote: I do not like it

      I did the following (upd: got AC):

      Each node gets subarray and preprocess it to the map {number => freq} After that each pair (number, freq) is sent to the node hash(number)

      Each node then gets minimum number with fixed hash and send result to maximum

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

        Maybe I got your explanation wrong, but won't that simply TLE on the test

        1,1,2,2,...,N/2,N/2,N/2+1?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it +10 Vote: I do not like it

          I don't think this test will result in TLE. Why would it?

          Every node sends N/100 numbers and gets about N/100 numbers.

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

      In my approach, the given sequence is divided evenly between nodes and every node is responsible for its elements. It sends its sorted elements to every other node.

      Given the possible candidates at one node (sorted) and all elements from another node you can easily eliminate the candidates, which are present at the other node (in linear time).

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

        One node reads N/100 numbers and if all are different then it sends N/100 numbers to each of other 99 nodes? What did I understand wrong?

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

          Yep, not sure how slow it is. Unfortunatelly, I was unable to test it :-(

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

            so, sounds like O(N)

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

              I believe so, however, still getting Rule violation :-(

              → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    49 ACs XD, sorry guys, I won :D

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      I see why you missed by 1 — because your large failed. If it didn't you would be exactly spot on. :D

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Nice bet, Swistakk! :P

    → Reply
»
9 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Hey, is there a per-message size limit different from the total message size limit? I feel that I was getting Rule violation when sending too many messages in problem E (despite it was basically unlimited).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    8MB per one message.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +30 Vote: I do not like it

    Same problem – got Rule Violation for submitting max test for E.large for A. Technically, I should be within the memory limits for A – I was only sending a single message of 2MB from every node.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +53 Vote: I do not like it

    I was being hit by the same thing. All responses to my questions about this issue denied it was happening :(

    I have two identical submissions on Testrun. One attempts to send a single 500 kB message and gets Rule violation. The other sends 50 times a 10 kB message and works.

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

      Yeah, I faced the very same issue. Now, at least I feel that I am not the only one ;-)

      → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The results are up! To pass, you need 33 points and 2:25:00 penalty.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why this code fails for D large ? The same code passed for D small.

→ Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Ah, so silly mistake in B-large pushed me out of top-500 to place 659 :( I forgot to shift node's winner id by node base id.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    You mean C-large. Why didn't you test it on the small input? I did this for every problem and found some bugs.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      I think it's easy to miss that you can resubmit small inputs after getting AC with no penalties.

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

        Ouch, no penalty? Didn't know that.

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Oh right it was C-large :)

      Well, it was the exact same code (kinda "tested"), but it used a single node to solve every case where N <= 22. Other logic was the same — master node to accumulate results, etc. Agreed that I should have tested it better, or just write it in the way that small cases work absolutely the same way as large ones.

      → Reply
»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I got 100 and ranked 16. Here are my solutions:

B) Simply divide the N numbers into Nodes approx equal length subarrays for the slaves. Each slave sends the subarray max and min to the master. The master computes global max and global min and output global max — global min.

C) Two cases: N <= 22 and N > 22. If N <= 22, use single node version (same as small). If N > 22, use 2 ^ (N — 22) nodes, that is, 64 nodes when N = 28. Node i shall be responsible for [(2^22) * i, (2^22) * (i + 1)). Return the winning index to a master.

Then, the master gets all winning indices call GetFavoriteMove on the indices. Perform the tournament again with N' = N — 22.

D) Divide the N numbers into Nodes approx equal length subarrays for the slaves. Each slave broadcast its subarray sum to every other node. Therefore, each node can reproduce the partial sum upto the left boundary of its subarray. Also compute the required partial sum up to the left boundary. The difference (required — current sum) is what has to be deduced from the left position of the subarray. Simulate over the subarray to compute the answer for the node. Send the answers to a master to sum them up.

long long last = -(required[me] - psum[me]);
long long ret = 0;
for (long long i = l; i < r; i++) {
  long long t = GetStackHeight(i + 1) + last;
  long long u = p + (i < q);
  ret += abs(t - u);
  ret %= 1000000007;
  last = t - u;
}

E) Divide the N numbers into Nodes approx equal length subarrays for the slaves. For every number x, compute hash(x) that gives a number between 0 .. Nodes — 1 inclusive. Send the number x to Node hash(x). Note: gather all the numbers to the same destination Node and send them in 1 message using this format: (size of vector) v[0] v[1] v[2] .... Also, don't send the same number more than 2 times.

Now each slave should receive numbers x that has hash(x) = MyNodeId. Use map or whatever count each number's frequency. Send the smallest one that has freq = 1 to a master (if there is one).

The master should gather the numbers and return the smallest one. (again check if there is one).

Here is my hash function (^ 12345LL is added in case the admins decided to counter this PRNG)

mt19937_64 generator(x ^ 12345LL);
uniform_int_distribution<int> distribution(0, nodes - 1);
sends[distribution(generator)].push_back(x);
→ Reply
»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I got 7'th place! But why are people so weak in distributed? All of the problems were way easier than in normal rounds...

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    There is a lot of getting used to in the format.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Because it's something new. Not many solved more than 10-20 distributed problems in their life.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      Yea, also language restrictions. I normally code in C#, and I have to learn Java just for this round. Started practicing it yesterday :) I'd say I was 2-3 times less productive with it, because I wasn't familiar with infrastructure and so on. Have some hard times testing and debugging my code.

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

      I wrote my first distributed code during the practice last week and I don't see what's the big difference from normal programming. All you have to do is to picture the flow of information and then write it down like you always do, just that now we have two new functions which allows us to distribute the load.

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    BCD were very easy, however I find E really tricky.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +23 Vote: I do not like it

    The main factors for me were that, first, of course the main difficulty is very different from the main rounds -- algorithmically none of the problems were hard, the problem is just distributing chunks in a way that all nodes do more or less the same amount of work.

    Second, it's much harder to tell whether a solution works or not (how many messages can we send? A few big messages are faster than many small messages, but by how much, and how fast is one small message compared to one big message?) The benchmarks help a little, but it's no substitute for definite experience, and Testrun giving rule violations did not help matters. I didn't consider rearranging all values for E because I thought I didn't have time to send that many values.

    Also significant is that it's much trickier to code in these rounds, and it's much harder to debug when a problem does happen. For instance, memory limits are a big problem here, and in regular code jam it's a nonissue.

    And finally, I do think E was actually tricky.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Failed A large, I put everything into a vector for then getting maximum and minimum, memory limit exceeded and no t-shirt = (

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

    A large? Or B large?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      B large, sorry.

      10^9 / 20 long long > 128Mb

      Edit: I think that's why the problem is named "Oops", I bet the choice of 20 nodes instead of 100 was on purpose

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Does anyone know how to make the provided localtesting systems work? I tried both the Linux and Windows version in both Windows cmd and Cygwin, then the Linux version on pure (non-emulated or anything) Linux. The Windows version compiles successfully, but when ran, the program gives a failed assert

STDERR 0: assertion "cmdin != NULL" failed: file "[...]/dcj/../libraries/zeus_local.c", line 67, function: Init

and the Linux version fails to compile with an OS error

Error when executing command (u'[...]/dcj/../executable/parunner', '--n', '10', '--stdout', 'tagged', '--stderr', 'tagged', '[filename]'): OSError(8, 'Exec format error').

I tried to fix this until about 10 minutes into the contest, then gave up and compiled (or failed to compile) by submitting for the rest of the contest.

I'd like to be able to upsolve without resorting to this masochism.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I got the same error but MinGW worked.

    "To make Java work on Windows, you will have to modify paths and commands in build.py. We are working on a version which would work for common Windows configurations. One option is to use MinGW instead of cygwin. Make sure to add MinGW's environment path before cygwin's. Then, "python dcj.py test --source sandwich.cpp --nodes 10" works (because we can't use shell scripts in MinGW)."

    It seems this is required for C++ too.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      BTW I couldn't make Java work on Windows, whereas it works on Linux on my work computer (you still had to fix the JDK_HOME/include issue — I copied some .h files from that directory to the parent directory and it worked).

      This is the error I'm getting now with Java:

      Error when executing command (u'javac', 'D:\\Programming\\dcj\\dcj\\..\\libraries\\Wrapper.java', 'Main.java', 'D:\\Programming\\dcj\\dcj\\..\\libraries\\message.java', 'D:\\Programming\\dcj\\dcj\\..\\libraries\\messageJNI.java', u'-classpath', 'D:\\Programming\\dcj\\dcj\\..\\libraries:D:\\Programming\\dcj'): WindowsError(2, '').

      I used C++ today, and it worked fine with MinGW.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Ugh. I've spent way more time on this shit than the contest itself, it's just a different kind of masochism.

      Why doesn't it work in Linux, then?

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I can't run it in cygwin, but you can run this in windows cmd directly (without that .sh script):

    python dcj.py test --source src/sum/code.cpp --nodes 10
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      File "dcj.py", line 17
  print ' '.join(x)
          ^
SyntaxError: invalid syntax

      This is insane.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        It looks like you're trying to use Python 3 to run a Python 2 script.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Oh, yeah, it seems Windows doesn't make the distinction between Python 3 and Python 2 like Linux does (I can't think of a single good reason for this). And I have to install Python 2.7 because for some reason, the only version of 2 I have is 2.6.

          UPD: I run it with the right Python (manually set path) now. Now the bad news:

          Error when executing command ('gcc', '-O2', '-lm', '-static', '-I[path]\\dcj\\..\\includes', '[path]\\dcj\\..\\libraries\\zeus_local.c', '-c', '-o', '[path]\\dcj\\..\\libraries\\zeus_local.o'): WindowsError(2, 'File not found [translated from Slovak]').
          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            Is gcc in your path? If all else fails, you can simply try executing the same command the Python script is trying to run in a command line yourself and see what error you get.

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

              Cygwin /bin is in my path (and MinGW /bin should also be there now, but I observed no changes to the errors), gcc should be there.

              Did you see the script's insides? There is no sequence of hardwired commands to run, so to me, it's a big mumble-jumble. I tried to reverse-engineer it even before the contest, but found that I have a better chance of reading Assembler code.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                ← Rev. 2   Vote: I like it +10 Vote: I do not like it

                It's telling you the command it's running right in the error message: 'gcc', '-O2', '-lm', '-static', '-I[path]\dcj\..\includes', '[path]\dcj\..\libraries\zeus_local.c', '-c', '-o', '[path]\dcj\..\libraries\zeus_local.o'

                The script this year is much better than last year, when we had only the Linux version and I had to reverse-engineer it to make it work in Windows, but setting up environments is still nasty either way...

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

                  I would've welcomed a working Linux version, in fact. My original comment lists the error I got in pure Linux.

                  The problem was that I really needed to add MinGW, nothing works without it.

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

                  The Linux version was working fine for me.

                  → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        Are you using Python 3? If so, try Python 2.7.

        → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone say what is wrong with my submission for C-large? I used min(2^n, 64) slaves to calculate the results on subarrays, and send the winner information (his favourite character and index) to the master node. On the master node, I solved the initial problem for min(2^n, 64) players.

Code

UPD The same code with MASTER = min(2^n, 8) gets AC on the small subproblem, so this is really weird

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I may be wrong, but won't this fail?

                      char c1 = a.get(b.get(i));
                  char c2 = a.get(b.get(i+1));

    b.get(i) seems to contain the index of a.get(i) in the entire sequence, so this should be something of the form a.get(b.get(i) - start) where start is the starting position of your block.

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

      for (int i = 0; i < a.size(); ++i) b.add(i);

      So I think that b stores indices in the range [0; a.size())

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

        Oh, my bad, I didn't notice this was a different b from the one in main.

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

          Sorry for such an ugly code, I was fixing exactly the bug, that you've described, and it seemed like the easiest way to do this :)

          → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you test your solutions?

I wrote a script that changes an include in a cpp file (i.e. changes "crates.h" to crates1.h"), and then runs the original dcj.py with new temporary cpp file (which has a correct include).

I run the script as follows: > python __run.py crates.cpp crates1.h 2 — the parameters are .cpp file, .h file and the number of nodes. I only change the last digit in the library name and the number of nodes.

Maybe I missed something and there is an easier way?

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

    I think that "cp crates1.h crates.h" and recompiling is easier than changing include in code and recompiling.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I downloaded and extracted the provided tool. There is a directory dcj_linux. There, I wrote a script:

    cp $1 TODO.h
./dcj.sh test --source pro.cpp --nodes $2

    and I've copied my templates into a file pro.cpp. Now I can copy my folder when I start a new problem. After copying I must by hand change name TODO.h in a script into e.g. oops.h (problem name). And I also by hand change #include "TODO.h" in my code into e.g. #include "oops.h".

    Then, I can run my program with: ./script lolsample1 100 — this one runs my program for input in file lolsample1 on 100 nodes.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I use JHelper with tweaked templates
    I put headers as tests, and for each test it just creates header and run the code. (I don't usually change the number of nodes)

    Note very convenient, but still I don't have to run each test separately

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I think that trying various numbers of nodes is crucial.

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

        Well, I don't remember any problem where it's important anything except it's > 1.

        But maybe it's a good idea to add loop on number of nodes

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          What about RPS problem today? For me it was important if n > nodes

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

            Fair enough

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

            if(n <= nodes) nodes =n;

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

              Yea, I did the same.

              if (id >= (nodes = min(N, nodes))) return 0;
              → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
              ← Rev. 3   Vote: I like it 0 Vote: I do not like it

              Well, I don't think that Errichto had problem with implementing this, but it was a good point that testing on different number of nodes could help find the bug

              PS: I would add several spaces to your code, if you ask

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                  Vote: I like it -15 Vote: I do not like it

                It's C++, not Whitespace...

                Yeah, I suppose, based on the way of splitting. I immediately used just (the maximum power of 2 not greater than N) nodes.

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

    How do you include message.h without raising an error?

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

      You can download a code someone submitted and base your own on it.

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

        I meant when testing.

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

          The exact same way.

          #include <message.h>

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

    I find most of supplied testcases useless (except as additional way to understand problem statement better). It's usually 3-5 items. For 100 nodes. So I usually just end up writing up some random generated large input. Or not exactly random — like in "crates" I was testing on N piles with N, N-1, N-2 and so own height. In E I was testing with 70,000,000 players distributed over 2 nodes each producting n+1 as number. So I knew correct answer of 1 and could see (by using PARunner statistics) how big messages were sent between nodes.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    I create a symbolic link pointing to the test I want to run:

    ln -fs 01.h crates.h
dcj test --source main.cpp --nodes 5

    Linux rules.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I heard Windows has symlinks too. Don't quote me on that though.

      → Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I finally managed to make MinGW work. Thanks guys. But the Windows version should get renamed to MinGW version and the Linux version should include a list of tested situations where it actually works.

Debugging time: 5 minutes. Trying to get the system to work: 5 hours.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I feel your pain. I've spent a few hours during the practice rounds modifying the dcj script to make it work and I wrote some additional scripts to switch between problems.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    You know, practice round was there for a reason.

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

      It wasn't there when I had free time.

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

        If you preferred to try getting environment to state where you are able to solve "a+b" problem during actual contest then you can't blame anybody other than you.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          Well, he doesn't.

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

          No, I spent 3 hours before the actual contest on it. Your premise is false.

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

            Ah, sorry, I didn't had enough free time to carefully read all of your comments ;).

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

              The real problem I have is that it took me way too much time that could've been spent better. If I hadn't tried anything before the contest (and it would've given me about the same result), that would have been a good thing.

              → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone show me why this solution get Runtime Error? I couldn't see anything wrong with it.

Solution

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

    Can you choose the language as C++ so that it highlights correctly?

    Few things wrong:

    • You're sending from node 0 to node 0
    • "Receive(-1)" on line 57 wth is that?
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Part with sending from node 0 to node 0 is actually OK. Well, yesterday I faced distributed problems first time in my life, reading guide right during round and sending code without an opportunity to compile it locally, writing half of it in notepad... So I can't say it for sure :) But for me it worked OK.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Sending from 0 to 0 is definitely OK

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

      Receive(-1) waits for any other node to send some message. That is, the source can be anything in range [0, NumberOfNodes()]. Not sure how he uses it, but it shouldn't be a source of error because yesterday when due to some bug my code was never receiving any message from other nodes, it got TLE..

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        There's still some issue at that line, as he put the "Receive" inside while loop. Though I think you're probably right and he should have got TLE for that.

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    I think you have problem because of this two lines:

    Receive(-1);
ll x = GetLL(node);

    You receive data from any node, but get data from specific node. Following code should work

    ll source=Receive(-1);
ll x = GetLL(source);
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry bor bothering you, but could you please also help me with this issue? Thanks in advance!

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

        Carefully looked through your code, but could not figure out what's the problem.

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

          Thanks so much!

          Well, that's really weird. Maybe Google had some problems with testing or something?

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            I suspect it's Receive(-1). I've read your code and didn't find anything too, except that I didn't use Receive(-1) in my solutions and all of them passed :) What if you replace it with Receive(cnt)?

            One more thing is that ML is 128 MB, but lots of Integer and Character objects may consume more. Replace them with arrays. I got Runtime Error when I stored all numbers in std::vector in the first problem, luckily I noticed it and resubmitted.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              Thank you for your time :)

              Well, the documentation says, that "You can call Receive(-1) to retrieve a message from any source".

              Unfortunately, I had no time to make local testing tool work, so I can't check what happens if I change this line. But it worked fine on C-small submission (with MASTER equal to 8).

              → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +59 Vote: I do not like it

I liked this round.

The first problem (B) came with sample code (correct but slow). It was a good starting point if one has been completely clueless what to do. I used it as a template, and didn't have to look at the documentation while solving the problem. Edit: It exposed not only the code itself, but also various ideas, such as taking the index modulo nodes, or making the master node do routine work and master work, instead of being a master exclusively.

Overall, the problems were a lot more approachable than in the previous year's round. As I had no experience in distributed computing, I remember feeling clueless there, and the change in difficulty this year felt nice. I wonder whether Distributed Round 2 will be of the same difficulty as the previous year's only round.

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Possibility of upsolving or another practice round with all problems from previous rounds would be great.

My D-large failed with a RTE-message, the same code gets OK on D-small.

I have no idea what went wrong. It would be great to findout the bug before the 2nd round, to avoid the same problem.

Here is my code: http://pastebin.com/FcFEH6Rz any ideas?

Nice round, btw. Simple problems fitted very well.

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

    I have the similar issue with problem C. I've already emailed the organazers.

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

      You have a few lists in your code so my bet is that you use too much memory too.

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

        I think you are right, thank you!

        That's a silly mistake :(

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I also have similar "bug" but in round A. I don't know what is the reason, but code is much shoter. May someone else could find:)

      Round A task E

      problem statement

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

    Maybe vector of 107 longs exceeds ML?

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

      Yep. Maybe, but it's 80 MB isn't it? And in the statement the limit is 128MB.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Array would take 80MB, vector needs a bit more.

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

          Ok that's it. Thank you. Vector of 10^7 longs is exactly 128 MB, and I used a little bit more.

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

            Yes, this is because of dynamic resizing. After it gets one item over 64MB it jumps to 128MB. I didn't think about this potential problem, but I used exact size of vector from beginning and didn't use push_backs. So didn't run into this problems.

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

      No it doesn't. I used 10^7 longs and got wrong answer.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        With vector too? On maxtest on testrun? Because getting WA after submitting problem means that there exists a test where your program prints incorrect answer. Still, for bigger test it may get MLE.

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

          Oh! You might be right. I used static array.

          → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      My solution with vector passed, but I (luckily?) used resize instead of push_backs. Looks like vector after 10^7 push backs uses >130MB (http://ideone.com/ONOiDH) but with resize / size initialization just the expected 80MB.

      → Reply
»
9 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Is there anyway to practice for the next round?

→ Reply