zscoder's blog

By zscoder, history, 6 years ago,

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

Good luck to all people participating!

• +42

 » 6 years ago, # |   +43 I really hope they will not make Problem A "Test problem" again. Hopefully test problem will be Problem X or Z.
•  » » 6 years ago, # ^ | ← 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.
•  » » 6 years ago, # ^ |   +31 +1. Please, X or Z would be much more convenient.
 » 6 years ago, # |   +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).
•  » » 6 years ago, # ^ | ← Rev. 2 →   +2 Isn't it 500 best placed?EDIT: Ok, I think I know who asked this question in the Round :p
•  » » » 6 years ago, # ^ |   +8 Swistakk meant: there won't be many more than 500 participants so maybe any large problem would be enough to be in top500.
•  » » » » 6 years ago, # ^ |   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.
•  » » 6 years ago, # ^ |   +18 Wow, ~900 coders have participated, that's consoling :).
•  » » » 6 years ago, # ^ |   0 Out of 3,000 eligible — that's sad.
 » 6 years ago, # |   +15 Let's bet how many points are enough for to qualify (top500).26 points, time 2:30:00
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 I'd bet around 33. Time 3:00:00.
•  » » 6 years ago, # ^ |   0 33 points, time 3:00:33
•  » » » 6 years ago, # ^ |   +3 Almost correct :D
•  » » 6 years ago, # ^ | ← Rev. 3 →   +3 18 pts, 2:00:00UPD: A mistake I made when calculating the summation LOL, should be 26pts (same on time)
•  » » 6 years ago, # ^ |   +3 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.
•  » » » 6 years ago, # ^ |   0 I think that many will fail on large versions. Yes, my bet is exactly B-full + CDE-smalls.
•  » » 6 years ago, # ^ |   0 41 points, time 3:45:51
•  » » 6 years ago, # ^ |   0 I'll go with the still-optimistic "14 points and a fast time" :)
•  » » » 6 years ago, # ^ |   0 They would have to disqualify a lot of people ;p
 » 6 years ago, # |   0 Does the round have T-Shirts?
•  » » 6 years ago, # ^ |   0 Top 500 get T-shirts.
•  » » » 6 years ago, # ^ |   0 Just confirming my understanding of their language, T shirts will NOT be passed on to competitors beyond rank 500 right?
•  » » » » 6 years ago, # ^ |   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
•  » » » » » 6 years ago, # ^ | ← 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..
 » 6 years ago, # |   +20 How to solve E?
•  » » 6 years ago, # ^ | ← 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.
•  » » » 6 years ago, # ^ |   +8 What if all input numbers are the same?
•  » » » » 6 years ago, # ^ |   +13 I send pairs, so it would be the best case possible. Just 12 bytes sent from all nodes to single node.
•  » » » » » 6 years ago, # ^ |   0 Another way is: if there are more than 2 such numbers, send only 2.
•  » » » » » » 6 years ago, # ^ |   +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.
•  » » » » » » » 6 years ago, # ^ |   0 And potentially introduce some bug ;)
•  » » » » » » 6 years ago, # ^ |   0 True, I even typed:unordered_map, 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 :)
•  » » » 6 years ago, # ^ |   0 Doesn't this require reading every number at every node? This doesn't fit in 4 seconds.
•  » » » » 6 years ago, # ^ | ← 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"
•  » » » » » 6 years ago, # ^ |   0 Got it, I misunderstood your message.
•  » » » » 6 years ago, # ^ |   0 You may also distribute it to every nodes!
•  » » » 6 years ago, # ^ |   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 ;-)
•  » » » » 6 years ago, # ^ |   0 I knew it was not Codeforces competition :)
•  » » » 6 years ago, # ^ |   +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.
•  » » » » 6 years ago, # ^ |   +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.
•  » » 6 years ago, # ^ |   +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.
•  » » » 6 years ago, # ^ |   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.
•  » » » » 6 years ago, # ^ |   0 Yeah, but why is this a problem? Every node has to send a single message of 2MB in size back to the master.
 » 6 years ago, # |   +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)?
•  » » 6 years ago, # ^ |   +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.
•  » » 6 years ago, # ^ |   +8 But at any one time there are at most 10^18 crates in the warehouse?
•  » » » 6 years ago, # ^ | ← 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 :)
•  » » » » 6 years ago, # ^ |   0 You have to calculate the answer modulo 109 + 7.
•  » » » » 6 years ago, # ^ |   +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.
•  » » 6 years ago, # ^ |   +13 Aren't there at most 1018 crates? 109 stacks times 109 crates each.
•  » » » 6 years ago, # ^ |   0 There goes my bignum code :( Didn't read the statement carefully.
 » 6 years ago, # |   +18 Does anybody have a sense about how long it will take before people learn whether their Larges are accepted?
•  » » 6 years ago, # ^ |   +8 They said around half an hour.
 » 6 years ago, # |   +10 When will the judging take place?
•  » » 6 years ago, # ^ |   +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."
 » 6 years ago, # |   +10 Let's bet number of accepted larges in last problem (309 submitted). My bet is 50 :P.
