Distributed Google Code Jam Round 2

7 years ago, # ^ |

Huh, that's cruel :o. In my first submission I also got this bug, then found that I do not check exactly that condition and still got WA, because I got another sublte bug. I got lucky I had done that second bug, otherwise I wouldn't have noted that I do not check that digits < base xd.

→ Reply

Gassa

7 years ago, # |

+25

I wonder what's the point of 10-minute timeout for resubmitting large solutions. Do they actually start being tested when there are resources available?

→ Reply

W4yneb0t

7 years ago, # |

← Rev. 2 →

Does anyone have a deterministic (i.e. not hashing) solution for C?

Edit: Sorry, I meant D

→ Reply

Rafbill

7 years ago, # ^ |

+40

Yes, two ranges a and b in two different nodes have one or two differences if and only if we don't have $\text{[math]}$ and $\text{[math]}$ .

→ Reply

eatmore

7 years ago, # ^ |

+25

Yeah, but you shouldn't be doing this modulo 2⁶⁴.

→ Reply

Gassa

7 years ago, # ^ |

Apparently, my polynomial hash modulo 2⁶⁴ passed.
It is hard to counter every possible bad attempt at hashing.

→ Reply

riadwaw

7 years ago, # ^ |

Why wouldn't it? (I mean if you choose multiplier randomly at least)

→ Reply

7 years ago, # ^ |

+10

Is http://codeforces.me/blog/entry/4898 relevant?

→ Reply

riadwaw

7 years ago, # ^ |

I don't think so(or not directly) because you have at most two nonzero elements in this problem.

→ Reply

rng_58

7 years ago, # ^ |

+60

(2⁵⁹, 0, 0, ...) (0-th is nonzero) and (0, 0, ..., 0, 2⁵⁹, 0, 0, ...) (32th is nonzero).

→ Reply

riadwaw

7 years ago, # ^ |

Indeed, that seems to fail my solution.

Didn't think about the fact that big range allows to fail everything such easily

→ Reply

Rafbill

7 years ago, # ^ |

Indeed. I lost 20minutes and 1 penalty because my code to transmit 128bit integers didn't work on the google servers though, and my submission using 64bits integers was accepted...

→ Reply

Xellos

7 years ago, # ^ |

← Rev. 4 →

Yes.

Let's just focus on the subproblem "test if this long number is 0 in base B". Split it into intervals, convert the number in it to the form where all digits except maybe the most significant one are in [0, B). That most significant digit is the "left carry" and nodes are going to gradually send carry values to each other. Compute the number which it must receive from its right neighbour in order to send exactly that left carry (or, if impossible, the number which results in sending left carry + 1); call this number "right carry".

More specifically: if we had L consecutive digits D[1..L] initially, we make a number with L + 1 digits D[0..L]; the most significant is D[0]. Now compute D[1..L] modulo B² = x. If we didn't need to use the modulo (all digits D[0..L - 2] are zero), then the left carry is D[0] and right carry is - x. Otherwise, all digits D[0..L - 2] must be B - 1 (or the number can't be 0 in B); the left carry is D[0] + 1 and right carry is B² - x.

When this interval receives c from the node to its right, it's the same as receiving c - c_r with D[1..L] = 0; the actual carry is (c - c_r) / B^L + c_r (if c - c_r isn't divisible by B^L, the number again can't be 0 in B) and we can send it to the node to its left. In the end, we have to check if the last carry is 0 and if neither node reported fail.

