You are not logged in. Please login at www.codechef.com to post your questions!

×

POINTCN - Editorial

1
2

PROBLEM LINK

Practice
Contest

Author: Hasan Jaddouh
Tester: Alexey Zayakin
Editorialist: Jakub Safin

DIFFICULTY

CHALLENGE

PREREQUISITIES

none

PROBLEM

You're given two $N\times N$ matrices $C$ and $D$. Construct a connected undirected graph on $N$ vertices while minimising its total cost. The cost of a graph with $M$ edges $(u_1,v_1),\dots,(u_M,v_M)$ and degrees of vertices $d_1,\dots,d_N$ is $$\sum_{i=1}^M C_{u_i,v_i} + \sum_{i=1}^N D_{i,d_i}\,.$$ Note that the vertex costs aren't necessarily increasing with increasing degrees. The test data are generated randomly.

QUICK EXPLANATION

What, you want a quick explanation for an optimisation problem?

Find a decent solution, then try adding/removing edges and hillclimbing. A decent solution is e.g. the minimum spanning tree or a graph with optimal degrees.

EXPLANATION

First, let's list some statistical results.

  • the expected sum of $N$ random integers, each in the range $[0,M]$, is $\mu=NM/2$

  • Central Limit Theorem tells us that for large enough $N$, the standard deviation of this sum is $\sigma=\frac{\sqrt{N}M}{\sqrt{12}}=\frac{\mu}{\sqrt{3N}}$

  • the expected value of a minimum of $N$ random numbers is $M/(N+1)$; its standard deviation is $\sigma=\mu\sqrt\frac{N}{N+2}$

One thing we can do easily is take a random solution -- with $M$ edges and $N$ vertices, the cost is $~N\frac{H_{max}}{2}+M\frac{C_{max}}{2}$ -- and then try improving it by adding/removing edges (while keeping connectivity) and recalculating the cost; everytime if we find a better solution, we can keep improving that. Each improvement attempt runs in $O(N+M)$, but the limiting factor is just checking if it's still connected, so it can be done in $O(1)$ per failed attempt e.g. if the graph is a spanning tree ($M=N-1$).

It's usually a good idea to take less edges instead of many. We can also try improving a different solution than a random one.

Minimum spanning tree

Note that if the second sum didn't exist, we've got a problem that's well-known and easy to solve: computing the MST of a complete graph. This can be done in $O(N^2)$ using a modification of Jarnik-Prim algorithm which uses a list instead of a heap. Turns out the expected cost of this tree is $~1.2C_{max}$.

Of course, even if we find an MST, the second sum will give us $N$ random costs, so the expected costs of this approach is $~N\frac{H_{max}}{2}+1.2C_{max}$.

Optimal degrees

How about optimising the second sum? We can just pick the minimum $H_{ij}$ for each $i$, but that doesn't guarantee us if there even is a connected graph with these degrees. Regardless, the expected minimum is $~H_{max}/N$, so their expected sum is $~H_{max}$ (instead of $H_{max}N/2$ for random choices).

The required conditions for a connected graph with degrees $d_{1..N}$ are:

  • the sum of degrees must be even (the so-called handshake lemma)

  • $\sum d_i \ge 2(N-1)$

  • no vertex has degree 0

This works because we can just keep making edges between 2 vertices with the currently maximal $d_i$ and decrementing those $d_i$, which gives some graph with $\ge N-1$ vertices; then we can keep removing a non-bridge edge from some component and using it to connect 2 components until the graph is connected.

It might turn out that the degree sequence which gives the minimum cost from $H$ isn't feasible, but non-zero degrees are trivial, the expected $\sum d_i$ is $~N^2/2$ (the indices $j$ which give minima are random) so that condition shouldn't be a problem and if the parity doesn't fit, it can be fixed by changing just one degree. All in all, the cost of the second sum can be $~H_{max}$.

We still need to choose edges to fit the degrees. This is good, because it allows us to minimise the cost of the first sum as far as possible and get something better than $~\frac{C_{max}}{2}\frac{N^2}{4}$ (there are $\sum d_i/2$ edges). After we choose the edges, we can still run the hill-climbing / random optimisation.

Something else

We have described two approaches which try to minimise one sum at the cost of keeping the other pretty large. Something in between would be even better -- picking degrees so that the cost from $H$ wouldn't be toolarge and the number of edges wouldn't be too large either, choosing worse edges to get better degrees... it also depends on the specific values of $C_{max}$ and $H_{max}$.

What did you use?

AUTHOR'S AND TESTER'S SOLUTIONS

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 07 Oct '17, 19:32

xellos0's gravatar image

7★xellos0
5.9k54394
accept rate: 10%

edited 17 Oct '17, 10:44

admin's gravatar image

0★admin ♦♦
19.8k350498541


Setter's solution is the default template.

link

answered 16 Oct '17, 16:30

kaldiuo's gravatar image

4★kaldiuo
212
accept rate: 0%

vital part of problem is Minimum spanning tree.after that we have a network that all connected to each other ... now we can use add or remove(must remain connected!) some cable optimally for get best point....in this part we can use many approach for connect office optimally ..

link

answered 16 Oct '17, 16:46

chemtham's gravatar image

2★chemtham
203
accept rate: 0%

edited 16 Oct '17, 16:47

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×858
×140
×72
×5
×4

question asked: 07 Oct '17, 19:32

question was seen: 693 times

last updated: 17 Oct '17, 10:44