infoarena

http://www.infoarena.ro/blog/hill-climbing-shortlist

The first problem can be solved using Simulated Annealing method. Time complexity is O(N log P), where P depends on the precision the result is calculated. This method also works for the third problem.

For #1 since it's the squared distance, the x and y coordinates are independent to each other :)
Hence, the cost for x is sum((x[itr] - cX) ^ 2)
And this is sum(x[itr] * x[itr] - 2 * cX * x[itr] + cX * cx)
From this we have a 2nd degree equation
N * cX * cX - 2 * cX * sum(x[itr]) + sum(x[itr] * x[itr])
And cX = sum(x[itr]) / N

#[2, 5] it is correct to do some hill climbing like ... right?

this should run in O(N * logMaxRange * nrDimension) ~ around there :)
with a bigger, lets say, constant

#11 Is there a faster way than making a min-matching in the graph, and the result is just the answer?

[#10]: If n is large (I think N>=7 holds), we can make an undirected graph where the vertices are the N peeps, and the edges are { (u,v) : u is not an enemy of v }. For a large N, the graph would be dense enough for us to apply the Hamiltonian Cycle in a dense graph algorithm, as shown here: http://www.infoarena.ro/ciclu-hamiltonian-in-graf-dens (http://www.infoarena.ro/ciclu-hamiltonian-in-graf-dens).
The cycle would give an "ideal" scenario, where no 2 enemies are near each other. That ought to make them happy enough :) .

For N<7, a brute-force approach should work fine.

For this solution to be correct, I presumed the "enemy" relationships are reciprocal (and, let's be serious, they usually are). If they are not, however, we redefine the edges to be {(u, v) : u is not an enemy of v and v is not an enemy of u}. If the graph is dense, we apply the algorithm. If is is not, then N is small enough and we can use the brute-force (or a randomized approach, if we want to be sneakier).

@Lucian Bicsi

It seems that you're describing a way to minimize *adjacent* enemy relationships, but this is not what the problem asks at all (although I get how the table setting can be confusing). I think this is the actual problem: http://codeforces.com/problemset/problem/272/E.

You are right. I was solving some other problem, for sure  :oops:

#10 it's simple.
we have a bipartite graph, and then assume that cost(G) is equal to the number of edges that are wrong, that is the same 2 persons are in the same team or w/e

let's say that cost(G) is equal to s :)
if 1 person is on the left side, and it has 2 enemies, we can move him to the other table or side, and than he has only 1 enemy.
if we do this, we extract from s 2 and then add 1 to it (by moving it in the wrong side)
in this manner we can do this at most 2 * n times or so and at the end of the day we will end with at most 1 enemy for every guy.

maybe we can do better, like cost(G) = 0, but we only need to have at most 1 enemy so this will do it

That would be correct, but I don't think scanning the people in linear manner would do the job, as moving vertices around may cause earlier-scanned ones to "break" (for example, maybe you have to move vertex no. 5 to the right table, but doing that will make vertex no. 2 have two enemies at his table). What I am thinking now, if the idea works, is keeping all the people in a MAX-heap sorted by the number of enemies at the same table, and solving the problem in a Dijkstra-like manner (XORing the top's table and updating its enemies' status), until the heap top has a priority less than 2.

However, I am not very certain about why it actually works.