Hill Climbing Shortlist

[•Cosmin]

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

[•SebiSebi]

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.

[•loses]

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?

Cod:

rez = [0, 0]
p = maxRange
while p >= 0:
  mn = f(rez)
  where = -1
  for dir in allDirections(2 * nrDimensions):
    if f(rez + changeDir[dir] * p) < mn:
      mn = f(rez + changeDir[dir] * p)
      where = dir
  if where == -1:
    p /= 2
  else 
    rez = changeDir[where] * p + rez

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?

[•retrograd]

[#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.
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).

[•klamathix]

@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.

[•retrograd]

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

[•loses]

#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

[•retrograd]

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.