Last year, they opened the judge of all the previous problems to anyone who qualified for DCJ before DCJ Round 1. I think they'll do something similar this year!

They are judged during the contest, you can see verdicts in 'View my submissions'.

vector <char> tmp — why is it char?

You could use the straightforward merge algorithm on each node if you knew for certain that you will use segments [l1, r1) and [l2, r2) of the given arrays. To balance the load, set .

And you can calculate these segments for each node using binary search. This problem is equivalent to "take the smallest k elements from these two sorted arrays".

I was thinking a checkbox asking whether you want to automatically submit Large in case Small is right would be useful.

Rough calculation shows 100 * 99 * 98 * 97 * 96 > 10^9, so it takes only about 500 messages for master node :)

Edit:

Below solution will probably time out.

I did not manage to submit the following solution (I needed 10 more minutes, maybe if they extended the contest like Codeforces...):

• Run algo on all nodes except 0.
• Split the sequence equally among 99 nodes.
• Ask for the value 10 times (it may not fit time limit, so maybe ask 5-6 times). And hope that you will get 2 different results within first 6-10 answers.
• Send the results back to node 0, with the indication which node is broken and what is qod.

Sum previous results + run the interval for broken node again on node 0.

I just wonder if finding qod wihtin first 6-10 answers is possible.

Edit: I think my steps 1–5 are actually exactly the same as the above solution by Xellos; he just uses 100 in place of my million.

My solution was similar but perhaps more efficient. (Of course, I still don’t know if I got it right in the end… I spent ages and resubmitted small many times looking for a stupid bug.)

Below is a simplified description. (My implementation is a bit more complicated, but needlessly so.)

1. Designate one node as the master node and the remaining nodes as workers.

2. Compute sums in a standard distributed way. Each node first reads all of its numbers, stores them in an array and adds them up. Then it rereads some numbers a million times. (In fact, it is enough to store the value of one number and reread the same number a million times.) If any of the rereads does not equal the stored value, the node reports to the master that it is broken; otherwise, it reports the sum. The probability of a false negative is 2^- 1000000, a ridiculously small number.

3. The master node adds up all valid sums and reallocates the broken range among the other worker nodes.

4. Repeat step 2.

5. Repeat step 3.

6. Compute sums in a distributed way, but slightly differently:

   sum = 0
   for i in range(start, end):
       v = GetValue(i)
       sum += v
       repeat 1000 times:
           if GetValue(i) != v:
               report value #{i} is broken, prefix sum is #{sum}, my range extends until #{end}
   report all fine, sum is #{sum}

   The probability of missing the broken index is 2^- 1000, which is still plenty small.

7. The master node adds up all valid sums, the prefix sum reported by the newly broken node and the individual values at indices in range(i+1, end) reported by the newly broken node. It then outputs the total.

Each query takes 0.2 µs, so the total time required for the rereads in steps 2 and 4 is just 0.4 s. The maximum range size is about 10⁶ in step 2, 10⁴ in step 4 and 10² in step 6, so the remaining queries take 0.2 s + 0.002 s + 0.00002 s + 0.02 s (for the rereads in step 6). The total time taken by all queries should thus be well below a second.

I'll remember to use parentheses.

I will remember that it's better to submit with cerr-s than try to comment all cerr-s and comment other lines by accident.

I'll remember to think before submitting

I'll rember including cstdlib before using srand.

What do you mean by antagonistic?

I thought I was called. How about this strategy?

Let partition the array into the N/(numNodes/2) size blocks. Then, node 2i+0 will traverse block i from left to right and node 2i+1 will traverse block i from right to left.

Send a block from 2i+0 to 2i+1 and compare these. If two are the same then the block has true values (broken or not doesn't matter). Otherwise, the block has the death position. Process recursively as this comment.

Edit: I missed the fact that broken node can't be used for further queries. What msg555 says below is this thing.

Nore says he has a solution with (2k-1)n nodes and (at most) n^k values : each value should be visited by (2k-1) different nodes, and the intersection of visiting nodes between two values should contain at most (k-1) nodes, the majority of visiting nodes for each value is correct. (I didn't check myself that it is possible with (2k-1)n and n^k). I don't know if it can be distributed well enough. It can be used to solve this round's large with n=3 and k=17, but not the small (it would require 51 nodes).

You are supposed to include it in your code. In Java at least you copy the input class, say the pancakes class for the pancakes problem, and then make the class static. You can obviously change the class, say change GetStackSize() to return 10^8 and GetStackItem() to return whatever you want for input in range [0, 10^8). Then you get somewhat of an idea of how fast your code runs, with the caveat that obviously the function calls do not take the listed times, they are faster. However it is still useful to check correctness (in the sense that there is no runtime exception or anything, obviously it always returns WA), and get a bit of an idea if your code runs way too slow.

Email just sent, results are delayed, noooooooooo ...

Also just to note there are some errors with the scoring. For instance it shows me with 2 wrong tries for E, but in reality I only had 1 wrong try. This is because I submitted a correct solution, and then an incorrect solution, and somehow it counted the incorrect solution as occurring before the correct one. As a result the code shown in the solution download is also for my incorrect submission, rather than the correct one.

I'm pretty sure in most of the problems you may just delete it. I mean nodes can iterate over empty range just fine

I personally solved E faster than D, although it may be because I found E interesting and was able to "bite into" it better, but I agree that E is harder than D — needs a better idea. Maybe the round authors were trying to compensate for E-small being worth more (or just trolling us).

Maybe because of the very easy solution described above: http://codeforces.com/blog/entry/51596?#comment-360193?

Which passed E-large.