liys's blog

By liys, 10 years ago, In English

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[1]-a[2], a[2]-a[3], a[3]-a[4], ... , 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[100010];

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

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

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

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?

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

    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.

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

      Oh okay, I didn't know that theorem about semi-Eulerian graphs. Thanks a lot.

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

      very nice proof. thanks a lot! :)

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

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

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

    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.

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

    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, @Shuaishuailiyishuai

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

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

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

    Nice abstract, but this problem seems easier than Chinese postman's problem, because the length of every edges are equal.

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

this is a cool reduction of the problem... thanks guys :D

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

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!

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

    Since each pair of (x, y) is connected, I came to the thought of a complete graph. Also, considering that a[1]-a[2]-a[3]-...-a[n] is a road that goes through all the edges in the graph, I determined that this graph is semi-Eulerian.

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

Here is an easier way to code the same: 45590224

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

THERE ARE TWO CASES 1) NUMBER OF VERTICES ARE ODD THEN IN THE COMPLETE GRAPH THE DEGREE OF EVERY VERTEX WOULD BE EVEN AND THIS IS A NECESSARY AND SUFFICIENT CONDITION FOR A EULER GRAPH AS ALL THE VERTICES HAVE EVEN DEGREE AND THERE IS ONLY ONE COMPONENT IN THE GRAPH AND IT CONTAINS ALL THE EDGES SO EULER TOUR IS POSSIBLE IN THIS GRAPH IN THIS WAY WE CAN TRAVEL THROUGH EACH OF THE N*(N-1)/2 EDGES EXACTLY ONCE AND IT IS A EULER TOUR OF THE GRAPH.2)NUMBER OF VERTICES ARE EVEN THEN IN THE COMPLETE GRAPH THE DEGREE OF EVERY VERTEX WOULD BE ODD AND THIS IS NOT SUFFICIENT CONDITION FOR A EULER OR A SEMI EULERIAN GRAPH BUT WE CAN MAKE IT A SEMI EULERIAN GRAPH BY MAKING THE DEGREE OF N-2 VERTICES AND EVEN AND LEAVING THE OTHER TWO AS ODD IN THIS WAY WE CAN TRAVEL THROUGH EACH OF THE EDGES (N*(N-1))/2 ATLEAST ONCE AND THAT TOO IN MINIMUM NUMBER OF STEPS AND IT IS THE SEMI EULERIAN TOUR OF THE GRAPH.