Блог пользователя zscoder

Автор zscoder, история, 8 лет назад, По-английски

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

Good luck to all people participating!

  • Проголосовать: нравится
  • +42
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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).

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    Isn't it 500 best placed?

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

26 points, time 2:30:00

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does the round have T-Shirts?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Top 500 get T-shirts.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

          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..

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

How to solve E?

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      What if all input numbers are the same?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится

            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.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 :)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        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"

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You may also distribute it to every nodes!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 ;-)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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)?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 :)

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You have to calculate the answer modulo 109 + 7.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

When will the judging take place?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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."

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    42

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    26

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    100

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    15

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    70

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Btw, how to solve it?
    39.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +10 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

          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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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).

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

    49 ACs XD, sorry guys, I won :D

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Nice bet, Swistakk! :P

»
8 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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).

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    8MB per one message.

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +30 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +53 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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);
»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

      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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +35 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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
    
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      File "dcj.py", line 17
        print ' '.join(x)
                ^
      SyntaxError: invalid syntax
      

      This is insane.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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]').
          
          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

                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...

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  The Linux version was working fine for me.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +18 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 :)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      I think that trying various numbers of nodes is crucial.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Fair enough

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            if(n <= nodes) nodes =n;

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Yea, I did the same.

              if (id >= (nodes = min(N, nodes))) return 0;
              
            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

              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

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится -15 Проголосовать: не нравится

                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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    You know, practice round was there for a reason.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It wasn't there when I had free time.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

          Well, he doesn't.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Solution

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Sending from 0 to 0 is definitely OK

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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..

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +38 Проголосовать: не нравится

    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);
    
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thanks so much!

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              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).

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +59 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Maybe vector of 107 longs exceeds ML?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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.

»
8 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Is there anyway to practice for the next round?