Betlista's blog

By Betlista, 9 years ago, In English

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:

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 = 260 (a little more that in problem statement 1012), m = 50 and k = 50 is 952, probably not max value, for n = 260 - 1 it is 982 and for n=999999999999908879 the size is 1164

Someone might be interested in other discussions:

  • Vote: I like it
  • +31
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

More detailed description of the trick Betlista described in editorial of 500 — /blog/entry/11497.

»
9 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Div2 500 can be done without bin.search — you may just greedy remove every gap by either moving all cars from the left or moving all cars from the right.

As the cost function is quadratic — you need ternary search. torres89 moved from searching minimum of function to searching a point where derivative of function is equal to zero — and for this problem you can use binary search.

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Easier Solution For 500:

Assemble all cars at the median, i.e. if n = number of cars is odd, don't move the central car and assemble all other cars around this car and if n is even, assemble all cars either around n/2th car of around (n/2+1)th car.

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    After trying complicated things, I said to myself "hey you are in DIV2, so think simple". Then I came up with the same idea but unfortunately did not manage to submit in time :(

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I tried the solution, that was moving always first/last car to the next/previous one, but I have a bug there and it returns lower cost for last test case...

If someone has a free time, some help might be fine (maybe some smaller test case, let say with length 5 would be great), otherwise I'll try to find it my way ;-)

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I found the problem, now it returns what I expected — not optimal solution, for example for

    { 1, 6, 11, 19, 23, 30 }
    { 5, 1, 5, 4, 1, 1 }
    

    -> 13 instead of 11

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

For DIV 2 500 pointer,my solution sets every car as center and moves all the cars left and right of it.Then by comparing all the costs sets the minimum one as answer.

It passed the test & system cases.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also did the same. The number of coaches is less than or equal to 50. So O(n^2) will pass easily

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks :) Nice editorial :)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You know, if you intend to write editorials, you can do this formally at TopCoder (then they will pay you, and your editorial will be in the wiki). See vexorian's blog for some insights on what it's like to be an editorialist ;)

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it +14 Vote: I do not like it

    I sent two e-mails to TopCoder and I received no reply. I also asked vexorian for help with that, using messages here on CodeForces, but probably he is too busy :-( On the other side I'm also happy for that, because this is somewhere in the middle (official/unofficial) — it does not need to be so precise and that's why I can delivery it a lot earlier. Also, as you can see from my rating, I'm not able to crack DIV1 problems, but that's ok for now, my main goal is to help DIV2 contestants, I believe they need the help (editorial) more ;-)

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks for the Editorial for DIV2 Contestants....It is much needed....

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    That matter was discussed a bit here, there was no response from any admin (not even "thinking about it" style response, only from Nickolas). When even SRM forums aren't bumped...

    I also started writing down some div1 editorialey things — even though the main editorial page says anyone can edit the editorials, it's not true at all.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I saw that, tried in SRM 644, asking for the same via e-mail, but no reply at all. Maybe it was meant you can edit existing editorial (but not to add new), which is strange.

      Nicely done ;-) I stopped trying with topcoder pages (I never used TopCoder's wiki before), it's a lot easier here. I'll link your wiki post when I get notification about the change ;-)