antipr000's blog

By antipr000, history, 7 years ago, In English

Hi. This is my first post here. This post is mainly aimed for newbies like me. I recently learned about euler tour but didnt solve any problem until last contest and I am glad that I could solve it in contest time. So those who dont know much about euler tour or segment trees you are at the right place . :) Ok so first lets start with euler tour. Euler tour is nothing but dfs order traversal. When you travel a tree using dfs suppose you insert the node you are currently in,in a vector twice , once when you just entered it and second time when you have already visited all its children. So suppose you are at some vertex v with children v1,v2,v3. Let v1,v2,v3 be leaf nodes. So if you see the segment of vector having v1 it will be something like v1,v1 and same for v2 and v3. Now if you see the segment of vector having v it will look something like v,v1,v1,v2,v2,v3,v3,v. Now if v1,v2,v3 had children the vector with segment v would look something like v,v1,...,v1,v2,....,v2,v3,...,v3,v . Where ... represents similar represntation for children. Now lets define start[v] as the index when v occurs first time in the vector and end[v] when it occurs for 2nd time. Each vertex would occur exactly twice as we pushed twice during dfs. So from above its clear that in the range [start[v],end[v]] the entire subarray comes and each vertex present exactly twice. So when we will query for a subarray we will query between l=start[v] and r=end[v]. Now the problem boils down to a simple problem. Its same as FLIPCOIN in codechef. So lets solve this. Its clear the light has 2 states either on or off. And we need to count how many of them are on. Lets denote on by 1 and off by 0. The problem now boils down to sum of interval[l,r]. For range update use lazy propagation. Now when you query for [l,r] you will get an ans=2*required ans as each vertex is present twice in that interval. So just divide the ans by 2. my solution link:http://mirror.codeforces.com/contest/877/submission/31652064 If you have any doubt feel free to comment

Problems for practise : http://mirror.codeforces.com/problemset/problem/620/E

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide links for some problems based on this algorithm?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am sorry this was the first problem i solved using this. If anyone has variants of eulers tour please do post :)

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for your efforts. But formatting could be improved.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am sorry. This is my first post. Dont know much about how to do formatting and stuffs. Hopefully i will learn with more posts :)

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it +6 Vote: I do not like it

      You can write code using the backticks like this: `code`

      Also add a few newlines in the text, that would help making the text more readable.

      And protip: You can still edit your post. So go on and make it better.

»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

You can put this problem for practise. LINK

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by antipr000 (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can add the problem you solved in contest in practice problems :p