•  » » 6 years ago, # ^ |   +18 42
•  » » 6 years ago, # ^ |   +8 26
•  » » 6 years ago, # ^ |   0 100
•  » » 6 years ago, # ^ | ← 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!
•  » » » 6 years ago, # ^ |   +8 That was a big hint: 1GB is about all inputs, that means we need to re-arrange all input.
•  » » 6 years ago, # ^ |   0 15
•  » » 6 years ago, # ^ |   0 70
•  » » 6 years ago, # ^ |   0 Btw, how to solve it?39.
•  » » » 6 years ago, # ^ | ← 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
•  » » » » 6 years ago, # ^ |   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?
•  » » » » » 6 years ago, # ^ | ← 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.
•  » » » 6 years ago, # ^ |   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).
•  » » » » 6 years ago, # ^ |   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?
•  » » » » » 6 years ago, # ^ |   0 Yep, not sure how slow it is. Unfortunatelly, I was unable to test it :-(
•  » » » » » » 6 years ago, # ^ |   0 so, sounds like O(N)
•  » » » » » » » 6 years ago, # ^ |   0 I believe so, however, still getting Rule violation :-(
•  » » 6 years ago, # ^ |   +36 49 ACs XD, sorry guys, I won :D
•  » » » 6 years ago, # ^ |   +21 I see why you missed by 1 — because your large failed. If it didn't you would be exactly spot on. :D
•  » » 6 years ago, # ^ |   +13 Nice bet, Swistakk! :P
 » 6 years ago, # |   +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).
•  » » 6 years ago, # ^ |   +20 8MB per one message.
•  » » 6 years ago, # ^ | ← 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.
•  » » 6 years ago, # ^ | ← 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.
•  » » » 6 years ago, # ^ |   0 Yeah, I faced the very same issue. Now, at least I feel that I am not the only one ;-)
 » 6 years ago, # |   +8 The results are up! To pass, you need 33 points and 2:25:00 penalty.
 » 6 years ago, # |   0 Can anyone tell me why this code fails for D large ? The same code passed for D small.
•  » » 6 years ago, # ^ |   0 Does it get wrong answer or time limit?
•  » » » 6 years ago, # ^ |   0 It gets runtime error. I don't see why it would be so.
 » 6 years ago, # |   +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.
•  » » 6 years ago, # ^ |   +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.
•  » » » 6 years ago, # ^ |   +23 I think it's easy to miss that you can resubmit small inputs after getting AC with no penalties.
•  » » » » 6 years ago, # ^ |   0 Ouch, no penalty? Didn't know that.
•  » » » 6 years ago, # ^ |   +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.
 » 6 years ago, # |   +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 distribution(0, nodes - 1); sends[distribution(generator)].push_back(x);
 » 6 years ago, # |   +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...
•  » » 6 years ago, # ^ |   +13 There is a lot of getting used to in the format.
•  » » 6 years ago, # ^ |   +13 Because it's something new. Not many solved more than 10-20 distributed problems in their life.
•  » » » 6 years ago, # ^ | ← 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.
•  » » » 6 years ago, # ^ |   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.
•  » » » » 6 years ago, # ^ |   +43 That's why you got 7th place.
•  » » 6 years ago, # ^ |   +35 BCD were very easy, however I find E really tricky.
•  » » 6 years ago, # ^ | ← 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.
 » 6 years ago, # |   0 Failed A large, I put everything into a vector for then getting maximum and minimum, memory limit exceeded and no t-shirt = (
•  » » 6 years ago, # ^ |   0 A large? Or B large?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 B large, sorry.10^9 / 20 long long > 128MbEdit: I think that's why the problem is named "Oops", I bet the choice of 20 nodes instead of 100 was on purpose
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 deletedOh sorry, nvm, I'm tired.
 » 6 years ago, # | ← 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.
•  » » 6 years ago, # ^ |   +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.
•  » » » 6 years ago, # ^ |   +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.
•  » » » 6 years ago, # ^ |   +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?
•  » » 6 years ago, # ^ |   +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
•  » » » 6 years ago, # ^ |   0 File "dcj.py", line 17 print ' '.join(x) ^ SyntaxError: invalid syntax This is insane.
•  » » » » 6 years ago, # ^ |   +11 It looks like you're trying to use Python 3 to run a Python 2 script.
•  » » » » » 6 years ago, # ^ | ← 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]').
•  » » » » » » 6 years ago, # ^ |   +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.
•  » » » » » » » 6 years ago, # ^ |   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.
•  » » » » » » » » 6 years ago, # ^ | ← 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...
•  » » » » » » » » » 6 years ago, # ^ |   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.
•  » » » » » » » » » 6 years ago, # ^ |   0 The Linux version was working fine for me.
•  » » » » 6 years ago, # ^ |   +18 Are you using Python 3? If so, try Python 2.7.
 » 6 years ago, # | ← 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.CodeUPD The same code with MASTER = min(2^n, 8) gets AC on the small subproblem, so this is really weird
