4pm UTC (11am EST) on Tuesday, if I calculated correctly.

Thanks for pointing this out; the issue was that the sample case was not the first test case. This is being fixed and past submissions are being regraded.

Subtracting k from possible.size() can do bad things, since possible.size() is an unsigned int.

Thanks for pointing it out! My solution should now be fixed.

I believe the solution is correct as is, though the number of parentheses is admittedly confusing. We are subtracting s[N] - s[N - 1] from the total number of ways.

Take a look at the C/C++ technical details on the instructions page (http://www.usaco.org/index.php?page=instructions).

Maybe the judge decided to perform some rounding...

Minor typo — I think you mean "decrement L twice."

These are the steps I used to compare two pairs (of a base point + a vector):

1. Compare the angles of the vectors

2. If those are equal, the lines are parallel; now compare their projections onto a line perpendicular to them

3. If those are equal, the lines coincide; now check which pair has a base point "further along" the line (and break ties by comparing the second points in the same fashion)

To check which point is "further along" we can just check if the dot product of their difference with the line vector is positive or negative.

This exact solution worked for me. The only optimizations I made were using no floating point operations (which might have been necessary anyway to deal with parallel lines and collinearity), and looping through only N(N - 1) / 2 lines rather than N(N - 1) lines (though that this works might have been obvious to other people, at first it wasn't to me).

Also, it's not necessary to figure out the list of points on a line and reverse them. If we sort the lines (i.e. pairs of points) properly, at each time-step we can just swap the two points which define the current line. After all pairs of points with a certain slope are processed, the points on one line will be reversed.

http://cms.ioi-jp.org/contest/

Does anyone know if accounts from main.edu.pl will be migrated to szkopul.edu.pl too?

My guess (which could be completely wrong) was that there is no faster solution aside from improvements in matrix multiplication. This problem seems to be equivalent, in some sense, to multiplying and exponentiating matrices.

Since we have to remove the case when r=1, we must subtract 1 from the final answer (so for n=5, we get 3). The answer for n=5 should be 3, since we also have the sum of 15 consecutive positive integers (120 = 1 + 2 + ... + 14 + 15).

Sure. To get that first formula, notice that

Simplifying the formula in my previous comment, we get

Instead of counting all pairs (r,a) we will count all pairs (r,r+2a+1) because it's simpler: now we're just counting all ordered pairs (x,y) with xy = 2N! where x<y and x and y have different parity.

This is equivalent to counting the number of odd divisors of 2N!. I can explain the solution to this reduced problem if you're still stuck.

Any sum of consecutive integers can be described by a low value a and a length r. So we must have:

Try simplifying this expression and then factoring it.

Here we go: 14144018

Here's my solution, which receives full points after a small bug-fix:

We binary search on D, so now we need to solve the problem of finding whether a given value of D works. This is in two parts: joining with union-find all points within distance D, and then applying knapsack to each component to test if some subset adds to 0 mod K.

Part 1: Scan by x-value, maintaining a set sorted by y-value of all points with x-value at most D behind the leading line. Now for each point (a,b) in our scan, we iterate in the set through all points in this set with y-value in (b-D,b+D), and join to (a,b) all points within distance D. These are the points in the rectangle [a-d,a]x[b-D,b+D]. Note that by Pigeonhole, if we ever find a component of size at least K, we may stop and return a YES. This short-circuiting means (I think) that there can only be ~180 points in this box without more than K points lying in close proximity, and in most cases there should be much less.

Part 2 modulo knapsack is quite easy, so of course this is where I made a bug.

This solution is O(N*K*log(MAX_DIST)) but runs in less than 0.5 seconds on the test data.

Here's my understanding of the solution provided in your link:

A sufficiently 'nice' sum that depends only on N will be a polynomial on N. I don't have a definition of 'nice' or a proof that this sum is 'nice', but several examples should convince you of this — or or .

Furthermore, the degree of the polynomial should be 10. We're multiplying five terms and summing over five variables. Again, take a look at the above examples — the third one should be a degree-three polynomial in N, as we are multiplying one term and summing over two variables.

Unfortunately, we don't know the coefficients of this magical 10th degree polynomial. However, we can find them if we have 10 linear equations in terms of these coefficients. Let P(N) = c₁₀x¹⁰ + ... + c₁x + c₀. Then our desired equations are P(N_i) = c₁₀(N_i)¹⁰ + ... + c₁N_i + c₀ for 10 different N_i, where P(N_i) must be calculated manually or with a slow program.

Finally, we put these equations into an augmented matrix and use Gaussian elimination to solve for the 'variables', which are the 10 coefficients c_i. Now we simply evaluate P(N) for each given N.

Well, he gave 167 people a contest to remember.

Thank you tourist!

The line " if ( L — lo > 1 || ans != -1) " doesn't take into account the case where L > hi. Try this case, for example:

4 2
4 8 8 1
4 12 12 0

Here's your code modified to pass: 12140485

Thanks, fixed.

Here's another O(N log(N)) solution for C (which can be made O(N) with a simple modification).

Let ans[i] be the number of moves to reach the state where all numbers are equal to i.

Also, notice that any minimal sequence of moves for one number consists of some number of divisions, followed by some number of multiplications.

Now suppose that we have ans[k / 2] and want to find ans[k].

Case 1: k is even.

Every number i that cannot reach k with only divisions must end its sequence of moves i -  > ... -  > k with a multiplication k / 2 -  > 2 * (k / 2) = k, so it requires one more move to reach k than to reach k/2.

Every number i that can reach k with only divisions must pass through k on any minimal sequence i -  > ... -  > k / 2, so it requires one less move to reach k than to reach k/2.

Case 2: k is odd. By the above logic, the final number can only be k if every i can reach k with only divisions: a multiplication by 2 can never end up at k. If this condition is satisfied, we proceed as above; if not, we mark k as impossible to reach.

Thus if we pre-compute in O(N) the array nreach[i] = number of numbers which can reach i with only divisions, and pre-compute in O(N log(N)) or O(N) ans[1], we can calculate ans[k] for all values of k in O(N) with the formula ans[k] = ans[k / 2] + (N - nreach[k]) - nreach[k].

O(N log(N)) code: 12059157 O(N) code: 12060248