Distributed Google Code Jam Round 2

7 лет назад, # ^ |

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.

→ Ответить

Gassa

7 лет назад, # |

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

→ Ответить

W4yneb0t

7 лет назад, # |

← Rev. 2 →

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

Edit: Sorry, I meant D

→ Ответить

Rafbill

7 лет назад, # ^ |

+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]}$ .

→ Ответить

eatmore

7 лет назад, # ^ |

+25

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

→ Ответить

Gassa

7 лет назад, # ^ |

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

→ Ответить

riadwaw

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

+10

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

→ Ответить

riadwaw

7 лет назад, # ^ |

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

→ Ответить

rng_58

7 лет назад, # ^ |

+60

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

→ Ответить

riadwaw

7 лет назад, # ^ |

Indeed, that seems to fail my solution.

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

→ Ответить

Rafbill

7 лет назад, # ^ |

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

→ Ответить

Xellos

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

+56

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

→ Ответить

KAN

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # |

← 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 ^^

→ Ответить

chintu

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

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

→ Ответить

fruwajacybyk

7 лет назад, # ^ |

+15

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

→ Ответить

7 лет назад, # ^ |

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

→ Ответить

Radewoosh

7 лет назад, # ^ |

+20

Yep, I confirm this ;_;

→ Ответить

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

← Rev. 2 →

+20

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

→ Ответить

Radewoosh

7 лет назад, # ^ |

+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

→ Ответить

7 лет назад, # ^ |

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.

→ Ответить

Endagorion

7 лет назад, # ^ |

+10

Just to check, is 998981514 the correct answer?

→ Ответить

7 лет назад, # ^ |

+10

Yes, it is.

→ Ответить

W4yneb0t

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

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

→ Ответить

Endagorion

7 лет назад, # ^ |

Sadly no, I've copypasted my answer.

→ Ответить

Endagorion

7 лет назад, # ^ |

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.

→ Ответить

tourist

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

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

→ Ответить

tourist

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

+18

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

→ Ответить

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

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

→ Ответить

simonlindholm

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

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.

→ Ответить

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

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

→ Ответить