Reminder that Google Distributed Code Jam Online Round 1 starts at this time.
Good luck to all people participating!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 141 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
I really hope they will not make Problem A "Test problem" again. Hopefully test problem will be Problem X or Z.
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.
+1. Please, X or Z would be much more convenient.
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).
Isn't it 500 best placed?
EDIT: Ok, I think I know who asked this question in the Round :p
Swistakk meant: there won't be many more than 500 participants so maybe any large problem would be enough to be in top500.
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.
Wow, ~900 coders have participated, that's consoling :).
Out of 3,000 eligible — that's sad.
Let's bet how many points are enough for to qualify (top500).
26 points, time 2:30:00
I'd bet around 33. Time 3:00:00.
33 points, time 3:00:33
Almost correct :D
18 pts, 2:00:00
UPD: A mistake I made when calculating the summation LOL, should be 26pts (same on time)
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.
I think that many will fail on large versions. Yes, my bet is exactly B-full + CDE-smalls.
41 points, time 3:45:51
I'll go with the still-optimistic "14 points and a fast time" :)
They would have to disqualify a lot of people ;p
Does the round have T-Shirts?
Top 500 get T-shirts.
Just confirming my understanding of their language, T shirts will NOT be passed on to competitors beyond rank 500 right?
You will get ONE T-shirt if you are in top 1000 in GCJ Round 2 and/or in top 500 DGCJ Round 1
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 [email protected] . Maybe they'll change their mind about it..
How to solve E?
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.
What if all input numbers are the same?
I send <number, count> pairs, so it would be the best case possible. Just 12 bytes sent from all nodes to single node.
Another way is: if there are more than 2 such numbers, send only 2.
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.
And potentially introduce some bug ;)
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 :)
Doesn't this require reading every number at every node? This doesn't fit in 4 seconds.
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"
Got it, I misunderstood your message.
You may also distribute it to every nodes!
To make it theoretically correct, you'd choose a random long
aat the root, send it to all the children and let them use the hash functionx -> a*x % prime % node_countor another universal family.If this had been a Codeforces competition, just using
number % 997 % node_countwith no randomness would certainly have gotten you hacked ;-)I knew it was not Codeforces competition :)
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.
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.
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.
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.
Yeah, but why is this a problem? Every node has to send a single message of 2MB in size back to the master.
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)?
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.
But at any one time there are at most 10^18 crates in the warehouse?
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 :)
You have to calculate the answer modulo 109 + 7.
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.
Aren't there at most 1018 crates? 109 stacks times 109 crates each.
There goes my bignum code :( Didn't read the statement carefully.
Does anybody have a sense about how long it will take before people learn whether their Larges are accepted?
They said around half an hour.
When will the judging take place?
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."
Let's bet number of accepted larges in last problem (309 submitted). My bet is 50 :P.
42
26
100
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!
That was a big hint: 1GB is about all inputs, that means we need to re-arrange all input.
15
70
Btw, how to solve it?
39.
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
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?
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.
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).
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?
Yep, not sure how slow it is. Unfortunatelly, I was unable to test it :-(
so, sounds like O(N)
I believe so, however, still getting Rule violation :-(
49 ACs XD, sorry guys, I won :D
I see why you missed by 1 — because your large failed. If it didn't you would be exactly spot on. :D
Nice bet, Swistakk! :P
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).
8MB per one message.
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.
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.
Yeah, I faced the very same issue. Now, at least I feel that I am not the only one ;-)
The results are up! To pass, you need 33 points and 2:25:00 penalty.
Can anyone tell me why this code fails for D large ? The same code passed for D small.
Does it get wrong answer or time limit?
It gets runtime error. I don't see why it would be so.
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.
You mean C-large. Why didn't you test it on the small input? I did this for every problem and found some bugs.
I think it's easy to miss that you can resubmit small inputs after getting AC with no penalties.
Ouch, no penalty? Didn't know that.
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.
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.
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 (
^ 12345LLis added in case the admins decided to counter this PRNG)I got 7'th place! But why are people so weak in distributed? All of the problems were way easier than in normal rounds...
There is a lot of getting used to in the format.
Because it's something new. Not many solved more than 10-20 distributed problems in their life.
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.
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.
That's why you got 7th place.
BCD were very easy, however I find E really tricky.
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.
Failed A large, I put everything into a vector for then getting maximum and minimum, memory limit exceeded and no t-shirt = (
A large? Or B large?
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
deleted
Oh sorry, nvm, I'm tired.
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
and the Linux version fails to compile with an OS 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.
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.
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:
I used C++ today, and it worked fine with MinGW.
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?
I can't run it in cygwin, but you can run this in windows cmd directly (without that .sh script):
This is insane.
It looks like you're trying to use Python 3 to run a Python 2 script.
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:
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.
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.
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...
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.
The Linux version was working fine for me.
Are you using Python 3? If so, try Python 2.7.
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
I may be wrong, but won't this fail?
b.get(i)seems to contain the index ofa.get(i)in the entire sequence, so this should be something of the forma.get(b.get(i) - start)wherestartis the starting position of your block.for (int i = 0; i < a.size(); ++i) b.add(i);
So I think that b stores indices in the range [0; a.size())
Oh, my bad, I didn't notice this was a different
bfrom the one inmain.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 :)
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?
I think that "cp crates1.h crates.h" and recompiling is easier than changing include in code and recompiling.
I downloaded and extracted the provided tool. There is a directory
dcj_linux. There, I wrote a script: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 nameTODO.hin 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 filelolsample1on 100 nodes.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
I think that trying various numbers of nodes is crucial.
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
What about RPS problem today? For me it was important if n > nodes
Fair enough
if(n <= nodes) nodes =n;Yea, I did the same.
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
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.
How do you include message.h without raising an error?
You can download a code someone submitted and base your own on it.
I meant when testing.
The exact same way.
#include <message.h>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.
I create a symbolic link pointing to the test I want to run:
Linux rules.
I heard Windows has symlinks too. Don't quote me on that though.
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.
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.
You know, practice round was there for a reason.
It wasn't there when I had free time.
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.
Well, he doesn't.
No, I spent 3 hours before the actual contest on it. Your premise is false.
Ah, sorry, I didn't had enough free time to carefully read all of your comments ;).
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.
Can anyone show me why this solution get Runtime Error? I couldn't see anything wrong with it.
Solution
Can you choose the language as C++ so that it highlights correctly?
Few things wrong:
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.
Sending from 0 to 0 is definitely OK
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..
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.
I think you have problem because of this two lines:
You receive data from any node, but get data from specific node. Following code should work
Sorry bor bothering you, but could you please also help me with this issue? Thanks in advance!
Carefully looked through your code, but could not figure out what's the problem.
Thanks so much!
Well, that's really weird. Maybe Google had some problems with testing or something?
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.
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).
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.
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.
I have the similar issue with problem C. I've already emailed the organazers.
You have a few lists in your code so my bet is that you use too much memory too.
I think you are right, thank you!
That's a silly mistake :(
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
Maybe vector of 107 longs exceeds ML?
Yep. Maybe, but it's 80 MB isn't it? And in the statement the limit is 128MB.
Array would take 80MB, vector needs a bit more.
Ok that's it. Thank you. Vector of 10^7 longs is exactly 128 MB, and I used a little bit more.
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.
No it doesn't. I used
10^7longs and got wrong answer.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.
Oh! You might be right. I used static array.
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.
Is there anyway to practice for the next round?