Да, в арене написано: Single Round Match 691 will start in 5 hours 52 minutes.

About 500:

Try this test

{3, 1}

{2, 1}

1000

It's better here to do {1, 1} first, and {3, 2} second.

250: I pictured it as if it was a directed graph with edges i -> a[i]. I've found all vertices reachable from 0 and 1 by following those edges, let's call those A and B respectively, and their common part C.

If C is empty then 0 and 1 are in different components at the beginning, and we need to choose at least one vertex from A and at least one from B, and all such choices are good. If they have some common vertices, then a choice is bad only if we choose some vertices from C, but they will all be in A \ B, or all in B \ A.

So in both cases it's a simple formula depending only on size(A), size(B), size(C).

500: Both halves must be sorted according to this criteria, but not the entire array. If there are just two elements then it's optimal to sort them according to something like B/(A+X).

I don't know if this counts, but here is an idea.

I had a 4-dimensional DP (total numbers passed; number of people in the first half; sum of B in the first half; sum of B yet to be taken in the second half) with (N / 2 * maxB)² * N * N / 2 = 78m states.

The starting points are (0, 0, 0, S) for all possible S. Therefore you can track through S in the outer loop and have a 3-dimensional DP with the same complexity.

First of all if X = 0 we should sort projects by a[i] / b[i] and in each half that order is the best possible.

Let's fix B sum of b[i] in the second half. Then dp[i][j][k] — the best possible amount of money with j projects in the second half, b[s₁] + b[s₂] + ... + b[s_t] = k where s₁, s₂, ...s_k is the set of projects in the second half. Then if we put i-th project to the first half we should increase answer by a[i]·(B + b[0] + ... + b[i]) and something similar if we put i-th project to the second half. Then the answer with fixed value of B is dp[n][n / 2][B].

I wonder if it can be challenged within the given constraints. I constructed a test where you would need on average N² / 4 swaps to get to the optimal state from the random one, but this attempt at failing it failed:)

Cool bug in 500: you should change i to i1 in one place. :) That's what happens when you forget about sort in the first place.

Yes, see the aforementioned solution by totsamyzed. Although, I believe, it is simple hill climbing.

Yes, I also did it. I use something like gradient descent and pass system test.

Repeat following procedure for about 10 times:

1. First, sort all elements by b_i/a_i

2. Repeatly about 10^5 times: randomly swap one from first half and one from second half. Then, sort first half and second half by b_i/a_i again. If the resulting list is better then take it to replace the original one.

In my room I saw a guy who just hardcoded sums for each of i * 1e7 up to 1e9 (100 numbers), then summed up values from (n / 1e7 + 1) to (n) and added this numbers. It passed :P

Why 2³⁰? There are only 26 possible answers, and this can be solved in 2²⁶·26 (forward pass — compute D_i, mask =  count of t_j so that t_j is submask of mask and the last i bits are identical to the bits of mask, backward pass — compute d_i, mask =  count of t_i, t_j such that t_i|t_j is submask of mask, the last i - 1 bits are 1 and i'th bit is 0).

But 2²⁶·26 is almost 2 billion, and I sincerely hope jury's solution is much faster (otherwise this is rather evil).

Think positive: at least you're not getting Internal Server Error.