### liys's blog

By liys, 5 years ago, , First post on Codeforces. I hope you enjoy it.

Codeforces Round #215 (Div. 1) Problem C — Sereja and the Arrangement of Numbers

## Analysis

Treat each q[i] as vertex, and treat each pair of a[j] and a[j+1] as an edge. What we need is a semi-Eulerian graph in which multiple edges are allowed between two edges, and each vertex must be connected to another by at least one direct edge. Situation for 5 vertexes, which can afford edges not less than 10. Situation for 6 vertexes, which can afford edges not less than 17.

## Solve

First, calculate the maximum number of q[i]s that are available for the limit of number of edges, store it into N. Second, sort the w[] in a descending order, pick N largest costs, the sum of which is the answer.

## Notice

For each given n, there are n-1 instead of n edges that are available in the graph: a-a, a-a, a-a, ... , a[n-1]-a[n].

## Code

#include<algorithm>
#include<cstdio>
#include<iostream>
using namespace std;

long long calc(long long limit, long long sup)
{
long long inf = 1;
while(inf < sup)
{
long long mid((inf + sup + 1) >> 1);
// for odd vertexes, the complete graph is what we need
if(mid & 1)
{
long long temp(mid * (mid - 1) >> 1);
if(temp <= limit)
inf = mid;
else
sup = mid - 1;
}
// for even vertexes, the complete graph is not semi-Eulerian
else
{
// we need to add some edges to make it semi-Eulerian
long long temp((mid * (mid - 1) >> 1) + (mid / 2 - 1));
if(temp <= limit)
inf = mid;
else
sup = mid - 1;
}
}
return inf;
}

long long value;

bool cmp(long long x, long long y)
{
return y < x;
}

int main()
{
long long n, m;
scanf("%I64d%I64d", &n, &m);
n = calc(n - 1, m);
// replaces n with the result
for(long long i(0); i != m; ++i)
{
long long x;
scanf("%I64d%I64d", &x, value + i);
}
sort(value, value + m, cmp);
long long ans(0);
for(long long i(0); i != n; ++i)
ans += value[i];
printf("%I64d\n", ans);
}


5254205  Comments (14)
 » So, in the case of an even node count, how can we prove that we need to add at least edges so that the graph becomes semi-Eulerian? And how do we prove that this is always possible?
•  » » If the graph is semi-Eulerian, than every vertex (maybe except two of them) is of even degree.If k is even, then there are exactly k vertices with odd degree. If you add an edge, than, obviously, not more than two vertices can change their degree from odd to even. So, you need to add at least (k — (k-2)) / 2 = k-1 edges.It is sufficient, because you can add edges 1-2, 3-4, ..., k-4 — k-3.
•  » » » Oh okay, I didn't know that theorem about semi-Eulerian graphs. Thanks a lot.
•  » » » very nice proof. thanks a lot! :)
•  » » A graph is semi-Eulerian iff the number of nodes with odd degree is at most 2. In the case of a complete graph on n vertices, where n is even, initially all nodes have odd degree. If you add a edge to the graph, the number of nodes with odd degree will not decrease by more than two. On the other hand, if you connect two nodes which have odd degree, it will decrease by two. So the optimal way to add a minimum number of edges to the graph and make it semi-Eulerian is to connect pairwise the vertices with odd degree (all but two).
•  » » » Thanks! Makes a lot of sense.
•  » » 5 years ago, # ^ | ← Rev. 3 →   This can actually be interpreted as "Count the minimum number of paths to travel through all edges such that each edge is crossed exactly once" (then we simply add duplicating edges to connect these paths). Degrees of nodes in each path decrease by an even number except for the first and the last (they can be the same). Hence, at most we can reduce the number of odd-degreed nodes by 2 with one path. When n is even, we need n / 2 paths which means n / 2 - 1 duplicating edges.
•  » » When n is even, there're n odd nodes. One multiple egde can make two of them become even. To get the minium ans we just let two points stay odd. So it's the answer.In addition, nice post, @Shuaishuai » Looks like the general name of this problem is "Chinese postman's problem" - "finding the minimum length, edge-covering tour of a graph G(N, A) with no restrictions placed on G other than that it be connected and undirected." http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.4.html
•  » » Nice abstract, but this problem seems easier than Chinese postman's problem, because the length of every edges are equal.
 » this is a cool reduction of the problem... thanks guys :D
 » Your analysis is splendid. But I just have some troble understanding why we could transform the problem into the one relating to Eular path and semi-Eulerian graph. Could you explain it to me? Thank you!
•  » » Since each pair of (x, y) is connected, I came to the thought of a complete graph. Also, considering that a-a-a-...-a[n] is a road that goes through all the edges in the graph, I determined that this graph is semi-Eulerian.
 » Here is an easier way to code the same: 45590224