COOK82D - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

MEDIUM

PREREQUISITES:

Hashing, Eulerian Circuit

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
2

Editorialist solution also doesnt work atm.

3

Yeah just updated.

2 Likes
4

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?

5

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 :slight_smile:

1 Like
6

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
7

Thanks!!!.

1 Like
8

@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
9

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

5 Likes
10

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
11

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

1 Like
12

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
13

@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
14

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

1 Like
15

“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?

16

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
17

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

1 Like
18

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

1 Like
19

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

1.You need to traverse each edge once

2.You need to return to the initial node

So if you enter a node using some edge you need to leave the node (to satisfy point2) using some other edge (to satisfy point1) . So for each entering edge to a node there exits a unique leaving edge from that node . So the degree of each node must be even.This proves necessity of even degree.

Sufficiency can be visualized as since the degree of each node is even you can move to any node (visit it) and then leave it until you’ve exhausted all the edges.You could return to the initial node by choosing such a tour(of many available tours) such that you visit the edge corresponding to the initial vertex last.

1 Like
20

Quick explanation - instead of storing it like a prefix sum hash it up

can any one tell me what that means, i know hashing theortically but never used in competitive programming