PROBLEM LINK:
Author: Hussain Kara Fallah
Primary Tester: Hasan Jaddouh
Secondary Tester: Istvan Nagi
Editorialist: Udit Sanghi
DIFFICULTY:
MEDIUM
PREREQUISITES:
PROBLEM:
Given a graph with N nodes and a list of M edges, there are Q queries which ask whether the all the edges from l-th edge to r-th edge form a eulerian circuit or not.
QUICK EXPLANATION:
Maintain a degree array for each node as you add the edges but instead of storing it like a prefix sum hash it up and for each query check whether pref[r] == pref[l-1].
EXPLANATION:
So our first observation is that basically a ‘Deadwing’ graph is a graph which is an Eulerian circuit with just one difference that it need not be connected.
The condition necessary for an Eulerian circuit is that the degree of all vertices is divisible by 2.
So our problem reduces to checking whether the number of occurrences of all numbers is divisible by 2 or not.
Let’s think of a naive method.
We can use prefix sums to keep track of the degree of all the nodes so far.
Like [0,1,0,1,1]
Actually we don’t need the degree, we can just store degree%2.
Then we need to check whether pref[r] - pref[l-1] == 0 or not.
Sadly, we can’t do this. This is very slow. O(nm)
But, we notice one thing here. That is each element is either 0 or 1. So we can hash it up.
So the array [0,1,0,1,1] will become 0(2^0) + 1(2^1) + 0(2^2) + 1(2^3) + 1(2^4) .
So, while we are increasing the degree of a node we just have to do this -
function increase_degree(cur_hash,cur_degree,node){
if cur_degree == 1:
new_hash = cur_hash-2^node
else:
new_hash = cur_hash+2^node
return new_hash
}
So now in each query, we can just check whether pref[r] - pref[l-1] == 0 or pref[r] == pref[l-1].
EDITORIALIST’s, AUTHOR’S AND TESTER’S SOLUTIONS:
EDITORIALIST’s solution: [Here] 333
AUTHOR’s solution: [Here] 444
TESTER’s solution: [Here] 555