I strongly believe, that editorial delivery for SRM is (should be) part of the contest.

The fact, that TopCoder editorials are delayed (currently unavailable ) is really bad I think. So there are two possibilities — to do not care or do something with that. I selected the later. Here it is:

DIV2 — easy (250)

(link)

There nothing really difficult about the logic. One has to modify current array according the rules described in problem statement and check whether new and old arrays are the same. If they are, we are done. Possible mistake is, that one is updating same array (I'll try find counter example, but no-one in my room did that, so maybe it's clear from provided test cases).

DIV2 — medium (500)

(link)

First idea I had was binary search. Problem is, that cost function is quadratic (so I didn't solve the problem during the contest) — it's easy to see, that if we want to move all cars far to the left/right the value of the function is increasing. Very nice implementation of binary search had user torres89 in my room (46). The idea is such, that instead of one middle point, we need two, let say for position i and i+1, according the value in those point we know in which part of the quadratic function we are, so we know which part we can eliminate (and search for minimum in other part).

	double EPS = 0.01;

	// ps is ordered array of pairs - start position f (from) and length l
	private double ternarySearch(Pair[] ps) {
		int N = ps.length;
		double left = ps[0].f - 1, right = ps[N-1].f + 1;
		while (right - left > EPS) {
			double p1 = (left + right) / 2;
			double p2 = p1 + EPS;
			double c1 = cost(p1, ps);
			double c2 = cost(p2, ps);
			if (c1 == c2) {
				left = p1;
				right = p2;
			} else if ( c1 < c2 ) {
				right = p1;
			} else {
				left = p2; 
			}
			
		}
		double p = (left + right)/2;
		double fc = cost(p, ps);
		System.out.printf("p=%f, c=%f%n", p, fc);
		return fc;
	}

	private double cost(double p, Pair[] ps) {
		double res = 0;
		double e = p;
		for (int i = 0; i < ps.length; i++) {
			res += Math.abs(ps[i].f - e);
			e += ps[i].l;
		}
		return res;
	}

DIV2 — hard (1000)

Note: Sorry guys, I didn't find how to use latex on CodeForces — I also asked here, when someone helps me, I'll correct it

This is inspired by amit43's solution (linked below).

To maximize probability that at least one player wins, out strategy is to place the tokes uniformly over the m fields. So we will have on L (lower) tokens on LC (lower count) fields and G (greater) tokens on GC fields. The formula is:

Pseudocode without caching is:

L  = n / m;
G  = L + 1
LC = n % m;
GC = m - LC;
P(n, k) = LC/m * P(n-L, k-1)
        + GC/m * P(n-G, k-1)

Terminating conditions for P are clear — when incomming n is 0, the probability is 0.0, if n > 0 and there are no rounds (k = 0), probability is 1.0.

Ona has to add hashing to prevent calculation of already calculated fields. While n is up to 10^12, we cannot use array.

Examples of complete solutions:

• amit43's code (winner of DIV 2)
• torress89's

Opened questions:

1. I cannot see, why result is long instead of double while in problem statement for medium is written:

   (Note that there is no restriction on the movement of cars or on the final position of the train. Janusz may push the cars in any order, and he may even push some cars by a non-integer number of meters if he wants to.)

2. when we use map<pair<long long, int>> what is the upper bound for number of elements in the map. What I can see is, that while n < m n is decreasing slowly...

3. the strategy for hard problem is intuitively correct, some simple idea why it works? For first test case P(3, 2) is 0.75, if we place all 3 to one field, probability decrease to 0.5

Answers:

1. I implemented ternary search with doubles and EPS = 0.01, so I place cars at point p, that is in distance at most EPS from min. I such solution the best points where the train starts are 5.255 for first test case and 152949945.885 for last test case, but the cost seems to be always integer.

2. I checked that experimentally and size of the map for n = 2⁶⁰ (a little more that in problem statement 10¹²), m = 50 and k = 50 is 952, probably not max value, for n = 2⁶⁰ - 1 it is 982 and for n=999999999999908879 the size is 1164

Someone might be interested in other discussions:

• http://codeforces.me/blog/entry/15747 (currently DIV 1 mainly)
• http://codeforces.me/blog/entry/15730
• Xellos0's notes on TopCoder