 # COOK82D - Editorial

Author: Hussain Kara Fallah
Secondary Tester: Istvan Nagi
Editorialist: Udit Sanghi

MEDIUM

### 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

4 Likes

Editorialist solution also doesnt work atm.

Yeah just updated.

2 Likes

I was using a prefix xor to check for all degrees being zero but got WA.if the ith edge connects x and y then prefix[i]_xor=prefix_xor[i-1]^x^y.For a particular query if the occurrences of all numbers is even,i.e indegree of every node is even,then the xor of that particular segment should also be zero.Thus,answer will be yes,otherwise no.Can anyone point out what is wrong with this approach?

For other users, it might ask you to enter the code on screen. Enter it to proceed to the solution. BTW, nice job on editorial dear 1 Like

Try this:

6 2

1 6

3 4

1

1 2

1^6^3^4 = 0

This only works incase if there is only one number odd number of times. and rest even.

4 Likes

Thanks!!!.

1 Like

@aditya730, as mentioned by you, its necessary condition for ‘yes’ answer, but not sufficient condition. Suppose 1st edge connects vertices (4, 6) and second edge connects vertices (2, 4). The resultant xor for segment of edges (1, 2) will be zero. But the answer is ‘no’ for it.

2 Likes

How do we know that there are no collisions in this hash?

5 Likes

You can make multiple hash functions with different ‘modulo’ and ‘prime’ to decrease the probabilty of collisions. Generally 2 different modulo should suffice.

1 Like

I’ve used sqrt-decomposition, but got time limit exceed.

1 Like

The probability is very less. We can’t avoid that just like in a quick sort problem the worst case is O(n^2) but the probability is very less.

2 Likes

@mathecodician I don’t get it why such a question was there which doesn’t have a worst case proof. I didn’t implement hashing solution for a long time thinking it will fail, then I decided to go for double hashing with two close primes just to be extra cautious. Also, comparing it to quick sort is incorrect as in quicksort you can at least argue something in expectation or in amortized time but if a collision happens then your answer is wrong for sure.

5 Likes

I am feeling dumb I did everything right… Just printed “YES”/“NO” instead of “Yes”/“No” :’(

1 Like

“The condition necessary for an Eulerian circuit is that the degree of all vertices is divisible by 2.” Can someone help me prove that this condition is sufficient as well?

You can see this by observation but if u want the proof u can see this, https://math.stackexchange.com/questions/671624/proving-that-a-euler-circuit-has-a-even-degree-for-every-vertex

1 Like

When will the editorials for COOK82C and COOK82E come (if they will)?

1 Like

@mathecodician That link proves that the condition is necessary. It doesn’t prove that the condition is sufficient as well.

1 Like

@praran26 See this
Even Degree for each node can be visualized as

1.You need to traverse each edge once