MTEL-Editorial

PROBLEM LINK:

MTEL
Practice link

Author: Hitk Codechef Chapter

Tester: Ankur Kayal

Editorialist: Hitk Codechef Chapter

DIFFICULTY:

Intermediate

PREREQUISITES:

Basic Mathematics, Ad Hocs, Graphs

PROBLEM:

In the given problem, ‘a’ gives the number of telephones in the city. Each of the ‘a’ number of telephones should be connected to ‘b’ number of telephones.

QUICK EXPLANATION:

We can think of each telephone to be a vertex in the graph and the wires connecting them as the edges. Then this becomes a basic question of the Handshaking theorem.

EXPLANATION:

In the given problem, ‘a’ gives the number of telephones in the city. Each of the ‘a’ number of telephones should be connected to ‘b’ number of telephones.

(The degree of a vertex is the number of edges connected to it). Hence, the degree of each of the ‘a’ vertices is ‘b’ which gives the sum of degree of all the vertices to be a*b (by unitary method).

In graph theory, Handshaking Theorem or Handshaking Lemma or Sum of Degree of Vertices Theorem states that “sum of degree of all vertices is twice the number of edges contained in it”.

By the handshaking theorem,

ab =2(number of edges in the entire graph).

According to this relation, a*b should always be even.

Also, one telephone can be at max connected to all the other a-1 telephones and

so, 0<=b<a.

Time Complexity

O(1).

SOLUTIONS:

Setter's Solution
#include <iostream>
 
using namespace std;
 
int main()
{
    unsigned long int t , a , b ;
    unsigned long long int c;
    cin >> t ;
    while ( t-- ) 
    {
        cin >> a >> b ;
        if( a <= b || ( a % 2 != 0 && b % 2 != 0 ) )
            cout <<-1 <<endl ;
        else
        {
            c = ( a * b ) / 2 ;
            cout<< c <<endl;
        }   
    }
    return 0;
} 

Tester's Solution
#include <bits/stdc++.h>
using namespace std;

//----------------------------------- DEBUG -----------------------------------
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }

//----------------------------------- END DEBUG --------------------------------

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

//----------------------------------- DEFINES ----------------------------------- 

#define sz(x) (int)(x).size()
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ins insert
#define nl '\n'

//----------------------------------- END DEFINES -------------------------------- 

//-------------------------- CUSTOM UNORDERED MAP HASH ---------------------------

struct custom_hash{
    static uint64_t splitmix64(uint64_t x){
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t a) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(a + FIXED_RANDOM);
    }
    template<class T> size_t operator()(T a) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        hash<T> x;
        return splitmix64(x(a) + FIXED_RANDOM);
    }
    template<class T, class H> size_t operator()(pair<T, H> a) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        hash<T> x;
        hash<H> y;
        return splitmix64(x(a.first) * 37 + y(a.second) + FIXED_RANDOM);
    }
};
template<class T, class H>using umap=unordered_map<T,H,custom_hash>;

//----------------------- CUSTOM UNORDERED MAP HASH END--------------------------

void run_cases() {
    int64_t nodes, degree;
    cin >> nodes >> degree;
    int64_t ans = -1;
    if(degree >= nodes) {
        cout << -1 << nl;
        return;
    }
    if(degree % 2 == 1 and nodes % 2 == 1) {
        cout << -1 << nl;
        return;
    }
    cout << nodes * degree / 2 << nl;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr);

    int tests = 1;
    cin >> tests;

    for(int test = 1;test <= tests;test++) {
        run_cases();
    }
}

Feel free to Share your approach, if you want to. (even if its same !). Suggestions are welcomed as always had been. !