Compute both the left and right carries, then send the actual carries (which depend on each other but that's okay, they can be recomputed in O(1) now) and check if everything is okay.

UPD: To clarify, the first problem is B.

→ Reply

7 years ago, # ^ |

+56

That's the price we have to pay because DCJ always names testrun as A xD

→ Reply

KAN

7 years ago, # ^ |

+103

I wonder why they don't name testrun the last problem, it's strange to solve problems named B..E, and is very inconvenient to discuss the problems afterwards.

→ Reply

7 years ago, # |

← Rev. 3 →

+33

Nanobots was easiest problem for me today xD. Even flags took me longer and half of time I needed to solve nanobots was to note that experiment returns T or N and not 1 or 0 xdd.

I find my idea pretty neat, this was my shortest code today, so here it is:

For simplicity assume that #nodes==100. We divide range [1, 1e12] into 1e7 intervals of length 1e5. I divide these intervals evenly to nodes in random way. Every node counts result in all his intervals. Computing result within one interval takes $\text{[math]}$ where b is number of nanobots there, simple binary search.

EDIT: It passed ^^

→ Reply

chintu

7 years ago, # ^ |

Well, because this question was almost similar to gold from last finals. Your idea is an exact copy of fhlasek's solution of gold :)

→ Reply

7 years ago, # ^ |

← Rev. 2 →

I don't know that problem ;p. However I am a bit afraid that my solution will get TLE :<. I will have to wait for results. EDIT: I am less afraid of TLE because I realized that usleep(1) takes on average 55microsecs, so doing it many times is not a good idea to check for TLE ;p (as I did in testrun)

→ Reply

fruwajacybyk

7 years ago, # ^ |

+15

I learned by reading correct submissions that it was enough to divide interval into 100 even pieces without any randomization.

→ Reply

7 years ago, # ^ |

+53

OMG this is some poor joke... My friend noted it in almost same moment as you. That's an obvious solution that obviously TLEs --__--. Why is it so hard to create tests against first wrong solution that comes to mind?

→ Reply

Radewoosh

7 years ago, # ^ |

+20

Yep, I confirm this ;_;

→ Reply

7 years ago, # ^ |

← Rev. 3 →

+15

Any usernames, please? I tried opening the ones submitted late and didn't find anything like that. I've found one solution splitting the interval into 100 pieces, but it's limiting the number of binary search runs and re-distributing remaining work, which is perfectly fine.

The reason I doubt it is because I have exactly the same "solution" submitted in the last minute on the off chance the tests are crap and it obviously TLE'd. On small doing the work on 10 nodes instead of 1 decreased the time from 1012ms to 998ms, which leads me to believe that they are handling this "solution" properly.

→ Reply

7 years ago, # ^ |

← Rev. 2 →

+20

In other words, it seems to be the solution described in the last paragraph of the analysis.

→ Reply

Radewoosh

7 years ago, # ^ |

+10

No, he isn't re-distributing work, he is just splitting into 100 intervals. Also while checking top20 solutions I've found one which gives WA and another which gives MsgLE... Some rejudge maybe? XD

.h file

→ Reply

7 years ago, # ^ |

He who? eduardische found johnchen902, who does at most 5 * (n / nodes + 1) iterations before reporting to the master node and redistributing the remaining search space.

→ Reply

Endagorion

7 years ago, # ^ |

+10

Just to check, is 998981514 the correct answer?

→ Reply

7 years ago, # ^ |

+10

Yes, it is.

→ Reply

W4yneb0t

7 years ago, # ^ |

My solution gives 998981415, please tell me that's a typo :(

→ Reply

7 years ago, # ^ |

My slow solution on a single node also gives me 998981514 on this test case.

→ Reply

Endagorion

7 years ago, # ^ |

Sadly no, I've copypasted my answer.

→ Reply

Endagorion

7 years ago, # ^ |

Another tough case would be this:

long long GetRange() { return 1000000000000LL; }

long long GetNumNanobots() { return 1000*10000; }

char Experiment(long long size, long long speed) {
    const long long L = 5e11;
    if (speed == GetRange() || size == GetRange()) return 'E';
    if (size <= L) return 'T';
    if (size >= L + GetNumNanobots()) return 'E';
    return size + speed <= GetRange() ? 'T' : 'E';
}

Most people seem to handle this within the (enormous) TL, but I didn't make the functions purposedly slow.

I've also noticed that tourist's code exceeds total message size limit both on your and my cases. Might be a local bug with my environment though.

→ Reply

tourist

7 years ago, # ^ |

+40

Well, my solution always sends at most 4*MAX 8-bit integers (plus a hundred 4-bit ones). In my submission, MAX = 240000, so I expect to send at most 7,68 MB.

In my local environment it does get "message size limit exceeded", though. It works with MAX = 230000, so I suspect that the communication system also sends a byte corresponding to the type of each variable — can someone confirm that? (I haven't read the rules :))

Nevertheless, my submission passed the system test, so maybe there's a difference between local and testing environments.

→ Reply

7 years ago, # ^ |

← Rev. 2 →

+40

I’ve just dug into the source code of the local testing tool, and it does indeed appear that it sends a byte corresponding to the type of each field. It then verifies them on the other end and dies with a “Type mismatch between read and requested types” message if you try to read a wrong type.

This can be disabled by changing the value of the macro DEBUG to 0 in libraries/message_internal.c and rebuilding the tool (or possibly just recompiling message_internal.o; it seems the object files are not linked together, at least in the macOS build that I have at hand). Judging by the macro name, I hope this is disabled in the actual contest, but I don’t think I’ve seen this explicitly mentioned anywhere.

→ Reply

tourist

7 years ago, # ^ |

+83

Hey, your test case is invalid, experiment returns 'T' for points (1, 10¹²) - (99, 10¹²). That explains W4yneb0t's answer — the difference is exactly 99.

→ Reply

7 years ago, # ^ |

+18

Woooo, tourist saves the day by rebutting false accusations against himself and other innocent people, sorry for questioning your power ;)

→ Reply

7 years ago, # ^ |

← Rev. 3 →

adsz is doing it in the most naive way. His code is easily hacked by test posted by Radewoosh if we assume that each call takes 0.2s then his code works for 147s. In fact it runs in 5s, but it is because that particular function is very simple, so it is very fast, but you got the point.

→ Reply

7 years ago, # ^ |

← Rev. 3 →

I see. Then I'm at loss why my attempt at doing exactly that TLE'd: https://pastebin.com/R3uH7qrL. Any ideas? This passes the small, so I was hoping it's not just a bug.

Also, the test that Radewoosh mentioned isn't failing this type of solutions, since the bots are distributed evenly [UPD: Disregard this paragraph].

→ Reply

simonlindholm

7 years ago, # ^ |

The download link for my E-large leads to my old solution (with broken constants). Maybe that could explain things?

→ Reply

7 years ago, # ^ |

Ah, that would explain everything perfectly. adsz also has one wrong answer. Seems like DCJ and the scoreboard does not get along with each other...

→ Reply

7 years ago, # ^ |

That's really strange, however actually, both solutions mentioned by Radewoosh were submitted only once on large. SizeOfMsgLE is tourist's (it seems that even when his codes are not correct then tests are adjusted accordingly to make it work ;p) and WA is W4yneb0t's. However maybe adsz submitted faster solution, he resubmitted it once.

→ Reply

7 years ago, # ^ |

← Rev. 2 →

I was more concerned about naive split not TL'ing. WA and SizeOfMsgLe is the usual "got lucky with the tests", so it's all fair.

→ Reply

7 years ago, # ^ |

I think that adsz carefully adjusted bounds of binary search to be as tight as possible. Are you also doing this?

And bots in Radewoosh's test are distributed not really evenly. They all fall into first interval if I'm not mistaken. Nevertheless, this test caused adsz code to make 737253930 calls on first adsz's node (~147s if one call is 0.2micros).

→ Reply