FRISBEE- EDITORIAL

PROBLEM LINK:

Practice

Contest

Author: Pritish Priyatosh Nayak

Tester: Sibasish Ghosh

Editorialist: Pritish Priyatosh Nayak

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Graph Theory, Eulerian Graphs , Semi-Eulerian Graphs

PROBLEM:

Basically the problem boils down to :
Given a complete undirected graph of N+1 vertices find out the minimum time to explore all edges at least once if you are allowed to move from one vertex to any other adjacent vertex. Check if that minimum time is less than or equal to given X

QUICK EXPLANATION:

When N+1 is odd, the resulting graph is Eulerian and thus the answer is (N+1)*(N)/2.
When N+1 is even, make the resulting graph semi-Eulerian by adding (N+1)/2-1 edges and final answer is (N+1)*(N)/2+(N+1)/2-1

EXPLANATION:

For case when N+1 is odd:

A complete undirected graph of odd number of vertices is Eulerian as it satisfies the property that all vertex must have even degree. Thus it’s possible to traverse all edges of the graphs without having to re-visit any edge.
So total time in optimal condition is equal to (N+1)*(N)/2.

For case when N+1 is even:

A complete undirected graph of even number of vertices is not Eulerian as it doesn’t satisfy the propery that all vertex must have an even degree.Thus it is impossible to travel all the edges without revisiting any edge.

Now the question arises , how many edges we must re-visit before we are able to traverse the entire graph?
The answer to that is (N+1)/2-1 edges.

Proof?

Well , to traverse the graph edges under minimum time we must make the graph Semi-Eulerian or Eulerian.
By definition Semi-Eulerian graphs are those graphs which have atmost 2 vertices with odd degree. And to make it Eulerian we must make all vertices have even degree. So it’s obvious that it’s better to try make the graph Semi-Eulerian.

To make the graph Semi-Eulerian we can add an edge between 2 vertices and turn them both from odd-degree to even-degree. Total number of pairs is (N+1)/2 and because we are free to leave 1 pair with odd degree , the answer is to add (N+1)/2-1 edges.

So the answer becomes (N+1)*(N)/2 + (N+1)/2-1 .

Compare the minimum time required with given X and print the solution.

Read theory on this site:http://mathonline.wikidot.com/eulerian-graphs-and-semi-eulerian-graphs

SOLUTIONS:

Setter's/Editorialist's Solution
    #include<bits/stdc++.h>
    using namespace std;
     
    int main()
    {
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		int n,x;
    		cin>>n>>x;
    		n++;
    		if(n%2==0){
    			if(n*(n-1)/2+n/2-1<=x)cout<<"Happy";
    			else cout<<"Unhappy";	
    		}
    		else{
    			if(n*(n-1)/2<=x)cout<<"Happy";
    			else cout<<"Unhappy";
    		}
    		cout<<'\n';
    	}
    	return 0;
    } 
Tester's Solution
    #include<bits/stdc++.h>
    #define mod 1000000007
    #define F first
    #define S second
    #define pb push_back
    #define all(v) v.begin(),v.end()
    #define rall(v) v.rbegin(),v.rend()
     
    using namespace std;
    typedef long long int ll;
     
    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        ll t=1;
        cin>>t;
        assert(t >= 1 && t <= 1e3);
        while(t--)
        {
            ll n,x,i,ans;
            cin>>n>>x;
            assert(n >= 1 && n <= 1e4);
            assert(x >= 1 && x <= 1e9);
            n++;
            if(n & 1)
                ans=n*(n-1)/2;
            else ans=(n*(n-1)/2)+(n/2)-1;
            if(ans <= x)
                cout<<"Happy\n";
            else cout<<"Unhappy\n";
        }
        return 0;
    } 
1 Like