•  » » 6 years ago, # ^ | ← 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.
•  » » » 6 years ago, # ^ |   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())
•  » » » » 6 years ago, # ^ |   0 Oh, my bad, I didn't notice this was a different b from the one in main.
•  » » » » » 6 years ago, # ^ |   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 :)
 » 6 years ago, # |   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?
•  » » 6 years ago, # ^ |   0 I think that "cp crates1.h crates.h" and recompiling is easier than changing include in code and recompiling.
•  » » 6 years ago, # ^ | ← 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.
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 I use JHelper with tweaked templatesI 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
•  » » » 6 years ago, # ^ |   +5 I think that trying various numbers of nodes is crucial.
•  » » » » 6 years ago, # ^ |   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
•  » » » » » 6 years ago, # ^ |   +8 What about RPS problem today? For me it was important if n > nodes
•  » » » » » » 6 years ago, # ^ |   0 Fair enough
•  » » » » » » 6 years ago, # ^ |   0 if(n <= nodes) nodes =n;
•  » » » » » » » 6 years ago, # ^ |   0 Yea, I did the same. if (id >= (nodes = min(N, nodes))) return 0;
•  » » » » » » » 6 years ago, # ^ | ← 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 bugPS: I would add several spaces to your code, if you ask
•  » » » » » » » » 6 years ago, # ^ |   -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.
•  » » 6 years ago, # ^ |   0 How do you include message.h without raising an error?
•  » » » 6 years ago, # ^ |   0 You can download a code someone submitted and base your own on it.
•  » » » » 6 years ago, # ^ |   0 I meant when testing.
•  » » » » » 6 years ago, # ^ |   0 The exact same way.#include
•  » » 6 years ago, # ^ |   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.
•  » » 6 years ago, # ^ | ← 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.
•  » » » 6 years ago, # ^ |   +10 I heard Windows has symlinks too. Don't quote me on that though.
 » 6 years ago, # |   +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.
•  » » 6 years ago, # ^ |   +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.
•  » » 6 years ago, # ^ |   +18 You know, practice round was there for a reason.
•  » » » 6 years ago, # ^ |   0 It wasn't there when I had free time.
•  » » » » 6 years ago, # ^ |   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.
•  » » » » » 6 years ago, # ^ |   +10 Well, he doesn't.
•  » » » » » 6 years ago, # ^ |   0 No, I spent 3 hours before the actual contest on it. Your premise is false.
•  » » » » » » 6 years ago, # ^ |   0 Ah, sorry, I didn't had enough free time to carefully read all of your comments ;).
•  » » » » » » » 6 years ago, # ^ |   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.
 » 6 years ago, # |   0 Can anyone show me why this solution get Runtime Error? I couldn't see anything wrong with it.Solution
•  » » 6 years ago, # ^ |   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?
•  » » » 6 years ago, # ^ |   +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.
•  » » » 6 years ago, # ^ |   +5 Sending from 0 to 0 is definitely OK
•  » » » 6 years ago, # ^ |   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..
•  » » » » 6 years ago, # ^ | ← 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.
•  » » 6 years ago, # ^ |   +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);
•  » » » 6 years ago, # ^ |   0 Sorry bor bothering you, but could you please also help me with this issue? Thanks in advance!
•  » » » » 6 years ago, # ^ |   0 Carefully looked through your code, but could not figure out what's the problem.
•  » » » » » 6 years ago, # ^ |   0 Thanks so much! Well, that's really weird. Maybe Google had some problems with testing or something?
•  » » » » » » 6 years ago, # ^ | ← 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.
•  » » » » » » » 6 years ago, # ^ | ← 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).
 » 6 years ago, # | ← 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.
 » 6 years ago, # |   +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.
•  » » 6 years ago, # ^ |   0 I have the similar issue with problem C. I've already emailed the organazers.
•  » » » 6 years ago, # ^ |   0 You have a few lists in your code so my bet is that you use too much memory too.
•  » » » » 6 years ago, # ^ |   0 I think you are right, thank you! That's a silly mistake :(
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 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 Eproblem statement
•  » » 6 years ago, # ^ |   0 Maybe vector of 107 longs exceeds ML?
•  » » » 6 years ago, # ^ |   0 Yep. Maybe, but it's 80 MB isn't it? And in the statement the limit is 128MB.
•  » » » » 6 years ago, # ^ |   +8 Array would take 80MB, vector needs a bit more.
•  » » » » » 6 years ago, # ^ |   0 Ok that's it. Thank you. Vector of 10^7 longs is exactly 128 MB, and I used a little bit more.
•  » » » » » » 6 years ago, # ^ |   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.
•  » » » 6 years ago, # ^ |   0 No it doesn't. I used 10^7 longs and got wrong answer.
•  » » » » 6 years ago, # ^ |   +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.
•  » » » » » 6 years ago, # ^ |   0 Oh! You might be right. I used static array.
•  » » » 6 years ago, # ^ |   +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.
 » 6 years ago, # |   +25 Is there anyway to practice for the next round?