You are not logged in. Please login at www.codechef.com to post your questions!

×

# Abacus'17-OLPC Geek Tree Solution

 1 Hello, the contest Abacus'17 has just finished. Can somebody tell how to solve the problem, Geek Tree. asked 18 Mar '17, 00:01 2.6k●1●10●34 accept rate: 7%

 3 try solving this https://www.hackerrank.com/challenges/similarpair answered 18 Mar '17, 01:59 174●5 accept rate: 13%
 2 This u can do easily bu using a dfs and BIT or segment tree.Basically as u go into a branch during dfs u update the node value in BIT.Then u do a search for all values in the range [s-k,s+k] in the ancestors where "s" is the current node value because all those values will be counted as pairs with s. Here is when u will use BIT to find this value: ans+=query(s+k)-query(s-k-1); U find this in O(log n).Then update this current node's value in BIT before going to its children. By doing this u can find the answer for all vertices and hence for the whole subtree. See my code for reference : https://www.codechef.com/viewsolution/13109792 Happy coding ;) answered 18 Mar '17, 00:50 99●5 accept rate: 16% Thanks although I don't know BIT or segment trees yet. So, I'll probably try this problem later. (18 Mar '17, 01:06) Can you please elaborate your answer? What will you get in ans after performing this query? And why there is a need of update in this offline query? (18 Mar '17, 01:38)
 0 Can someone tell the solution for this problem too : https://www.codechef.com/ABCS2017/problems/ABCS05 answered 18 Mar '17, 00:11 497●1●8 accept rate: 15%
 0 @tihorsharma In this problem,try drawing a matrix to come up with a solution. You will observe a pattern. If u still can't figure it out, tell me and I'll tell u the full solution. answered 18 Mar '17, 00:21 2.6k●1●10●34 accept rate: 7% Okay I will try Thanks :) (18 Mar '17, 00:27)
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×218

question asked: 18 Mar '17, 00:01

question was seen: 367 times

last updated: 18 Mar '17, 01:59