GREEDY MOVES DAY 01 – Q2

Minimum Euler Cycle

Problem – https://codeforces.com/problemset/problem/1334/D

To start with, if you don’t know about complete graphs, check this out https://en.wikipedia.org/wiki/Complete_graph

So, we have a complete graph, where each edge needs to be visited only once and we need to find the lexicographical shortest such cycle.

It is a greedy problem, because we know we will start with the vertex 1 first. Then, we will look at shortest among its neighbours. We know it is 2, then we will stand at 2 and look for it’s shortest, we know it is 1. And repeat the process again and again.

To get a clear understanding of the approach, try to write down the adjacency list on paper:

Let us assume our n = 5.

1 -> 2,3,4,5

2->1,3,4,5

3> 1,2,4,5

4> 1,2,3,5

5> 1,2,3,4

Above is our adjacency list. We obviously are starting from node 1. Among it’s available neighbours, we see 2 is shortest, so we visit 2. Now, remove 2 from adjacency list of 1, because we know if we reach to vertex 1, we will not be able to visit 2 again, because we need to visit each edge only once. So updated list for vertex 1 is :

1 -> 3,4,5

Answer till now = 1,2

Now, stand at 2 and we know we will visit 1. Repeat it again and again and we get this:

Answer = 1,2,1,3,1,4,1,5

Updated adjacency list – >

1 ->

2 -> 3,4,5

3-> 2,4,5

4-> 2,3,5

5 > 1,2,3,4

Notice that we cannot visit node 1 from vertex 5, because vertex 1 is not having any edge to visit, so it will be wrong. We, gonna visit node 2 here and repeat the entire process again.

We will notice, ultimately, only node 5 will be remaining with an edge to 1, rest all will be striked out. So, atlast, we again visit node 1.

Obviously, we cannot do this way implementation, as n is order 5. This will TLE. But, notice the final answer carefully.

Final answer = 1,2,1,3,1,4,1,5,2,3,2,4,2,5,3,4,3,5,4,5,1

It looks like this way:

1 -> (2,3,4,5) [First, 1 will come up with all this]

2 -> (3,4,5) [ Then, 2 will come with all this]

3 -> (4,5) [Then, 3 will come with all this]

4 -> (5) [Then, 4 will come with all this]

At last, always 1 will come.

Now, this becomes easy to implement. I have kept a counter, say ct, initialized to 1. If, ct=1, it means we are pairing 1 with [2.3.4.5] and there are exactly n-ct options available to pair with.

Using this, here is my code.

void solve()
{
	ll n,l,r;
	cin >> n >> l >> r;
	ll ct = 1;
    bool flag=0;
    if (r == (n*(n-1)+1)){
        r--;
        flag = 1;
    }
    while(l <= r){
        if (l <= (n-ct)*2){
            if (l%2 == 1){
                cout << ct << " ";
                l++;
            }
            else{
                cout << ct + l/2 << " ";
                l++;
            }
        }
        else{
            l -= 2*(n-ct);
            r -= 2*(n-ct);
            ct++;
        }
    }
    if (flag){  
        cout << 1 << " ";
    }
    cout << endl;
}

Leave a Reply